和栈类似,队列queue也是表。然而,使用队列时插入在一端进行而删除在另一端进行。
队列的基本操作是enqueue(入队)和dequeue(出队),入队是在队尾rear(表的末端)插入一个元素,出队是删除在队头front(表的开头)的元素。
和栈一样,对于队列而言任何表的实现都可以,而且对于每种操作,链表实现和数组实现都是快速的O(1)时间。下面主要讨论队列的循环数组实现。
对于每一个队列数组结构,我们保留一个数组theArray[]以及位置front和rear,它们表示队列的两端。我们还要记录实际存在于队列中的元素个数currentSize。为使一个元素x入队,我们执行enqueue()使currentSize和rear增1,然后置theArray[rear]=x。为使元素出队列,我们置返回值为theArray[front],并且currentSize减1,然后使front加1。以下是相关代码实现:
import java.util.Iterator; import java.util.NoSuchElementException; public class MyQueue<AnyType> implements Iterable<AnyType> { private static final int DEFAULT_CAPACITY = 10; private AnyType[] theArray; // 以数组存放数据 private int currentSize; // 当前队列的长度,非数组长度 private int front; // 队头 private int rear; // 队尾 /** * 构造函数自动执行clear()函数 */ public MyQueue() { clear(); } /** * 分配内存,初始化各成员变量 */ public void clear() { ensureCapacity(DEFAULT_CAPACITY); currentSize = 0; front = rear = 0; } /** * 返回当前数组长度 * * @return 数组长度 */ public int size() { return theArray.length; } /** * 当前队列是否满 * * @return */ public boolean isFull() { return currentSize == size(); } /** * 当前队列是否空 * * @return */ public boolean isEmpty() { return currentSize == 0; } /** * 根据参数确定数组长度 * * @param newCapacity * 新的大小 */ @SuppressWarnings("unchecked") public void ensureCapacity(int newCapacity) { // 第一次(数组未分配)直接分配内存 if (theArray == null) { theArray = (AnyType[]) new Object[newCapacity]; return; } // 参数小于当前长度直接返回 if (newCapacity < size()) { return; } // 数组扩充时将原数据复制到新分配的数组里 AnyType[] old = theArray; theArray = (AnyType[]) new Object[newCapacity]; for (int i = front; i < front + old.length; i++) { theArray[i - front] = old[i % old.length]; } // 重新赋值各变量 front = 0; rear = old.length - 1; currentSize = old.length; } /** * 入队操作 * * @param value * 入队元素 */ public void enqueue(AnyType value) { // 检查队列是否满 if (isFull()) { ensureCapacity(size() * 2); } // 第一次入队时队尾无数据,直接赋值。之后队尾先加一取余再赋值 if (theArray[rear] != null) { rear = (rear + 1) % size(); } theArray[rear] = value; currentSize++; } /** * 出队操作 * * @return 出队元素 */ public AnyType dequeue() { // 若队列空则无法出队 if (isEmpty()) { throw new NullPointerException(); } // 出队操作 currentSize--; AnyType value = theArray[front]; theArray[front] = null; front = (front + 1) % size(); return value; } /** * 实现Iterable接口 */ public Iterator<AnyType> iterator() { return new QueueIterator(); } private class QueueIterator implements Iterator<AnyType> { private int current = 0; public boolean hasNext() { return current < size(); } public AnyType next() { if (!hasNext()) { throw new NoSuchElementException(); } return theArray[current++]; } } public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<Integer>(); Iterator<Integer> iterator1 = queue.iterator(); Iterator<Integer> iterator2 = queue.iterator(); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); queue.enqueue(4); queue.enqueue(5); queue.enqueue(6); queue.enqueue(7); queue.enqueue(8); queue.enqueue(9); queue.enqueue(10); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.dequeue(); queue.enqueue(11); queue.enqueue(12); System.out.println("队列未超出容量时结果:"); while (iterator1.hasNext()) { System.out.print(iterator1.next() + " "); } System.out.println("\n队列超出容量时结果:"); queue.enqueue(13); queue.enqueue(14); queue.enqueue(15); while (iterator2.hasNext()) { System.out.print(iterator2.next() + " "); } } }执行结果:
队列未超出容量时结果:
11 12 null null 5 6 7 8 9 10
队列超出容量时结果:
5 6 7 8 9 10 11 12 13 14 15 null null null null null null null null null