大家好,又见面了,我是全栈君。
队列:
先进先出,处理类似排队的问题,先排的。先处理,后排的等前面的处理完了,再处理
对于插入和移除操作的时间复杂度都为O(1)。从后面插入,从前面移除
双端队列:
即在队列两端都能够insert和remove:insertLeft、insertRight。removeLeft、removeRight
含有栈和队列的功能,如去掉insertLeft、removeLeft,那就跟栈一样了。如去掉insertLeft、removeRight。那就跟队列一样了
一般使用频率较低,时间复杂度 O(1)
优先级队列:
内部维护一个按优先级排序的序列。插入时须要比較查找插入的位置,时间复杂度O(N), 删除O(1)
/* * 队列 先进先出。一个指针指示插入的位置,一个指针指示取出数据项的位置 */public class QueueQ<T> { private int max; private T[] ary; private int front; //队头指针 指示取出数据项的位置 private int rear; //队尾指针 指示插入的位置 private int nItems; //实际数据项个数 public QueueQ(int size) { this.max = size; ary = (T[]) new Object[max]; front = 0; rear = -1; nItems = 0; } //插入队尾 public void insert(T t) { if (rear == max - 1) {//已到实际队尾,从头開始 rear = -1; } ary[++rear] = t; nItems++; } //移除队头 public T remove() { T temp = ary[front++]; if (front == max) {//列队到尾了,从头開始 front = 0; } nItems--; return temp; } //查看队头 public T peek() { return ary[front]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQ<Integer> queue = new QueueQ<Integer>(3); for (int i = 0; i < 5; i++) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 0; i < 5; i++) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } System.out.println("----"); for (int i = 5; i > 0; i--) { queue.insert(i); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer peek = queue.peek(); System.out.println("peek:" + peek); System.out.println("size:" + queue.size()); } for (int i = 5; i > 0; i--) { Integer remove = queue.remove(); System.out.println("remove:" + remove); System.out.println("size:" + queue.size()); } } }
/* * 双端队列<span style="white-space:pre"> </span>两端插入、删除 */ public class QueueQT<T> { private LinkedList<T> list; public QueueQT() { list = new LinkedList<T>(); } // 插入队头 public void insertLeft(T t) { list.addFirst(t); } // 插入队尾 public void insertRight(T t) { list.addLast(t); } // 移除队头 public T removeLeft() { return list.removeFirst(); } // 移除队尾 public T removeRight() { return list.removeLast(); } // 查看队头 public T peekLeft() { return list.getFirst(); } // 查看队尾 public T peekRight() { return list.getLast(); } public boolean isEmpty() { return list.isEmpty(); } public int size() { return list.size(); } }
/* * 优先级队列 队列中按优先级排序。是一个有序的队列 */ public class QueueQP { private int max; private int[] ary; private int nItems; //实际数据项个数 public QueueQP(int size) { this.max = size; ary = new int[max]; nItems = 0; } //插入队尾 public void insert(int t) { int j; if (nItems == 0) { ary[nItems++] = t; } else { for (j = nItems - 1; j >= 0; j--) { if (t > ary[j]) { ary[j + 1] = ary[j]; //前一个赋给后一个 小的在后 相当于用了插入排序。给定序列本来就是有序的。所以效率O(N) } else { break; } } ary[j + 1] = t; nItems++; } System.out.println(Arrays.toString(ary)); } //移除队头 public int remove() { return ary[--nItems]; //移除优先级小的 } //查看队尾 优先级最低的 public int peekMin() { return ary[nItems - 1]; } public boolean isEmpty() { return nItems == 0; } public boolean isFull() { return nItems == max; } public int size() { return nItems; } public static void main(String[] args) { QueueQP queue = new QueueQP(3); queue.insert(1); queue.insert(2); queue.insert(3); int remove = queue.remove(); System.out.println("remove:" + remove); } }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116477.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...