第 3 章 · 栈与队列

栈（LIFO，一端操作）与队列（FIFO，两端操作）都是受限线性表。

3.1 栈：后进先出

栈顶是唯一的活动端。两种实现：

// 顺序栈：数组 + 栈顶下标
typedef struct { int data[1000]; int top; } Stack;
void push(Stack *s, int v) { if (s->top < 1000) s->data[s->top++] = v; }
int  pop(Stack *s)  { return s->top > 0 ? s->data[--s->top] : -1; }

// 链式栈：复用链表头插，天然 O(1)
typedef struct Node { int val; struct Node *next; } Node;
Node *push(Node *top, int v) {
    Node *n = malloc(sizeof(*n));
    if (!n) return top;
    n->val = v; n->next = top; return n;
}
Node *pop(Node *top) {
    if (!top) return NULL;
    Node *t = top; top = top->next; free(t); return top;
}

3.2 队列：先进先出

队尾进、队头出。顺序实现若头删后数组前移是 O(n)，用循环队列把下标绕回来，头尾操作都 O(1)。

#define CAP 1000
typedef struct { int data[CAP]; int front, rear; } Queue;
// front 指向队头元素，rear 指向队尾下一空位；(rear+1)%CAP == front 视为满，牺牲一格
void enq(Queue *q, int v) {
    if ((q->rear + 1) % CAP == q->front) return;   // 满
    q->data[q->rear] = v; q->rear = (q->rear + 1) % CAP;
}
int deq(Queue *q) {
    if (q->front == q->rear) return -1;            // 空
    int v = q->data[q->front]; q->front = (q->front + 1) % CAP; return v;
}

3.3 双端队列（deque）

两端都能进能出。顺序实现同上，链式用双向链表。它兼有栈和队列的能力，是滑动窗口最值问题的常客。

3.4 应用

括号匹配：遇左括号入栈，遇右括号弹栈比对。

int match(char *s) {
    char st[1000]; int top = 0;
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') st[top++] = c;
        else {
            if (top == 0) return 0;
            char o = st[--top];
            if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
                return 0;
        }
    }
    return top == 0;
}

逆波兰（后缀）表达式：中缀 3 + 4 * 2 转后缀 3 4 2 * +，数字入栈、运算符弹两个算完压回，天然无括号、无优先级问题。

对比：栈「同一端进出」回放最近，用于 DFS/函数调用/撤销；队列「一端进一端出」回放最早，用于 BFS/缓冲/消息队列。

对比：顺序需预设容量（或扩容）但无指针开销；链式按需分配无上限，但每节点多一个指针。