数据结构（java语言描述）--队列
队列的特点是先进先出。我们将以之前写的链表和动态数组为基础，编写不同的queue。
先建设它的抽象类
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); }
基于array的arrayqueue
public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(int capacity){ array = new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } public int getCapacity(){ return array.getCapacity(); } @Override public int getSize() { return array.getSize(); } @Override public boolean isEmpty() { return array.isEmpty(); } @Override public void enqueue(E e) { array.addLast(e); } @Override public E dequeue() { return array.removeFirst(); } @Override public E getFront() { return array.getFirst(); } //重写toString方法 public String toString(){ StringBuilder res = new StringBuilder(); res.append("top: ["); for (int i = 0; i < array.getSize(); i++){ if (i+1 != array.getSize()-1){ res.append(array.get(i) + ", "); } res.append(array.get(i) + "] tail"); } return res.toString(); } public static void main(String[] args) { ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(); for (int i = 0; i < 10; i++){ arrayQueue.enqueue(i); } for (int i = 0; i < 10; i++){ System.out.println(arrayQueue.dequeue()); } } }
可以看出，数组型队列在入队的操作上时间复杂度是O(1)，在出队操作时需要完全遍历，时间复杂度是O(n)。接下来我们将队列进行改写：
我们将队列改为循环队列
我们始终为data数组中的元素预留一个位置，它是tail所指向的位置，起始位置（即数组为空时front和tail是重合的），front始终指着数组中最早插入的元素。当出队时，front指向下一个元素；当入队时，tail原先的位置放入入队的元素，tail向后移动一位。如此这番，直到tail到达了data.length，即容纳量的边界。而front之前因为做过出队操作，导致会有空缺。这是size和capacity没有到达符合扩容或缩容的微妙条件，我们将tail转向数组的头部。
此时，我们元素所位于的并不是它们的绝对位置，而是相对位置 i%data.length。
public class LoopQueue<E> implements Queue<E>{ private E[] data; private int front, tail; private int size; public LoopQueue(int capcacity){ //容量+1是给tail预留空间 data = (E[])new Object[capcacity+1]; front = 0; tail = 0; size = 0; } public LoopQueue(){ this(10); } public int getCapacity(){ return data.length-1;} @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if ((tail + 1) % data.length == front){ //此时front与tail之间只差一个预留空位，说明空间满了 resize(2*getCapacity()); } data[tail] = e; //tail指针相对向后移动一位 tail = (tail + 1) % data.length; size++; } @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("can not dequeue. queue is empty"); } E ret = data[front]; data[front] = null; front = (front+1) % data.length; size--; if (size == getCapacity() / 4 && getCapacity() / 2 != 0){ resize(getCapacity() / 2); } return ret; } @Override public E getFront() { if (isEmpty()){ throw new IllegalArgumentException("queue is empty"); } return data[front]; } private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++){ newData[i] = data[front % data.length + i]; } data = newData; front = 0; tail = size; } //测试真实位置 public void realStation(){ for (int i = 0; i <= getCapacity(); i++){ System.out.print(data[i] + "\t"); } } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity())); res.append("front ["); for(int i = front ; i != tail ; i = (i + 1) % data.length){ res.append(data[i]); if((i + 1) % data.length != tail) res.append(", "); } res.append("] tail"); return res.toString(); } public static void main(String[] args) { LoopQueue<Integer> loopQueue = new LoopQueue<>(); for (int i = 0; i < 3; i++){ loopQueue.enqueue(i); } loopQueue.dequeue(); loopQueue.enqueue(5); loopQueue.enqueue(7); loopQueue.dequeue(); loopQueue.enqueue(10); System.out.println(loopQueue.toString()); loopQueue.realStation(); } }Queue: size = 4 , capacity = 4
front [2, 5, 7, 10] tail
null 2 5 7 10
此时，在不需要改变容量的情况下，出队和入队时间复杂度为O(1)
基于链表的队列
注：链表的实现就是不断地在其头部添加新的节点，所以删除头部时的速度最快，为O(1)，而删除尾部需要全部遍历，为O(n)，但是队列的实现方式就是在链表头部添加，在尾部删除。所以，在这里我们重新用链表的形式写了一个queue。它拥有一个head和一个tail节点，以指针的形式分别指向链表的头部和尾部。这样使enqueue和dequeue的操作更加明显。
public class LinkedListQueue<E> implements Queue<E>{ LinkedList<E> linkedList = new LinkedList<>(); private class Node{ public E e; public Node next; public Node(E e, Node next){ this.e = e; this.next = next; } public Node(E e){ this(e, null);} public Node(){ this(null, null);} @Override public String toString(){ return e.toString();} } private Node head, tail; private int size; @Override public int getSize() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public void enqueue(E e) { if (tail == null){ tail = new Node(e); head = tail; }else{ tail.next = new Node(e); tail = tail.next; //万万不可写成 //tail = new Node(e); //因为tail是queue的一部分，只有先next一个新节点，使得新节点与queue连接上，才能将tail重新 //设置，记住，tail跟head是具有指针功能 } size++; } @Override public E dequeue() { if (isEmpty()){ throw new IllegalArgumentException("can not dequeue. queue is empty"); } Node retNode = head; head = head.next; if (head == null){ tail = null; } size--; return retNode.e; } @Override public E getFront() { if (isEmpty()){ throw new IllegalArgumentException("queue is empty"); } return head.e; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue: front["); Node cur = head; while (cur != null){ res.append(cur.e + "->"); cur = cur.next; } res.append("] null tail"); return res.toString(); } public static void main(String[] args) { LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>(); for (int i = 0; i < 10; i++){ linkedListQueue.enqueue(i); } System.out.println(linkedListQueue.toString()); } }
Queue: front[0->1->2->3->4->5->6->7->8->9->] null tail
此时，我们可以看出在enqueue和dequeue过程中，我们只需要将head和tail改变即可，不需要再遍历时间复杂度均为O(1)