看看你对队列的了解有多少？
队列(Queue) 简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。在队列中把插入数据元素的一端称为队尾(Rear)，删除数据元素的一端称为队头(Front )。向队尾插人元素称为进队或入队，新元素人队后成为新的队尾元素; 从队列中删除元素称为离队或出队，元素出队后，其后续元素成为新的队头元素。
由于队列的插入和删除操作分别在队尾和队头进行，每个元素必然按照进人的次序离队，也就是说先进队的元素必然先离队，所以称队列为先进先出表(First In First Out,FIFO)。队列结构与日常生活中在食堂排队打饭等候服务的模型是一致的，最早进入队列的人最早得到服务并从队头离开; 最后到来的人只能排在队列的最后，最后得到服务并最后离开。如图3.17所示，1是队头，6是队尾，取出数据只能从队头取出，存人数据只能在队尾中进入。
1.2顺序队列
利用顺序存储方式实现的队列称为顺序队列，顺序队列实际上是运算受限的顺序表。它是利用一组地址连续的存储单元存放队列中的元素。由于队列中的插人和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队首元素和队尾元素。
设顺序队列Q 的容量为6,其队头指针为front,队尾指针为rear,头、尾指针和队列中元素之间的关系如图3.18 所示。
1.入队操作思想
根据顺序队列的存储特点，要使某一元素进入队列，则要进行如下操作:
(1)先判断队列是否已经装满元素，如果未装满才能进行人队操作，否则不操作。
(2)将要入队的元素放人队尾，队尾指针再自增。
【例3.6】1200101班已有2名同学王丽、张阳的报到信息存放在队列中，现有(120010131，郑克龙) 同学来报到，请将其信息放入队列中。
首先要定义学生信息类来存放学生记录，具体参见上一章的class Student定义。
接下来放入对应结点的过程如下:
入队前如图3.19 所示。
将要入队的元素(120010131，郑克龙)放入队尾，队尾指针再自增，如图3.20所示 。
2.入队操作代码实现
入队首先判断队尾指针是否越界（队列的最大存储空间），在未越界的情况下，将新元素放入队列，并移后队尾指针，具体实现代码如下：
import com.t.Student;
public class SeqQueue {
int default_size = 8;// 保存数组的长度
int capacity;// 定义一个数组用于保存顺序队列的元素
Student[] data;// 保存顺序队列中元素的当前个数
int front = 0;
int rear = 0;
// 以默认数组的长度创建空顺序队列
public SeqQueue() {
capacity = default_size;
data = new Student[capacity];
}
// 获取顺序队列的实际大小
public int length() {
return rear - front;
}
// 插入队列
public void add(Student stu) {
if (rear < capacity) {
data[rear] = stu;
System.out.println("入栈:" + data[rear].no + "" + data[rear].name);
}
}
public static void main(String[] args) {
Student stu1 = new Student();
stu1.no = "120010103";
stu1.name = "张阳";
Student stu2 = new Student();
stu2.no = "120010102";
stu2.name = "王丽";
Student stu3 = new Student();
stu3.no = "120010131";
stu3.name = "郑克龙";
SeqQueue sq = new SeqQueue();
sq.add(stu1);
sq.add(stu2);
sq.add(stu3);
}
}3.出队操作思想
根据顺序队列的存储特点，要使某一元素移出队列，则要进行如下操作:
(1) 先判断队列是否为空，如果不为空才能进行出队操作，否则不操作。
(2)将队头的元素取出，再使队头指针自增。
【例3.7】1200101班已有3 名同学王丽、张阳、郑克龙的报到信息存放在队列内，现需要从队列中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息类来存放学生记录，具体参见上一章的class Student 定义。
接下来取出对应结点的过程如下:
出队前如图3.21所示。
将队头的元素(120010103,张阳)取出，再使队头指针自增，如图3.22 所示。
4.出队操作代码实现
出队首先判断队列是否为空，在队列非空的情况下，将队头元素取出，并后移队头指针。在入队程序的基础上，添加出队代码，具体实现代码如下：
import com.t.Student;
public class SeqQueue {
int default_size = 8;// 保存数组的长度
int capacity;// 定义一个数组用于保存顺序队列的元素
Student[] data;// 保存顺序队列中元素的当前个数
int front = 0;
int rear = 0;
// 以默认数组的长度创建空顺序队列
public SeqQueue() {
capacity = default_size;
data = new Student[capacity];
}
// 获取顺序队列的实际大小
public int length() {
return rear - front;
}
// 插入队列
public void add(Student stu) {
if (rear < capacity) {
data[rear] = stu;
System.out.println("入栈:" + data[rear].no + "" + data[rear].name);
rear++;
}
}
//移除队列
public Student remove(){
Student old =null;
if(front<rear){
old =data[front];//保留队列的rear端元素的值
data[front]=null;//释放队列的rear端的值
front++;
System.out.println("出栈:" + old.no + "" + old.name);
}
return old;
}
public static void main(String[] args) {
Student stu1 = new Student();
stu1.no = "120010103";
stu1.name = "张阳";
Student stu2 = new Student();
stu2.no = "120010102";
stu2.name = "王丽";
Student stu3 = new Student();
stu3.no = "120010131";
stu3.name = "郑克龙";
SeqQueue sq = new SeqQueue();
sq.add(stu1);
sq.add(stu2);
sq.add(stu3);
//出栈
while(sq.front<sq.rear){
sq.remove();
}
}
}1.3循环队列
在顺序队列中，为了降低运算的复杂度，元素入队时，只需要修改队尾指针，元素出队时只需要修改队头指针。由于顺序队列的空间是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限值时，就不能只通过修改队尾指针来实现新元素的入队操作。此时就会出现如下问题：
设数组空间为M，如图3.23所示，则：
当front=0，rear=M-1时，再有元素入队发生溢出--真溢出。
当front ！=0，rear=M-1时，再有元素入队发生溢出--假溢出。
解决假溢出的办法有两种：一是队首固定，每次出队剩余元素向下移动，这样时间效率比较低；二是使用循环队列。
在顺序队列的基础上，我们将数组的最后一个元素的下一个元素从逻辑上认为是数组的第一个元素，这样的形成逻辑上的环，如图3.24所示。
循环队列存在一个问题，就是如何判定循环队列空和满的问题。
表3.1列出了两种方法解决循环队列空和满的判定比较：
在图3.25 中用队首指针front 指向队首元素所在的单元，用队尾指针rear 指向队尾元素所在单元的后一个单元。如此在图3.25 (b)所示的循环队列中，队首元素为e0, 队尾元素为e3。 当e4、e5、e6、e7 相继进入队列后，如图3.25(c) 所示，队列空间被占满，此时队尾指针追上队首指针，有rear = front。反之，如果从图3.25 (b)所示的状态开始，e0、e1、e2、e3 相继出队，则得到空队列，如图3.25 (a)所示，此时队首指针追上队尾指针，所以也有front =rear。可见仅凭front 与rear 是否相等无法判断队列的状态是“空”还是“满”。解决这个问题可以有两种处理方法: 一种方法是少使用一个存储空间，当队尾指针的下一个单元就是队首指针所指单元时，则停止入队。这样队尾指针就不会追上队首指针，所以在队列满时就不会有front = rear。这样一来，队列满的条件就变为 ( rear+1 )%M = front, 而队列判空的条件不变，仍然为front = rear。另外一种方法是增设一个标志，以区别队列是“空”还是“满”，例如增设size 变量表明队列中数据元素的个数，如果size = Max 则队列满。
1.4链式队列
队列的链式存储可以使用单链表来实现。为了操作方便，这里采用带头结点的单链表结构。根据单链表的特点，选择链表的头部作为队首，链表的尾部作为队尾。除了链表头结点需要通过一个引用来指向之外，还需要一个对链表尾结点的引用，以方便队列的入队操作的实现。为此一共设置两个指针，一个队首指针和一个队尾指针，如图3.26 所示。队首指针指向队首元素的前一个结点，即始终指向链表的头结点，队尾指针指向队列当前队尾元素所在的结点。当队列为空时，队首指针与队尾指针均指向空的头结点。
链队列的结点定义与链栈的结点定义相同，参见上一节链栈Node 结点类定义。
链队列的基本操作也有进队、出队操作。
1.进队列操作思想
将某一个新结点s 排入队列内，则要进行如下操作:
(1) 将队尾rear 的后继设为新结点S。
(2) 将队尾指针rear 后移，即rear= rear.next。
【例3.8】 1200101班已有2名同学王丽、张阳的报到信息排在队列里，现有(120010131，郑克龙）同学来报到，请将其信息也排入队列中。
首先要定义学生信息类和结点类，具体参见上一章class Student 和class Node 的定义。
接下来将对应结点排入队列的过程如下:
入队列前如图3.27所示。
生成新结点（120010131，郑克龙），将队尾rear的后继设为新结点，如图3.28所示。
将队尾指针rear重新指向新节点（120010131，郑克龙）即可，如图3.29所示。
2.进队列操作代码实现
根据进队列操作思想，代码实现如下：
import com.t.Node;
import com.t.Student;
public class LinkQueue { // 链队列
Node front;// 链队头指针
Node rear;// 链队尾指针
int curlen;// 实际队长
public LinkQueue() {
front = new Node();
rear = front;
curlen = 0;
}
// 数据元素node入队
public void enQueue(Node node) {
rear.next = node;
rear = rear.next;
System.out.println("入队:" + rear.stu.no + "" + rear.stu.name);
curlen++;
}
public static void main(String[] args) {
LinkQueue lq = new LinkQueue();
Node node1 = new Node();
node1.stu = new Student();
node1.stu.no = "120010103";
node1.stu.name = "张阳";
Node node2 = new Node();
node2.stu = new Student();
node2.stu.no = "120010102";
node2.stu.name = "王丽";
Node node3 = new Node();
node3.stu = new Student();
node3.stu.no = "120010131";
node3.stu.name = "郑克龙";
lq.enQueue(node1);
lq.enQueue(node2);
lq.enQueue(node3);
}
}3.出队列操作思想
在队列内有元素的情况下，对于带头结点的链式队列出队是头结点后的队首元素出队，具体操作如下;
(1) 保存头结点后的队首元素。
(2) 设置头结点的后继元素为队首元素的后继元素，即front.next=front.next.next。
【例3.9】 11200101班已有3 名同学王丽、张阳、郑克龙的报到信息排入队列内，现需要从链队列中取出一位同学的信息进行审查，并显示取出的信息。
首先要定义学生信息类和结点类,具体参见上一章class Student 和class Node的定义。
接下来取出对应结点的过程如下:
出队前学生信息队列状态，如图3.30所示：
将队首出队元素存入ni变量中，再去除队首元素，如图3.31所示。
4.出队列操作代码实现
根据出队列思想，在队列入队程序的基础上，添加出队代码，实现出队功能，具体代码实现如下：
import com.t.Node;
import com.t.Student;
public class LinkQueue { // 链队列
Node front;// 链队头指针
Node rear;// 链队尾指针
int curlen;// 实际队长
public LinkQueue() {
front = new Node();
rear = front;
curlen = 0;
}
// 数据元素node入队
public void enQueue(Node node) {
rear.next = node;
rear = rear.next;
System.out.println("入队:" + rear.stu.no + "" + rear.stu.name);
curlen++;
}
//队首元素出队
public Node deQueue(){
Node ni= null;
if(curlen>0){
ni=front.next;
front.next=ni.next;
curlen--;
System.out.println("出队:" + ni.stu.no + "" + ni.stu.name);
}
return ni;
}
public static void main(String[] args) {
LinkQueue lq = new LinkQueue();
Node node1 = new Node();
node1.stu = new Student();
node1.stu.no = "120010103";
node1.stu.name = "张阳";
Node node2 = new Node();
node2.stu = new Student();
node2.stu.no = "120010102";
node2.stu.name = "王丽";
Node node3 = new Node();
node3.stu = new Student();
node3.stu.no = "120010131";
node3.stu.name = "郑克龙";
lq.enQueue(node1);
lq.enQueue(node2);
lq.enQueue(node3);
//出队
while(lq.curlen>0){
lq.deQueue();
}
}
}本章小结
本章主要介绍了运算受限的线性表: 栈和队列，并讨论了它们的相关概念和基本操作、存储结构、基本运算的实现以及一些应用实例。通过本章的学习，应掌握的重点内容包括如下几点:
( 1 ) 栈是限制在表的一端进行插入和删除的线性表，具有“先进后出”的特点，随着结点的进栈和出栈，用栈顶指针指示栈顶的变化。用顺序存储结构时，要注意栈满、栈空的条件; 用链式存储结构时，要注意链的方向。
( 2 ) 递归是指在定义自身的同时又出现了对自身的引用。如果一个算法直接或间接地调用自己，则称这个算法是一个递归算法。计算机执行递归算法时，是通过栈来实现的。
( 3 ) 队列的插入运算在表的一端进行，而删除运算在表的另一端进行，具有“先进先出”的特点，分别用队头指针和队尾指针指示队列队头结点和队尾结点的变化。队列的操作主要讲解了结点的插入、删除运算的算法及其溢出的条件。在顺序队列结构中，当结点不断插入、删除时，会很快移到队列末端而造成“假溢出”，用循环队列可以很好地防止“假溢出”，最后还讲解了链式队列及其操作。
( 4 ) 栈和队列的运算: 入栈、出栈、入队列、出队列，还介绍了栈和队列在不同存储方式下基本运算的实现方法及实例应用。
腾讯云开发者
