队列基础概念
队列是一种访问受限的线性表,只允许在一端插入(队尾),另一端删除(队头)。遵循先进先出 (FIFO) 原则。
队列的手动模拟实现
使用数组模拟队列时,我们需要维护两个指针:h 指向队头元素的前一个位置,t 指向队尾元素的位置。这种左开右闭 [h, t] 的设计能简化边界判断,实际开发中只要逻辑自洽即可。
初始化
const int N = 1e6 + 10;
int h, t; // 队头指针,队尾指针
int q[N]; // 队列数组
入队操作
从下标为 1 的位置开始存储有效元素,避免 0 索引带来的歧义。
void push(int x) {
q[++t] = x;
}
时间复杂度 O(1)。
出队操作
只需移动队头指针,无需真正删除数据。
void pop() {
h++;
}
时间复杂度 O(1)。
获取队头与队尾
注意队头元素实际位于 h + 1 处,因为 h 标记的是前驱位置。
int front() { return q[h + 1]; }
int back() { return q[t]; }
判空与大小
bool empty() { return t == h; }
int size { t - h; }


