线性结构：队列
项目地址：https://gitee.com/caochenlei/data-structures
第一章 顺序队列介绍
在现实世界中存在很多队列的实例。例如，在电影院的售票窗口排队等待买票的人，就是通过队列这种数据结构组织在一起的。人们按先来后到的顺序排成一队，最先买到票的人就是最先来的人。当某人买完票，他就会从队列的最前端离开，这就相当于删除操作。而添加的操作却仅能在队列的尾部进行，因此新来的人就只能排在队列的最后。此外，还有像公共汽车站人们排队等车、医院中病人排队候诊等都是现实生活中队列的例子。
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，进行插入操作的端称为队尾，进行删除操作的端称为队头。故队列又称为先进先出（FIFO—first in first out）线性表。
顺序队列是队列的顺序存储结构，通常采用一维数组进行存储，其中连续的存储单元依次存放队列中的元素。同时使用两个指针分别表示数组中存放的第一个元素和最后一个元素的位置。其中，指向第一个元素的指针被称为队头指针front，指向最后一个元素的位置的指针被称为队尾指针rear。
在实际编程过程中，通常设队头指针指向队列的第一个元素，队尾指针指向队尾元素的后一个位置，front和rear的初值在队列初始化时均应置为0；入队时将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一个位置。
顺序队列中的溢出现象：
（1） "下溢"现象：当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2）"真上溢"现象：当队列满时，做入队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3）"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于一维数组的规模时，也可能由于尾指针已超越一维数组的上界而不能做入队操作，该现象称为"假上溢"现象。
第二章 顺序队列实现
2.1、实现代码
public class SequentialQueue<E> {
private int front; //指向队头元素，默认为0
private int rear; //指向队尾元素，默认为0
private E[] elements; //存放队列元素，默认为null
private int maxSize; //队列最大容量，默认为0
public SequentialQueue(int capacity) {
maxSize = capacity;
elements = (E[]) new Object[capacity];
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//判断队列是否已满
public boolean isFull() {
return rear == maxSize;
}
//获取队列元素个数
public int size() {
return rear - front;
}
//入队列
public void enqueue(E element) {
//判断队列是否已满
if (isFull()) {
System.out.println("队列已满，插入失败：" + element);
return;
}
//入队列后队尾后移
elements[rear++] = element;
}
//出队列
public E dequeue() {
//判断队列是否为空
if (isEmpty()) {
System.out.println("队列已空，获取失败");
return null;
}
//出队列后对头后移
return elements[front++];
}
@Override
public String toString() {
//获取队列有效元素
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = front; i < rear; i++) {
sb.append(" " + elements[i] + " ");
}
sb.append("]");
//返回队列详细信息
return "SequentialQueue{" +
"front=" + front +
", rear=" + rear +
", elements=" + sb.toString() +
", eleSize=" + size() +
", maxSize=" + maxSize +
", isEmpty=" + isEmpty() +
", isFull=" + isFull() +
'}';
}
}
2.2、测试代码
public class SequentialQueueTest {
public static void main(String[] args) {
SequentialQueue<String> queue = new SequentialQueue<>(4);
System.out.println("==========第一块输出内容：开始==========");
System.out.println(queue);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
queue.enqueue("D");
System.out.println(queue);
System.out.println("==========第一块输出内容：结束==========");
System.out.println();
System.out.println("==========第二块输出内容：开始==========");
System.out.println(queue);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue);
System.out.println("==========第二块输出内容：结束==========");
System.out.println();
System.out.println("==========第三块输出内容：开始==========");
System.out.println(queue);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
queue.enqueue("D");
System.out.println(queue);
System.out.println("==========第三块输出内容：结束==========");
System.out.println();
}
}
==========第一块输出内容：开始==========
SequentialQueue{front=0, rear=0, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=false}
SequentialQueue{front=0, rear=4, elements=[ A B C D ], eleSize=4, maxSize=4, isEmpty=false, isFull=true}
==========第一块输出内容：结束==========
==========第二块输出内容：开始==========
SequentialQueue{front=0, rear=4, elements=[ A B C D ], eleSize=4, maxSize=4, isEmpty=false, isFull=true}
A
B
C
D
SequentialQueue{front=4, rear=4, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=true}
==========第二块输出内容：结束==========
==========第三块输出内容：开始==========
SequentialQueue{front=4, rear=4, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=true}
队列已满，插入失败：A
队列已满，插入失败：B
队列已满，插入失败：C
队列已满，插入失败：D
SequentialQueue{front=4, rear=4, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=true}
==========第三块输出内容：结束==========
第三章 循环队列介绍
在顺序队列中，入队操作就是先将尾指针rear后移一个单元(rear++)，然后将元素值赋给rear单元(elements[rear++] = element)。出队时．则是头指针front后移(front++)。像这样进行了一定数量入队和出队操作后，可能会出现这样的情况：尾指针rear已指到数组的最后一个元素，此时若再执行入队操作，便会出现队满“溢出”。然而由于在此之前可能也执行了若干次出队操作，因而数组的前面部分可能还有很多闲置的元素空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为“假溢出”。显然必须要解决这一个溢出的问题，否则顺序队列就没有太多使用价值。
循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止“假溢出”的发生，但队列大小是固定的。
在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front == rear，而队列判满的条件是((rear + 1) % maxSize) == front。
第四章 循环队列实现
4.1、实现代码
public class CircularQueue<E> {
private int front; //指向队头元素，默认为0
private int rear; //指向队尾元素，默认为0
private E[] elements; //存放队列元素，默认为null
private int maxSize; //队列最大容量，默认为0
public CircularQueue(int capacity) {
maxSize = capacity + 1; //有一个没用的元素，所以这里加一
elements = (E[]) new Object[capacity + 1]; //有一个没用的元素，所以这里加一
}
//判断队列是否为空
public boolean isEmpty() {
return front == rear;
}
//判断队列是否已满
public boolean isFull() {
return ((rear + 1) % maxSize) == front;
}
//获取队列元素个数
public int size() {
return (rear - front + maxSize) % maxSize;
}
//入队列
public void enqueue(E element) {
//判断队列是否已满
if (isFull()) {
System.out.println("队列已满，插入失败：" + element);
return;
}
//入队列
elements[rear] = element;
//向后移
rear = (rear + 1) % maxSize;
}
//出队列
public E dequeue() {
//判断队列是否为空
if (isEmpty()) {
System.out.println("队列已空，获取失败");
return null;
}
//出队列
E element = elements[front];
//向后移
front = (front + 1) % maxSize;
return element;
}
@Override
public String toString() {
//获取队列有效元素
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = front; i < front + size(); i++) {
sb.append(" " + elements[i % maxSize] + " ");
}
sb.append("]");
//返回队列详细信息
return "SequentialQueue{" +
"front=" + front +
", rear=" + rear +
", elements=" + sb.toString() +
", eleSize=" + size() +
", maxSize=" + (maxSize - 1) + //有一个没用的元素，所以这里减一
", isEmpty=" + isEmpty() +
", isFull=" + isFull() +
'}';
}
}
4.2、测试代码
public class CircularQueueTest {
public static void main(String[] args) {
CircularQueue<String> queue = new CircularQueue<>(4);
System.out.println("==========第一块输出内容：开始==========");
System.out.println(queue);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
queue.enqueue("D");
System.out.println(queue);
System.out.println("==========第一块输出内容：结束==========");
System.out.println();
System.out.println("==========第二块输出内容：开始==========");
System.out.println(queue);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue);
System.out.println("==========第二块输出内容：结束==========");
System.out.println();
System.out.println("==========第三块输出内容：开始==========");
System.out.println(queue);
queue.enqueue("A");
queue.enqueue("B");
queue.enqueue("C");
queue.enqueue("D");
System.out.println(queue);
System.out.println("==========第三块输出内容：结束==========");
System.out.println();
}
}
==========第一块输出内容：开始==========
SequentialQueue{front=0, rear=0, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=false}
SequentialQueue{front=0, rear=4, elements=[ A B C D ], eleSize=4, maxSize=4, isEmpty=false, isFull=true}
==========第一块输出内容：结束==========
==========第二块输出内容：开始==========
SequentialQueue{front=0, rear=4, elements=[ A B C D ], eleSize=4, maxSize=4, isEmpty=false, isFull=true}
A
B
C
D
SequentialQueue{front=4, rear=4, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=false}
==========第二块输出内容：结束==========
==========第三块输出内容：开始==========
SequentialQueue{front=4, rear=4, elements=[], eleSize=0, maxSize=4, isEmpty=true, isFull=false}
SequentialQueue{front=4, rear=3, elements=[ A B C D ], eleSize=4, maxSize=4, isEmpty=false, isFull=true}
==========第三块输出内容：结束==========
上一篇： 队列的基本运算
下一篇： 数据结构 顺序队列 循环队列 基本操作