队列与栈

📒 第五部分：栈和队列

---

第17讲：栈（Stack）⭐

🔑 知识点讲解

栈：后进先出（LIFO, Last In First Out）

操作：
    push(x)  -> 入栈
    pop()    -> 出栈
    top()    -> 查看栈顶
    isEmpty() -> 判空

实现方式：
    1. 数组实现（顺序栈）
    2. 链表实现（链栈）

应用场景：
    - 括号匹配
    - 表达式求值（中缀→后缀）⭐
    - 递归的模拟
    - 浏览器前进后退
    - DFS深度优先搜索

数组实现

#include <stdio.h>
#define MAXSIZE 1000

typedef struct {
    int data[MAXSIZE];
    int top;  // 栈顶指针，-1表示空栈
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAXSIZE - 1;
}

int push(Stack *s, int val) {
    if (isFull(s)) return 0;
    s->data[++(s->top)] = val;
    return 1;
}

int pop(Stack *s, int *val) {
    if (isEmpty(s)) return 0;
    *val = s->data[(s->top)--];
    return 1;
}

int top(Stack *s) {
    if (isEmpty(s)) return -1;
    return s->data[s->top];
}

✏️ 练习11：括号匹配

题目：判断一个字符串中的括号 (), [], {} 是否匹配。

输入：{[()]} 输出：匹配
输入：{[(])} 输出：不匹配

#include <stdio.h>
#include <string.h>

#define MAXSIZE 1000

typedef struct {
    char data[MAXSIZE];
    int top;
} CharStack;

void init(CharStack *s) { s->top = -1; }
int isEmpty(CharStack *s) { return s->top == -1; }
void push(CharStack *s, char c) { s->data[++(s->top)] = c; }
char pop_val(CharStack *s) { return s->data[(s->top)--]; }

int isMatch(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

int checkBrackets(char *s) {
    CharStack stack;
    init(&stack);
    
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            push(&stack, c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (isEmpty(&stack)) return 0;
            char top = pop_val(&stack);
            if (!isMatch(top, c)) return 0;
        }
    }
    return isEmpty(&stack);
}

int main() {
    char s[200];
    scanf("%s", s);
    printf("%s\n", checkBrackets(s) ? "匹配" : "不匹配");
    return 0;
}

---

第18讲：队列（Queue）⭐

🔑 知识点讲解

队列：先进先出（FIFO, First In First Out）

操作：
    enqueue(x) -> 入队（队尾）
    dequeue()  -> 出队（队头）
    front()    -> 查看队头
    isEmpty()  -> 判空

实现方式：
    1. 数组实现（顺序队列）-> 容易"假溢出"
    2. 循环队列 -> 解决假溢出
    3. 链队列

循环队列关键公式：
    队尾指针前进：rear = (rear + 1) % MAXSIZE
    队头指针前进：front = (front + 1) % MAXSIZE
    判空：front == rear
    判满：(rear + 1) % MAXSIZE == front  （牺牲一个空间）
    元素个数：(rear - front + MAXSIZE) % MAXSIZE

应用场景：
    - BFS广度优先搜索
    - 操作系统任务调度
    - 缓冲区

循环队列实现

#include <stdio.h>
#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

int isEmpty(Queue *q) {
    return q->front == q->rear;
}

int isFull(Queue *q) {
    return (q->rear + 1) % MAXSIZE == q->front;
}

int enqueue(Queue *q, int val) {
    if (isFull(q)) return 0;
    q->data[q->rear] = val;
    q->rear = (q->rear + 1) % MAXSIZE;
    return 1;
}

int dequeue(Queue *q, int *val) {
    if (isEmpty(q)) return 0;
    *val = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return 1;
}

int size(Queue *q) {
    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
}

✏️ 练习12：用两个栈实现队列

题目：用两个栈模拟队列的入队和出队操作。

#include <stdio.h>
#define MAXSIZE 1000

typedef struct {
    int data[MAXSIZE];
    int top;
} Stack;

void init(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, int x) { s->data[++(s->top)] = x; }
int pop(Stack *s) { return s->data[(s->top)--]; }

typedef struct {
    Stack s1;  // 用于入队
    Stack s2;  // 用于出队
} MyQueue;

void initQueue(MyQueue *q) {
    init(&q->s1);
    init(&q->s2);
}

void enqueue(MyQueue *q, int x) {
    push(&q->s1, x);
}

int dequeue(MyQueue *q) {
    if (isEmpty(&q->s2)) {
        // 将 s1 的全部倒入 s2
        while (!isEmpty(&q->s1)) {
            push(&q->s2, pop(&q->s1));
        }
    }
    if (isEmpty(&q->s2)) return -1;  // 队列为空
    return pop(&q->s2);
}

int main() {
    MyQueue q;
    initQueue(&q);
    
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    
    printf("%d\n", dequeue(&q));  // 1
    printf("%d\n", dequeue(&q));  // 2
    
    enqueue(&q, 4);
    printf("%d\n", dequeue(&q));  // 3
    printf("%d\n", dequeue(&q));  // 4
    
    return 0;
}