引言
队列（queue）是一种线性的数据结构，和栈一样是一种运算受限制的线性表。其限制只允许从表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。一般允许进行插入的一端我们称为队尾，允许删除的一端称为队首。队列的插入操作又叫入队，队列的删除操作又叫出队。
可以把队列想象成购物时排队结账的时候的队伍，先排队的人会先结账，后排队的人会后结账，并且不允许有插队的行为，只能在队伍的末尾进行排队。这就是队列的特点，具有先进先出（FIFO——First In First Out）的性质。
实现
由于队列和栈都是线性表，所以队列也同样可以用数组模拟来手动实现。但是由于队列的出队与入队在不同的两端，所以我们要引入一个循环队列的概念。
如果单纯地用数组进行模拟，那么当有元素出队的时候，我们有两种办法处理剩余的元素：第一种是保持队首（front）位置不变，其余所有的元素顺序往前移动一位；第二种是让队首（front）向后移动一位，其余每个元素的位置不变，也就是使现在的位置成为新的队首位置。
第一种方法需要移动队列的所有元素，时间效率非常低，第二种只需要移动队头则变得非常简单，但第二种会导致之前队头所在的位置以后不会再被用到，造成空间的浪费。循环队列就解决了这个问题。
在实际使用队列中，为了使队列的空间能重复使用，一旦队列的头（front）或者尾（rear）超出了所分配的队列空间，则让它指向队列的起始位置，从 MaxSize-1 增加 1 变成 0
当元素装满整个队列之后就会造成溢出，所以如果要手动实现队列的话，最好提前预估队列的最大容量。
手动实现队列：
#define maxsize 10000
class queue {
int q[maxsize];
int front, rear, count;
queue() {
front = 0;
rear = 0;
count = 0;
}
void push(int x) {
count++;
if (count == maxsize) {
// 溢出
}
q[rear] = x;
rear = (rear + 1) % maxsize;
}
int pop() {
count--;
front = (front + 1) % maxsize;
return q[front];
}
int front_val() {
return q[front];
}
bool empty() {
if (count == 0) {
return true;
}
return false;
}
};
STL 中的队列
在日常使用中，往往不需要手动实现队列，在 C++ 中有已经写好的队列，供我们使用。下面是使用 C++ 队列的示例代码。
#include <queue>
#include <iostream>
using namespace std;
int main() {
queue<int> q; // 声明一个装 int 类型数据的队列
q.push(1); // 入队
q.push(2);
q.push(3);
cout << q.size() << endl; // 输出队列元素个数
while (!q.empty()) { // 判断队列是否为空
cout << q.front() << endl; // 访问队首元素
q.pop(); // 出队
}
return 0;
}
总结
| 方法 | 功能 |
|---|---|
| push | 入队 |
| pop | 出队 |
| front | 访问队首元素 |
| size | 大小 |
| empty | 是否为空 |
京公网安备 11010502036488号