package testQueue;public interface Queue<T> {public abstract boolean isEmpty();public abstract boolean add(Object x);public abstract T peek();public abstract T poll();
}
1. 顺序队列
顺序队列在设计时，用数组存储数据元素。front和rear分别指示队列头和队列尾元素下标，front和rear初始值为-1。入队操作front++，出队操作rear++。当入队的元素个数（包括出队元素）超过数组容量时，rear下标越界。数据溢出，由于数组头部还有很多空位，这种溢出称为假溢出。
所以将顺序队列设计为循环顺序队列。设front为队头元素下标，rear为队尾元素下标。
设计注意点如下：
1. 首尾初始值分别为： front = 0， rear = 0. 空队列的条件是front == rear。
2. 入队操作改变rear，出队操作改变front。
front = (front + 1)%length;
rear = (rear+1)%length;
3. 队列满了的条件是(rear+1)%length == front。此时队列rear指向的位置仍然是空的。如果是设为满队列条件为front==rear，则与空队列条件相同
4. 队列满时再入列，数组容量扩充一倍，按照队列元素次序复制数组元素。
这样的话，设计顺序队列，入队操作和出队操作时间复杂度都是O(1)。
package testQueue;public final class SeqQueue<T> implements Queue<T>{private Object element[];private int front,rear;public SeqQueue(int length){if(length<64){length = 64;}this.element = new Object[length];this.front = this.rear = 0;}public SeqQueue(){this(64);}public String toString(){String str = "Queue(";int j = this.front;while(j != this.rear){str += this.element[j];j++;if(j != this.rear){str += ",";}}return str+")";}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn (this.front==0&&this.rear==0);}@Overridepublic boolean add(Object x) {// TODO Auto-generated method stubif(x == null){return false;}if(this.front == (this.rear+1)%this.element.length){Object[] temp = this.element;this.element = new Object[temp.length*2];int j = 0;for(int i = this.front; i != this.rear; i = (this.rear+1)%temp.length){this.element[j] = temp[i];j++;}this.front = 0;this.rear = j;}this.element[this.rear] = x;this.rear = (this.rear+1)%this.element.length;return true;}@Overridepublic T peek() {// TODO Auto-generated method stubreturn this.isEmpty()?null:(T)this.element[this.front];}@Overridepublic T poll() {// TODO Auto-generated method stubif(this.isEmpty()){return null;}T temp = (T)this.element[this.front];this.front = (this.front+1)%this.element.length;return temp;}public static void main(String[] args){SeqQueue<Integer> sq = new SeqQueue<Integer>();for(int i = 0;i<10;i++){sq.add(i);}System.out.println(sq.isEmpty());System.out.println(sq.toString());sq.poll();System.out.println(sq.toString());System.out.println(sq.peek());}
}
2.链式队列
如果采用单链表作为队列的数据结构，出队操作时间复杂度为O(1)，但入队操作则需要遍历所有结点，在尾结点处插入新的结点，时间复杂度为O(n)。
如果采用循环双链表作为队列的数据结构，时间复杂度均为O(1)。但是占用的存储空间过多。
最佳办法是采用单链表，并且加上尾指针。
- 设置初始空队列，front = rear = null。队列空条件为front == null && rear == null。
- 入队操作，将x结点连在rear以后，并将rear指向x结点，成为新的尾结点。
- 出队操作。当队列不为空时，取得头结点元素。删除队头结点，并使front指向原结点的后继结点。
- 第一个元素入队或者最后一个元素出队时，同时改变front和rear。
package testQueue;public final class LinkedQueue<T> implements Queue<T>{private Node<T> front,rear;public LinkedQueue(){this.front = this.rear = null;}@Overridepublic boolean isEmpty() {// TODO Auto-generated method stubreturn this.front == null && this.rear == null;}@Overridepublic boolean add(T x) {// TODO Auto-generated method stubif(x==null){return false;}Node<T> temp = new Node<T>(x,null);if(this.front == null){this.front = temp;this.rear = temp;}else{this.rear.next = temp;this.rear = temp;}return true;}@Overridepublic T peek() {// TODO Auto-generated method stubreturn this.isEmpty()?null:this.front.data;}@Overridepublic T poll() {// TODO Auto-generated method stubif(this.isEmpty()){return null;}T temp = this.front.data;this.front = this.front.next;return temp;}public String toString(){String str = "LinkedQueue(";Node<T> temp = this.front;while(temp != null){str += temp.toString();temp = temp.next;if(temp != null){str+=",";}}return str+")";}public static void main(String[] args){LinkedQueue<Integer> lq = new LinkedQueue<Integer>();for(int i = 0;i<15;i++){lq.add(i);}System.out.println(lq.peek());System.out.println(lq.poll());System.out.println(lq.toString());lq.add(15);System.out.println(lq.toString());}
}写好啦，测试结果都是正确的。