跳到主要内容

栈与队列

栈​

栈是只允许在一端进行插入和删除操作的线性表。

  • 栈顶：允许插入和删除的一端。
  • 栈底：另一端，即不允许插入和删除的一端。
  • 特点：后进先出 Last In First Out (LIFO) 。

卡特兰数 Cn=1n+1C2nnC_n = \frac{1}{n+1}C_{2n}^{n} ，可以用来计算 nn 个元素的出栈顺序有多少种。

顺序栈​

定义及初始化​

#define MAX_SIZE 10
typedef struct {
    Element data[MAX_SIZE];
    int top;    // 栈顶指针
} SeqStack;
void initStack(SeqStack &stack) {
    stack.top = -1; // 约定栈空时，top = -1
}

入栈​

bool push(SeqStack &stack, Element e) {
    if (stack.top == MAX_SIZE - 1) return false; // 栈满
    stack.top += 1;
    stack.data[stack.top] = e;
    return true;
}

出栈​

bool pop(SeqStack &stack, Element &e) {
    if (stack.top == -1) return false; // 栈空
    e = stack.data[stack.top];
    stack.top -= 1;
    return true;
}

获取栈顶元素​

bool getTop(SeqStack stack, Element &e) {
    if (stack.top == -1) return false; // 栈空
    e = stack.data[stack.top];
    return true;
}

共享栈​

定义及初始化​

#define MAX_SIZE 10
typedef struct {
    Element data[MAX_SIZE];
    int top1;   // 栈一栈顶指针
    int top2;   // 栈二栈顶指针
} ShareStack;
void initStack(ShareStack &stack) {
    stack.top1 = -1;
    stack.top2 = MAX_SIZE;
}

链栈​

可以使用单链表实现链栈，表头作为栈顶。

队列​

队列是只允许在一端进行插入，在另一端进行删除的线性表。

  • 队头：允许删除的一端。
  • 队尾：允许插入的一端。
  • 特点：先进先出 First In First Out (FIFO) 。

顺序队列​

顺序队列也称循环队列，它利用两个指针表示队头和队尾。

队尾应当始终指向队列中最后一个元素的下一个位置，这样可以区分队空和队满的情况。

如果要求队尾指针必须指向最后一个元素，则可以：

  • 加个长度变量来区分队空和队满；
  • 加个符号位表示队列的方向，正向表示最近一次操作是入队，反向表示最近一次操作是出队。

定义及初始化​

#define MAX_SIZE 10
typedef struct {
    Element data[MAX_SIZE];
    int front, rear;   // 队头 & 队尾指针
} SeqQueue;
void initQueue(SeqQueue &q) {
    q.front = q.rear = 0;
}
  • 判空：q.front == q.rear
  • 判满：(q.rear + 1) % MAX_SIZE == q.front

获取队头元素​

bool getFront(SeqQueue q, Element &e) {
    if (q.front == q.rear) return false; // 队空
    e = q.data[q.front];
    return true;
}

入队​

bool push(SeqQueue &q, Element e) {
    if ((q.rear + 1) % MAX_SIZE == q.front) return false; // 队满
    q.data[q.rear] = e;
    q.rear = (q.rear + 1) % MAX_SIZE;
    return true;
}

出队​

bool pop(SeqQueue &q, Element &e) {
    if (q.front == q.rear) return false; // 队空
    e = q.data[q.front];
    q.front = (q.front + 1) % MAX_SIZE;
    return true;
}

链队列​

可以使用单链表实现链队列，表头作为队头，表尾作为队尾。

定义及初始化​

typedef struct Node {
    Element data;
    struct Node *next;
} Node;

typedef struct {
    Node *front, *rear;   // 队头 & 队尾指针
} LinkQueue;
// 不带头结点
void initQueue(LinkQueue &q) {
    q.front = q.rear = NULL;
}

// 带头结点
void initQueue(LinkQueue &q) {
    q.front = q.rear = (Node *)malloc(sizeof(Node));
    q.front->next = NULL;
}

入队​

// 带头结点
bool push(LinkQueue &q, Element e) {
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = NULL;
    q.rear = q.rear->next = s; // 先连接，再移动
    return true;
}

// 不带头结点
bool push(LinkQueue &q, Element e) {
    Node *s = (Node *)malloc(sizeof(Node));
    s->data = e;
    s->next = NULL;
    if (q.front == NULL) {
        q.front = q.rear = s;
    } else {
        q.rear = q.rear->next = s;
    }
    return true;
}

出队​

// 带头结点
bool pop(LinkQueue &q, Element &e) {
    if (q.front == q.rear) return false; // 队空
    Node *p = q.front->next;
    e = p->data;
    q.front->next = p->next;
    if (q.rear == p) q.rear = q.front; // 队列中只有一个元素
    free(p);
    return true;
}

// 不带头结点
bool pop(LinkQueue &q, Element &e) {
    if (q.front == NULL) return false; // 队空
    Node *p = q.front;
    e = p->data;
    q.front = p->next;
    if (q.rear == p) q.rear = NULL; // 队列中只有一个元素
    free(p);
    return true;
}

双端队列​

双端队列（deque）是一种允许在两端进行插入和删除的队列。

  • 输入受限的双端队列：只允许从一端插入。
  • 输出受限的双端队列：只允许从一端删除。

应用​

括号匹配​

bool match(char *str) {
    LinkStack s;
    initStack(s);
    for (int i = 0; str[i] != '\0'; i += 1) {
        if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
            push(s, str[i]);
        } else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
            if (isEmpty(s)) return false;
            char top;
            pop(s, top);
            if (str[i] == ')' && top != '(') return false;
            if (str[i] == ']' && top != '[') return false;
            if (str[i] == '}' && top != '{') return false;
        }
    }
    return isEmpty(s);
}

中缀、后缀、前缀表达式​

表达式有三种元素构成，操作数、运算符、界限符（括号）。

  • 中缀：运算符放在两操作数之间，如：a+b-c。
  • 后缀：运算符放在两操作数之后，如：ab+c-。
  • 前缀：运算符放在两操作数之前，如：-+abc。

其中，前缀和后缀表达式不需要界限符。

计算前后缀表达式​

  1. 创建一个栈。
  2. 逐个扫描后缀表达式的元素。
    • 前缀表达式：从右向左扫描；
    • 后缀表达式：从左向右扫描。
  3. 如果是操作数，将其压入栈中。
  4. 如果是运算符，从栈中弹出两个操作数，进行运算，将运算结果压入栈中。
  5. 扫描结束后，栈中的元素即为运算结果。

中缀转后缀​

  1. 创建一个栈，并用一个表记录后缀表达式。
  2. 从左到右逐个扫描中缀表达式的元素。
  3. 如果是操作数，直接加入表中。
  4. 如果是运算符，从栈中弹出 优先级大于等于 该运算符的所有运算符，将这些运算符依次加入表中，然后将该运算符压入栈中。
  5. 如果是左括号，直接压入栈中。
  6. 如果是右括号，从栈中弹出所有运算符，直到遇到左括号，将这些运算符依次加入表中。
  7. 扫描结束后，将栈中所有运算符依次加入表中。

计算中缀表达式​

结合前两者方法，可以这样计算中缀表达式：

  1. 创建两个栈，一个用于存储操作数，一个用于存储运算符。
  2. 从左到右逐个扫描中缀表达式的元素。
  3. 如果是操作数，直接压入操作数栈中。
  4. 如果是非操作数，则与 "中缀转后缀" 逻辑相同。中间若有操作符弹出时，从操作数栈中弹出两个操作数，进行运算，将运算结果压入操作数栈中。
  5. 扫描结束后，操作数栈中的元素即为运算结果。

其他应用​

一般递归都可以用栈来实现，比如：

  • 函数的调用栈；
  • 斐波那契数列（递归优化的经典例子）；

队列的一些应用：

  • 树、图的遍历；
  • 操作系统的进程调度（先来先服务）；
  • 打印机的工作队列；