队列的图文解析和对应语言的实现
队列的介绍
Queue是一种先进先出的数据结构，和Stack一样，他也有链表和数组两种实现，理解了Stack的实现后，Queue的实现就比较简单了。
Queue
| 名称 | 描述 |
|---|---|
| Stack<T>() | 创建一个空的队列 |
| void Enqueue(T s) | 往队列中添加一个新的元素 |
| T Dequeue() | 移除队列中最早添加的元素 |
| boolean IsEmpty() | 队列是否为空 |
| int Size() | 队列中元素的个数 |
队列的操作
Queue示意
队列主要有两种操作：从队尾添加元素，从对头删除元素。添加元素称为入队，删除元素称为出队。如图：
Queue Operations
队列的创建
队列的创建有两种形式：基于数组结构实现（顺序队列）、基于链表结构实现（链式队列）。
代码实现：
入栈时，和在普通的链表中添加结点的操作是一样的；出队时，出的永远都是head结点。
package com.pingkeke.rdf.sample;
/**
* 通过链表的形式来创建队列，这样的话，队列在扩充时会比较方便。队列在出队时，从头结点head开始.
*/
public class Queue01 {
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
public Node head;
public Node curent;
/**
* 链表中添加结点
* @param data
*/
public void add(int data) {
if (head == null) {
head = new Node(data);
curent = head;
} else {
curent.next = new Node(data);
curent = curent.next;
}
}
/**
* 出队操作
* @return
* @throws Exception
*/
public int pop() throws Exception {
if (head == null) {
throw new Exception("队列为空");
}
Node node = head; // node结点就是我们要出队的结点
head = head.next; // 出队之后，head指针向下移
return node.data;
}
public static void main(String[] args) throws Exception {
Queue01 queue = new Queue01();
// 入队操作
for (int i = 0; i < 5; i++) {
queue.add(i);
}
//出队操作
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
/**
* 运行结果:
* 0
1
2
*/
}
}
使用数组实现队列
package com.pingkeke.rdf.sample;
/**
* 使用数组实现队列.
*/
public class Queue03 {
public static void main(String[] args) throws Exception {
ArrayQueue queue = new ArrayQueue(3);
System.out.println(queue.isEmpty());
for (int i = 0; i < 3; i++) {
queue.insert(i);
}
System.out.println(queue.isFull());
while (!queue.isEmpty()) {
System.out.println(queue.remove());
}
/**
* 运行结果:
* false
true
0
1
2
*
*/
}
}
class ArrayQueue {
private int[] arrInt; // 内置数组
private int front; // 头指针
private int rear; // 尾指针
public ArrayQueue(int size) {
this.arrInt = new int[size];
front = 0;
rear = -1;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty() {
return front == arrInt.length;
}
/**
* 判断队列是否已满
* @return
*/
public boolean isFull() {
return arrInt.length - 1 == rear;
}
/**
* 向队列的队尾插入一个元素
* @param item
*/
public void insert(int item) {
if (isFull()) {
throw new RuntimeException("队列已满");
}
arrInt[++rear] = item;
}
/**
* 获得队头元素
* @return
*/
public int peekFront() {
return arrInt[front];
}
/**
* 获得队尾元素
* @return
*/
public int peekRear() {
return arrInt[rear];
}
/**
* 从队列的对头移除一个元素
* @return
*/
public int remove() {
if (isEmpty()) {
throw new RuntimeException("队列为空");
}
return arrInt[front++];
}
}
两个栈实现一个队列
思路： 栈1用于存储元素，栈2用于弹出元素，负负得正。
说的通俗一点，现在把数据1、2、3分别入栈一，然后从栈一中出来（3、2、1），放到栈二中，那么，从栈二中出来的数据（1、2、3）就符合队列的规律了，即负负得正。
完整版代码实现：
package com.pingkeke.rdf.sample;
import java.util.Stack;
/**
* 两个栈实现一个队列.
*/
public class Queue02 {
private Stack<Integer> stack1 = new Stack<>(); // 执行入队操作的栈
private Stack<Integer> stack2 = new Stack<>(); // 执行出队操作的栈
/**
* 给队列增加一个入队的操作
* @param data
*/
public void push(int data) {
stack1.push(data);
}
/**
* 给队列增加一个出队的操作
* @return
* @throws Exception
*/
public int pop() throws Exception {
/**
* stack1中的数据放到stack2之前，先要保证stack2里面是空的
* （要么一开始就是空的，要么是stack2中的数据出完了），
* 不然出队的顺序会乱的，这一点很容易忘
*/
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop()); // 把stack1中的数据出栈，放到stack2中
}
}
/**
* stack2为空时，有两种可能：
* 1、一开始，两个栈的数据都是空的；
* 2、stack2中的数据出完了
*/
if (stack2.empty()) {
throw new Exception("队列为空");
}
return stack2.pop();
}
public static void main(String[] args) throws Exception {
Queue02 queue = new Queue02();
queue.push(1);
queue.push(2);
queue.push(3);
System.out.println(queue.pop());
queue.push(4);
System.out.println(queue.pop());
System.out.println(queue.pop());
System.out.println(queue.pop());
/**
* 运行结果:
* 1
2
3
4
*/
}
}
