3.队列(Queue) ——————本质为："线性表"
队列是一种运算受限制的线性表，元素的插入（入队）在表的一端(表尾, rear)进行，删除（出对）则在另一端(表头, front)进行。
允许插入的一端称为表尾(rear)，允许删除的一端称为表头(front)
队列的主要操作：
① 初始化
② 入队：插入
③ 出队：删除
④ 获取队头 —— 不删除元素
⑤ 求长度：队列元素个数
⑥ 判空
⑦ 正序遍历
⑧ 销毁
表示形式：
㈠逻辑结构:
q = (a1, a2, ... , an), a1为队头元素，an为队尾元素
┌───┬───┬───┬───┬───┐
出队<—— │a1 │a2 │a3 │...│an │ <——入队
└───┴───┴───┴───┴───┘
↑ ↑
队头 队尾
特点：'先进先出(FIFO, first in first out)',因此又被称之先进先出的线性表
㈡'物理存储结构'
(1) 顺序存储结构：顺序队列
其实质为：线性表的顺序表
顺序队列用一维数组实现，还需设置两个指针 front 和 rear 分别指示队列的队头元素和队尾元素的'下一个位置'。
注意：其实这里，将队头指针front指向队列元素的前一个空的位置处，而rear指针指向队列最后一个元素的位置处，也是可行的。
注意：
1.这种单向的顺序队列极易造成假溢出(即队列中明明还有存储单元，就是不能插入新的元素)
解决办法：
(1) 每次出队一个元素后，将整个队列元素均向队头方向移动一个单元，即始终保证整个队的队头指示器始终在数组的第一个存储单元处。时间复杂度：O(n)
(2) 将顺序队列的存储结构改造成头尾相连(只是表现在逻辑上的)的圆环，当队尾指示器rear到达数组的上限(数组最大下标处)时, 如果还有数据元素需要入队且数组的第 0 个存储单元空闲时，就可以让rear指向数组的0存储位置。同理，对头front指示器达到数组的上限(数组最大下标处)时,若果还有元素要出队时，就将front指向数组的0端。这样，就可以将队列中空闲的空间利用上。
方法分析：第一种解决方法会造成系统额外的开销，不是最佳解决办法。故采用第二种方法。
- 在循环队列中，判断队列是空还是满是个需要重点考虑的问题。单纯的依靠 front==rear并不能判断队列空间是空还满(因为空或满时，均有这个关系)。
解决办法：
(1)设定一个辅助标识位：flag，初始为0,当入队一个元素就加1，出队一个元素就减1。最后结合flag是否为大于零的数和front==rear来判断当前循环队列是满的还是空
(2)第二种方式就是，在循环队列中少用一个存储单元。因此，rear和front只相差一个位置。但是请注意：由于是循环结构，所以这个差1,有可能是相差整整一圈，因此，队满的条件：(rear + 1) % queueArray.length == front
方法分析：第一种解决办法要多设定一个参数，还要一直对这个参数执行运算，这样会增加一部分系统开销。因此，采用第二中解决办法。
顺序循环队列为"空"的条件：front == rear == 0
为"满"的条件：(rear + 1) % queueArray.length == front
队列的长度：(rear - front + queueArray.length) % queueArray.length
注意：取模的目的是为了整合rear和front大小为一个问题
'代码描述'（顺序循环结构队列）：
public class sequenceQueue<T> {
private final int maxSize = 10; //默认是队列容量
private T queueArray[]; //实现队列的数组
private int front; //队头指示器
private rear; //队尾指示器,指向队尾元素的下一个位置（始终保持所指的位置是空内容，即未被利用的那个存储单元）
/**
* 顺序队列初始化
*/
//采用默认容量初始化顺序队列
public sequenceQueue() {
front = rear = 0;
queueArray = (T[])new Object[maxSize];
}
//采用指定容量初始化顺序队列
public sequenceQueue(int n) {
front = rear = 0;
queueArray = (T[])new Object[n];
}
/**
* 入队操作：插入
*/
public void enQueue(T obj) {
//队列是否已满,若满了则需要扩容
if ((rear + 1) % queueArray.length == front) {
//扩容
T[] p = (T[])new Object[queueArray.length * 2];
//复制原数组中的数据至新的数组中
//表明rear指示器现在数组的末尾处，front指示器在数组的0下标处
if (rear == ((T[])queueArray).length - 1) {
for (int i = 1; i <= rear; i++) {
p[i] = queueArray[i];
}
}else {
/**
* 表明rear指示器在数组的其他位置处，则将队列分为两部分：
* (1) front位置到数组末尾
* (2) 0存储单元到rear指针器处
* 因此,得分段复制
*/
int i, j = 1;
// 复制front到末尾这段的数据
for (i = front + 1; i < queueArray.length; i++, j++) {
p[j] = queueArray[i];
}
// 复制从0存储单元到rear指示器处的数据
// 注意：这里将queueArray[0]位置的数据(为0)也复制到新的数组中，表明
// 新数组的扔是以0存储单元作为"判满"的辅助单位
for (i = 0; i < rear; i++, j++) {
p[j] = queueArray[i];
}
front = 0; // 将front调整到数组头部位置
rear = queueArray.length - 1; //将rear调整到数组中含有数据的尾部的位置
}
queueArray = p;
}
/**
* 执行插入数据的过程,
* 若将rear指向队尾元素的下一个位置时，front在队头元素处
* rear = (rear + 1) % queueArray.length;
* queueArray[rear] = obj; //因为rear指针在队尾元素的下一个位置处，因此先放元素，再移动指针
*/
//这个表示rear指向队尾的元素，注意和上面这段代码的区别
//取模是为了防止rear指针越界，
rear = (rear + 1) % queueArray.length; //因为rear指针在队尾元素处，因此先移动rear指针，再放元素
queueArray[rear] = obj;
}
//出队操作：删除
public T deQueue() {
//判空
if (isEmpty()) {
System.out.println("顺序队列为空，不能进行出队操作");
return null;
}
/**
* 进行出队的操作过程
* 由于：front在队头元素的前一个位置处，所以，插入数据时，要先移动指针，后放数据
*/
front = (front + 1) % queueArray.length; //front指针取模也是为了front防止越界
return queueArray[front];
}
//获取操作：返回队头的元素，不删除该元素
public T getTop() {
//判空
if (isEmpty()) {
System.out.println("顺序队列为空，不能进行获取队头元素的操作");
return null;
}
return queueArray[(front + 1) % queueArray.length];
}
//求长度
public int size() {
return (rear - front + queueArray.length) % queueArray.length;
}
//判空
public boolean isEmpty() {
return front == rear;
}
//正向遍历
public void nextOrder() {
System.out.print("[");
int j = front;
for (int i = 1; i <= size(); i++) {
j = (j + 1) % queueArray.length;
if (j == rear) {
System.out.print(queueArray[j]);
}else {
System.out.print(queueArray[j] + ", ");
}
}
System.out.println("]");
}
//销毁
public void clear() {
front = rear = 0;
}
}
(2) 链式存储结构：链队列
用链表实现的队列称为链队列,
其实质是：线性表的单链表（只是在'头删尾插'而已）
注意：
1.链队列的长度是不固定的，因此不存在假溢出的问题，故用一般的(非循环)队列即可。
2.同线性表的单链表一样，为了操作方便，在链队列中添加一个头结点，并令头指针(front)指向头结点。(在链栈中没有使用头结点)
链队列为'空'的条件(front和rear均指向头结点)：front.next == null
'代码描述'(链队列):
public class LinkQueue<T> {
private Node<T> front, rear; //这里的Node和前面的链表的Node是一样的
private int length; //记录队列元素的个数
//1.初始化链队列
public LinkQueue() {
length = 0;
front = rear = new Node<T>(null); //初始时，front和rear均指向表头结点
}
//2.入队：插入（不用考虑队满的情况，也就没有扩容的现象）
public void enQueue(T obj) {
rear.next = new Node<T>(obj, null);
rear = rear.next; //将rear指针移动到新的队尾结点处。
length ++; //增加一个元素个数
}
//3.出队：删除(删除的是头结点的后继结点，即第一个结点)
public T deQueue() {
//判空
if (isEmpty()) {
System.out.println("链队列为空，不可以进行出栈操作");
return null;
}
//出栈过程
Node<T> p = front.next; //辅助结点
front.next= p.next; //由于表头（头结点）的"位置"固定不动，因此，只能变动第一个结点。
length --;
/**
* 这部分是不是多余呢？不是多余的，当队列中只有一个结点时，出队后，此时队列为空了。
* 就要将rear指针指向头结点，即front的位置处
*/
if (front.next == null) {
front = rear;
}
return p.data;
}
//4.获取：返回队头元素
public T getHead() {
//判空
if (isEmpty()) {
System.out.println("链队列为空，不可以进行获取队头元素的操作");
return null;
}
//获取队头元素的过程
return front.next.data;
}
//5.求长度
public int size() {
return length;
}
//6. 判空
public boolean isEmpty() {
return front.next == null;
}
//7.正向遍历
public void nextOrder() {
System.out.print("[");
Node<T> p = front.next;
while (p != null) {
if (p.next == null) {
System.out.print(p.data);
}else {
System.out.print(p.data + ", ");
}
p = p.next;
}
System.out.println("]");
}
//8.销毁
public void clear() {
length = 0;
front.next = rear.next = null;
}
}
循环队列和链队列的比较：
它们的基本操作都是：O(1)
循环队列长：度固定，所以会存在浪费空间的情况。但是，在频繁出入队的时候，不需要申
请、释放结点，因此，空间开销少点
链队列：长度灵活可变，但会频繁的申请、释放结点，造成一顶的系统开销
总结：长度确定时，用循环链表
长度不可测时，选择链队列
典型应用：键盘输入各种字符的过程
网友评论