《算法导论》学习笔记之Chapter10---队列的数组实现

本文主要是介绍《算法导论》学习笔记之Chapter10---队列的数组实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

紧接上一篇文章，本文记录数组实现队列的实现

队列的定义：顺序存储结构存储的队列称为顺序队列，是一个内部存储元素按顺序排列的列表，遵循先进先出原则。

需要理解的是队列的两个定义：队头front和队尾rear。两者都是指向队列元素的指针，队头指针始终指向队列最先进去的元素的前一个下标位置，初始值可设为-1。队尾指向队列最后进去的元素下标，初始值常为0。

判断队列是否为空的条件是：队头指针是否等于队尾指针，即：rear == front

判断队列是否已满的条件是：队尾指针是否等于队列容量，即：rear == capacity（下面的程序中rear == a.length - 1是因为下标从0开始，其实是一个意思）

public class Queue {public static void main(String[] args) {ArrayQueue queue = new ArrayQueue(10);System.out.println(queue.isEmpty());System.out.println(queue.peekFront());for (int i = 0; i < 10; i++) {queue.insert(i);}System.out.println(queue.isFull());while (!queue.isEmpty()) {System.out.println(queue.remove());}}}class ArrayQueue {private int[] a;// 内置数组private int front;// 头指针-队头指针指向队列头结点的前一个位置private int rear;// 尾指针-队尾指针指向队列尾节点位置public ArrayQueue(int size) {this.a = new int[size];front = -1;rear = -1;}/*** 判断队列是否为空** @return*/public boolean isEmpty() {return front == rear;}/*** 判断队列是否已满** @return*/public boolean isFull() {return a.length - 1 == rear;}/*** 向队列的队尾插入一个元素*/public void insert(int item) {if (isFull()) {throw new RuntimeException("队列已满");}a[++rear] = item;}/*** 获得对头元素** @return*/public int peekFront() {return a[front + 1];}/*** 获得队尾元素** @return*/public int peekRear() {return a[rear];}/*** 从队列的对头移除一个元素** @return*/public int remove() {if (isEmpty()) {throw new RuntimeException("队列为空");}return a[++front];}
}

队列与栈的关系：

队列与栈关系还是较为近的，队列可以实现栈功能，栈也可以实现队列功能。

两个队列实现栈的代码：

class StackOfQueue {Queue<Integer> queue1 = new ArrayDeque<>();Queue<Integer> queue2 = new ArrayDeque<>();public boolean push(int node) {// 两个栈都为空时，优先考虑queue1if (queue1.isEmpty() && queue2.isEmpty()) {queue1.add(node);return true;}// 如果queue1为空，queue2有元素，直接放入queue2if (queue1.isEmpty()) {queue2.add(node);return true;}if (queue2.isEmpty()) {queue1.add(node);return true;}return false;}public int pop() {// 两个栈都为空时，没有元素可以弹出if (queue1.isEmpty() && queue2.isEmpty()) {try {throw new Exception("stack is empty");} catch (Exception e) {}}// 如果queue1为空，queue2有元素， 将queue2的元素依次放入queue1中，直到最后一个元素，我们弹出。if (queue1.isEmpty()) {while (queue2.size() > 1) {queue1.add(queue2.poll());}return queue2.poll();}if (queue2.isEmpty()) {while (queue1.size() > 1) {queue2.add(queue1.poll());}return queue1.poll();}return (Integer) null;}}

两个栈实现队列功能的代码：

class QueueOfStack {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public boolean push(int node) {// 两个栈都为空时，优先考虑queue1if (stack1.isEmpty() && stack2.isEmpty()) {stack1.push(node);return true;}// 如果queue1为空，queue2有元素，直接放入queue2if (stack1.isEmpty()) {stack2.push(node);return true;}if (stack2.isEmpty()) {stack1.push(node);return true;}return false;}public int pop() {// 两个栈都为空时，没有元素可以弹出if (stack1.isEmpty() && stack2.isEmpty()) {try {throw new Exception("queue is empty");} catch (Exception e) {}}// 如果stack1为空，stack2有元素， 将stack2的元素依次放入stack1中，直到最后一个元素，我们弹出。if (stack1.isEmpty()) {while (stack2.size() > 1) {stack1.add(stack2.pop());}return stack2.pop();}if (stack2.isEmpty()) {while (stack1.size() > 1) {stack2.add(stack1.pop());}return stack1.pop();}return (Integer) null;}
}

注释写的还算清楚，以后应该也能轻易看懂。

关于java中队列的使用这里有一篇不错的文章，可以参考一下：http://blog.csdn.net/lzy_lizhiyang/article/details/48311925