队列理论基础
# 队列定义
同样也是操作受限的线性表,底层也是基于数组实现,但顺序是先进先出FIFO,从队尾进队,从队头出队
队列分为:
- 顺序队列
- 循环队列
- 链式队列
- 双端队列
# 顺序队列
顺序队列的特征:
- 队头指针指向第一个元素
- 队尾指针一般指向最后一个元素的下一个位置
进队:先送值到队尾,再将队尾指针+1
Q.data[Q.rear] = x;
rear ++;
出队:先取出队头元素,再将队头指针+1
x = Q.data[Q.front]
front ++;
顺序队列存在的问题 :会导致上溢出;是一种 假溢出 ,在data数组中任然存在可以存放数组的位置
解决方法:
- 建立一个足够大的存储空间以避免溢出,但这样做空间使用率低,浪费存储空间
- 移动元素:每当出队一个元素,就将移动队列中所有的已有元素向队头移动一个位置
- 循环队列:将队头和队尾看作是一个首尾相接的循环队列
# 循环队列
循环队列可以弥补顺序队列的缺点,其定义是:
- 队列长度固定,即队列容量有限
- 队列的头尾相接形成一个环,当队尾到达数组的最后一个位置时,下一个位置是数组的第一个位置
具体实现步骤如下:
- 定义一个数组和两个指针:front 和 rear,分别表示队头和队尾的位置。初始时,队头和队尾都指向数组的第一个位置,即 front = rear = 0。
- 入队时,首先检查队列是否已满,即 rear+1 是否等于 front。如果满了则返回错误,否则将元素添加到队尾,即 data[rear] = element,然后将 rear 指针向后移动一位,即 rear = (rear + 1) % capacity。
- 出队时,首先检查队列是否为空,即 front 是否等于 rear。如果为空则返回错误,否则将队头元素取出并返回,即 element = data[front],然后将 front 指针向后移动一位,即 front = (front + 1) % capacity。
- 在队列的任何时刻,队列中的元素数量为 (rear - front + capacity) % capacity。
- 如何判断队列满?牺牲一个单元来区分队空和队满:(rear + 1) % maxsize = front
以下是一个基于数组实现循环队列的 Java 代码示例:
public class CircularQueue {
private int[] data;
private int front, rear;
private int capacity;
public CircularQueue(int k) {
capacity = k;
data = new int[capacity];
front = 0;
rear = 0;
}
public boolean enqueue(int element) {
if (isFull()) {
return false;
} else {
data[rear] = element;
rear = (rear + 1) % capacity;
return true;
}
}
public boolean dequeue() {
if (isEmpty()) {
return false;
} else {
front = (front + 1) % capacity;
return true;
}
}
public int front() {
if (isEmpty()) {
return -1;
} else {
return data[front];
}
}
public int rear() {
if (isEmpty()) {
return -1;
} else {
return data[(rear - 1 + capacity) % capacity];
}
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % capacity == front;
}
}
简单总结就是:
- 初始/队空:Q.front = Q.rear (队空条件)
- 出队:Q.front = (Q.front+1) % maxsize (最大元素个数)
- 进队:Q.rear = (Q.rear+1) % maxsize
- 队列长度 = (Q.rear - Q.front + maxsize) % maxsize
- 队满:( 牺牲一个单元来区分队空和队满 )(Q.rear + 1) % maxsize = Q.front
# 链式队列
实际就是一个同时带有头指针和尾指针的单链表
头指针指向队头结点,尾指针指向队尾结点(即单链表最后一个结点,与顺序存储有所不同)
适合于数据元素变动较大的情况,而且不存在队列满或者溢出的问题。
- 队空: Q.rear == Q.front == NULL
- 出队:(带头结点)
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next; //插入头节点之后
if(Q.rear = p) //若原队列中只有一个结点,删除后变空,还需修改尾指针
Q.rear = Q.front;
free(p);
- 进队:(带头节点)
LinkNode *s = (LinkNode *) malloc (sizeof(LinkNode)); //创建新结点
s->data = x; s->next = NULL;
Q.rear->next = s; //插入到表尾
Q.rear = s;
# 双端队列
允许两端都进行入队和出队操作的队列
- 输出受限:有一端允许插入和删除;另一端只允许插入
- 输入受限:有一端允许插入和删除;另一端只允许删除
# 队列的应用
- 层次遍历
- 计算机系统中的应用
- 解决主机与外部设备之间速度不匹配的问题(ex:打印机数据缓冲区中所存储的数据就是一个队列)
- 解决由多用户引起的资源竞争问题(CPU将请求按时间先后排成队列)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/06/09, 10:54:03