信息学奥赛数据结构入门：栈、队列与链表 C++ 实现

想象你往桌子上叠盘子：每次只能从顶上放新盘子（push），也只能从顶上拿盘子（pop）。最后放上去的盘子最先被拿下来——这就是栈（Stack），先进后出（LIFO）。

用数组模拟一个栈：

int stack[1005];
int top = 0;   // 栈顶指针，指向下一个空位

void push(int x) {
    stack[top++] = x;
}

int pop() {
    return stack[--top];
}

bool isEmpty() {
    return top == 0;
}

top 是栈顶指针。push 时把 x 放到 stack[top]，然后 top 加 1；pop 时先把 top 减 1，再返回 stack[top]。整个栈就两个操作，非常简单。

经典题：给一个只包含 `(`、`)`、`[`、`]`、`{`、`}` 的字符串，判断括号是否匹配。比如 `()` 匹配，`([)]` 不匹配。

思路：从左到右扫描字符串。遇到左括号就 push 进栈；遇到右括号，看栈顶是不是对应的左括号——是就 pop，不是就说明不匹配。扫描完之后栈必须为空。

#include <stack>
#include <string>
#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    stack<char> st;
    bool ok = true;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) { ok = false; break; }
            char top = st.top();
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{')) {
                st.pop();
            } else { ok = false; break; }
        }
    }
    if (ok && st.empty()) cout << "YES";
    else cout << "NO";
    return 0;
}

这是栈最经典的应用。括号匹配、表达式求值、递归调用的函数栈，底层都是同一个结构。

排队买票时，先来的人先买到票，后来的人排在队尾。这就是队列（Queue），先进先出（FIFO）。

用数组模拟一个队列，需要两个指针：head 指向队首，tail 指向队尾的下一个空位。

int q[1005];
int head = 0, tail = 0;

void push(int x) {
    q[tail++] = x;
}

int pop() {
    return q[head++];
}

bool isEmpty() {
    return head == tail;
}

入队 push 往 tail 方向加，出队 pop 从 head 方向拿。head 永远跟着 tail 往前走。这种简单实现有个问题：数组越用越短，前面的空间浪费了。竞赛里可以用循环队列解决，入门阶段先用简单版即可。

队列最经典的应用是 BFS（广度优先搜索）。想象你在一个迷宫里，要找从起点到终点的最短路径。BFS 的思路是：从起点开始，一圈一圈往外扩散，先访问离起点 1 步的所有格子，再访问 2 步的，直到撞到终点。

#include <queue>
using namespace std;

queue<pair<int,int>> q;
int dist[105][105];
bool visited[105][105];

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int sx, int sy) {
    q.push({sx, sy});
    visited[sx][sy] = true;
    dist[sx][sy] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

这里 `queue<pair<int,int>>` 就是一个存坐标的队列。每次从队首拿出一个格子，把它四周没访问过的邻居放进队尾。先放进去的先处理，保证按距离扩散。