队列
先进先出的线性表

#include <iostream>
using namespace std;
const int MAXN = 6;
int q[MAXN];
int head = 0, tail = 0;          // 有效区间是 [head, tail) 左闭右开

void push(int x) {
    if (tail == MAXN) { cout << "队满（假溢出）！" << endl; return; }
    q[tail++] = x;               // 入队：放到 tail 位置，tail 后移
}
void pop() {
    if (head == tail) { cout << "队空！" << endl; return; }
    head++;                      // 出队：head 后移（tail 不动！）
}
int main() {
    push(1); push(2); push(3); push(4);
    pop(); pop();                // 1、2 出队，前面空出 2 个位置
    push(5); push(6);            // tail 移到 6
    push(7);                     // 明明只存了 4 个数，却说队满
    return 0;
}

#include <iostream>
using namespace std;
const int MAXN = 1005;
int q[MAXN], head = 0, tail = 0;   // head 指向队头，tail 指向下一个可插入位置

bool empty() { return head == tail; }                    // 判空
bool full()  { return (tail + 1) % MAXN == head; }       // 判满（浪费一个单元）
int  size()  { return (tail - head + MAXN) % MAXN; }     // 元素个数
int  front() { return q[head]; }                         // 取队头

void push(int x) {                                       // 入队
    if (full()) { cout << "Queue Full!\n"; return; }
    q[tail] = x;
    tail = (tail + 1) % MAXN;                            // 取模回绕
}
void pop() {                                             // 出队
    if (empty()) { cout << "Queue Empty!\n"; return; }
    head = (head + 1) % MAXN;                            // 取模回绕
}

int main() {
    push(10); push(20); push(30);
    cout << front() << endl;   // 10
    pop();
    cout << front() << endl;   // 20
    push(40);
    cout << size() << endl;    // 3
    while (!empty()) { cout << front() << " "; pop(); }
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
int main() {
    queue<int> q;
    q.push(10); q.push(20); q.push(30);          // 从队尾入队
    cout << q.front() << " " << q.back() << endl; // 队头 10，队尾 30
    q.pop();                                      // 队头出队（不返回值！）
    cout << q.front() << " " << q.size() << endl; // 20 2
    while (!q.empty()) {                          // 遍历队列的唯一方式：边取边弹
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1005;
vector<int> g[N];      // 邻接表存图
bool vis[N];
int dist[N];

// 队列驱动的 BFS 通用框架
void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();       // 1. 取队头并出队
        for (int v : g[u]) {              // 2. 扩展 u 的所有邻点
            if (vis[v]) continue;         //    访问过的跳过，保证每个点只入队一次
            vis[v] = true;
            dist[v] = dist[u] + 1;        //    层数 = 上一层 + 1
            q.push(v);                    // 3. 新节点从队尾入队
        }
    }
}

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    queue<int> q;
    for (int i = 1; i <= n; i++) q.push(i);   // 1~n 依次入队
    while (q.size() > 1) {                    // 只剩 1 人时结束
        for (int i = 1; i < m; i++) {         // 前 m-1 个人：出队后立刻从队尾重新入队
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << " ";             // 第 m 个人出圈（出队后不再入队）
        q.pop();
    }
    cout << endl << q.front() << endl;        // 换行后输出最后剩下的人
    return 0;
}

#include <iostream>
#include <queue>
using namespace std;
const int MAXW = 1005;
bool inCache[MAXW];                       // inCache[x]：单词 x 是否在内存中
int main() {
    int m, n, x, ans = 0;
    cin >> m >> n;                        // m：内存容量，n：文章单词数
    queue<int> q;                         // 内存中的单词，按进入顺序排队
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (inCache[x]) continue;         // 已在内存，直接查，不查词典
        ans++;                            // 需要查词典
        if ((int)q.size() == m) {         // 内存已满：淘汰最早进入的（队头）
            inCache[q.front()] = false;
            q.pop();
        }
        q.push(x);                        // 新单词从队尾进入
        inCache[x] = true;
    }
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <deque>
#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main() {
    deque<int> dq;                                         // 双端队列：两端都能进出
    dq.push_back(1); dq.push_front(2);
    dq.pop_front(); dq.pop_back();
    cout << dq.size() << endl;                             // 0

priority_queue<int> pq;                                // 优先队列（大根堆），每次取最大
    pq.push(3); pq.push(1); pq.push(5);
    cout << pq.top() << endl;                              // 5（不是 3！）

priority_queue<int, vector<int>, greater<int> > pq2;   // 小根堆
    pq2.push(3); pq2.push(1); pq2.push(5);
    cout << pq2.top() << endl;                             // 1
    return 0;
}