⇧
❮
❯
↻
🍀计算机基础🍀 6291字 32分钟

数据结构强化笔记（3）：栈与队列

作者

本文介绍栈与队列。关于栈与队列在树、图中的应用详见各自篇章。

本系列博文为便于考研复习，特别规定了栈与队列的正常配置（相对应地还存在若干非正常配置），日常解算法题或其他自行应用场景中用简单数组实现各类栈与队列时无需严格遵守正常配置，可自由发挥，只需满足基本定义与性质即可。常见的简单数组定义方式如下：

int stk[N], tt = -1;    // 栈，tt为栈顶指针
int q[N], hh = 0, tt = -1;  // 非循环队列，hh为队头指针，tt为队尾指针
Hyplus目录

1 栈

栈（Stack）：只允许在⼀端进⾏插⼊/删除操作的输⼊输出受限的线性表。允许进⾏插⼊/删除的⼀端称为栈顶（Top），不允许进⾏操作的⼀端称为栈底（Bottom）。不含任何元素的栈称为空栈。

栈的特性 ——先进后出（First In Last Out, FILO），因此栈具有记忆功能

ADT Stack {
    数据对象: a_i
    数据关系: <a_{i-1}, a_i>, 只允许在⼀端增加、减少
    基本操作:
        initStack(&S)   // 初始化⼀个空栈S
        isEmpty(S)  // 判空操作，判断⼀个栈是否为空
        push(&S, x) // 压栈操作，若栈未满，则将元素x押⼊栈中
        pop(&S, &x) // 出栈操作，若栈⾮空，则弹出栈顶元素并⽤x接收
        getTop(&S, &x)  // 读取栈顶元素，若栈⾮空，⽤x返回栈顶元素
        destroyStack(&S)    // 销毁操作
} ADT Stack

1.1 栈的存储结构

分为顺序栈和链栈，其中顺序栈还包含一种重要衍生扩展结构——共享栈。

1.1.1 顺序栈

顺序栈（Sequential Stack）：栈最常见的一种存储结构之一，利⽤⼀组连续地址的存储单元⾃栈底⾄栈顶存储元素，并使⽤栈顶指针top指示当前栈顶元素的位置。正常配置下，初始化top = -1。

#define MAXSIZE 110

typedef struct SqStack {
    ElemType data[MAXSIZE];
    int top;    // 栈顶指针，通常配置下初值为-1
} SqStack;

状态表示（正常配置）：

  • 栈空/初始化状态：S.top == -1
  • 栈满状态：S.top == MAXSIZE - 1
  • 栈长：S.top + 1

基本操作（正常配置）：

  • 压栈：S.data[++S.top] = x;
  • 出栈：x = S.data[S.top--];
  • 读取栈顶元素：x = S.data[S.top];

变式：当栈顶指针top初始化为0或MAXSIZE时，可由上推算出各种状态表示与基本操作

1.1.2 共享栈

共享栈（Shared Stack）：栈的⼀种特殊的顺序存储结构。利⽤栈底位置相对不变的特性，让两个顺序栈共享⼀个⼀维数组空间，两栈栈底分别位于数组两端，并分别设置1号栈、2号栈的栈顶指针top1、top2，相向而行。正常配置下，初始化top1 = -1、top2 = MAXSIZE。

优点：节省存储空间，减少引起上溢的可能（对于下溢则不变）

typedef struct SharedStack {
    ElemType data[MAXSIZE];
    int top1, top2; // top1、top2分别为1、2号栈的栈顶指针。亦可⽤数组top[2]实现
} SharedStack;

状态表示（正常配置）：

  • 1号栈空/初始化状态：S.top1 == -1
  • 1号栈长：S.top1 + 1
  • 2号栈空/初始化状态：S.top2 == MAXSIZE
  • 2号栈长：MAXSIZE - S.top2
  • 共享栈满状态：S.top1 + 1 == S.top2

1.1.3 链栈

链栈（Linked Stack）：栈的⼀种链式存储结构。采⽤带有头指针的单链表实现。规定所有操作都在链表的表头进⾏，头指针即为栈顶指针。实际相当于只允许头插、头删的单链表。

优点：便于多个栈共享存储空间；提⾼其操作效率；且不存在栈满⾃溢的情况。

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

1.2 栈的性质

栈的实用性质：

  1. 出栈元素排列数：n个不同元素进栈，出栈元素不同排列的个数为卡特兰数：
\begin{aligned}
\text{Catalan}(n)=\dfrac{\text{C}^{n}_{2n}}{n+1}
\end{aligned}
  1. 由出栈序列判断容量相关问题：画图动态模拟即可，注意题设中可能的限制条件（如连续⼊栈/出栈次数上限等）
  2. 由升序⼊栈序列判断出栈元素相关问题：已知⼊栈序列为1,2,\cdots,n，出栈序列为p_1,p_2,\cdots,p_n，则
    1. 题型1——最后进栈的元素n最先出栈：若p_1=n，则p_i=n-i+1

      【证】最后进栈的元素最先出栈 \Rightarrow 在其之前无人出栈 \therefore p_2=n-1,p_3=n-2,\cdots,p_i=n-i+1

    2. 题型2——推算最后进栈的元素n出栈后其与之后出栈元素⼤⼩关系：若p_i=n\ (1\lt i \lt n)，则p_i,p_{i+1},\cdots,p_n的大小关系为p_i\gt p_{i+1} \gt \cdots \gt p_n，即最后进栈元素出栈后出栈降序

      【证】由题知，⼊栈升序，且n进栈后不可能出现进栈操作。⼜根据上⼀题的结论可得，n出栈后元素出栈降序。

口诀：若1、2、3，则无3、1、2！

实际解题时强烈推荐多⽤特值法（其他数值计算题同理）

1.3 栈的应⽤

在DFS中的实际应用见后述。

根据运算方向，表达式可分为3种类型：前缀（Prefix，波兰式，+ab）、中缀（Infix，a+b）、后缀（Postfix，逆波兰式，ab+）

所使用的辅助栈包括操作数（Operand）栈、运算符（Operator）栈、结果栈

在本节的第一子节开始前，预定义以下辅助函数（较为简单，实际作答时可不详细给出）：

/* 返回运算符优先级：运算优先级越⾼，返回值越⼤ */
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return -1;
}

/* ⼦表达式求值（仅有理运算）：通过res传回结果，函数返回值表示计算成功与否 */
bool calSub(double x, char op, double y, double &res) {
    if (op == '+') {
        res = x + y;
    } else if (op == '-') {
        res = x - y;
    } else if (op == '*') {
        res = x * y;
    } else if (op == '/') {
        if (fabs(y) < EPS) return false;    // EPS为预定义的宏常量，可为1e-6
        res = x / y;
    } else {
        return false;
    }
    return true;
}

/* 出栈做运算：取操作数栈s1栈顶两数，进行运算符栈s2栈顶运算符的运算；无法运算则报错 */
bool calStackTopTwo(double s1[], int top1, char s2[], int top2) {
    double x, y, res;
    char op;
    bool flag = false;  // 标志成功（1）或失败（0）
    y = s1[top1--]; // 右操作数先出栈
    x = s1[top1--]; // 左操作数后出栈
    op = s2[top2--];

    flag = calSub(x, op, y, res);
    if (!flag) std::cout << "ERROR" << std::endl;   // puts("ERROR");
    else s1[++top1] = res;
    return flag;
}

1.3.1 表达式的转换

根据实际情况，通常使用两种转换方法：

  1. ⼿⼯求解法（括号法）：
    • 中缀转后缀/前缀：对中缀式中所有⼦表达式按运算优先级添加括号，从⾥到外将所有运算符提到对应的括号前/后，即将中缀式转化成前/后缀式，最后去除所有括号即可。
      • 【例1】中缀转后缀：(a+b)*c+d-(e+g)*h → ((a+b)*c)+d-((e+g)*h) → (((a+b)*c)+d)-((e+g)*h) → ((((a+b)*c)+d)-((e+g)*h)) → ((((ab)+c)*d)+((eg)+h)*)- → ab+c*d+eg+h*-（若转前缀只需将运算符提至括号前即可，结果为-+*+abcd*+egh）
    • 后缀转中缀/前缀：逆转换的核心操作为从左至右扫连续2个操作数及1个运算符，还原原样（操作符放至两数之间/之前）并给该子表达式添加括号，反复操作，最后去除多余括号即可。
      • 【例2】后缀转中缀：ab+c*d+eg+h*- → (a+b)*c*d+eg+h*- → ((a+b)*c)d+eg+h*- → (((a+b)*c)+d)eg+h*- → (((a+b)*c)+d)((e+g)h*)- → (((a+b)*c)+d)((e+g)*h)- → ((((a+b)*c)+d)-((e+g)*h)) → ((a+b)*c)+d-(e+g)*h（若转前缀只需将运算符放至两数之前即可，最后括号全去，结果为-+*+abcd*+egh）
  2. 堆栈求解法：使⽤辅助运算符栈和结果栈

中缀转后缀（最为常用）：从左⾄右遍历中缀表达式串

  1. 遇到操作数：直接输出
  2. 遇到左括号：直接⼊栈
  3. 遇到运算符
    1. 栈空、栈顶为左括号：直接⼊栈
    2. 栈顶为运算符：【⽐较】当前运算符与栈顶运算符的优先级——当前运算符的优先级更⼤则⼊栈，否则弹出并输出栈顶运算符，并继续【⽐较】下⼀个栈顶运算符，指针i不后移
      • 原理：⾼优先级的先算（输出）
  4. 遇到右括号：顺序弹出并输出栈顶运算符直⾄栈顶为左括号，然后弹出栈顶左括号
  5. 遍历结束后，运算符栈顺序弹出并输出剩余栈顶运算符；将结果栈中元素顺序弹出即为后缀式
/* 中缀式转后缀式 */
void infixToPostfix(char infix[], Stack &res) {
    Stack S;    // 运算符栈
    initStack(S);
    for (int i = 0; infix[i] != '\0';) {
        if ('0' <= infix[i] && infix[i] <= '9') {
            res.data[++res.top] = infix[i];
        } else if (infix[i] == '(') {
            S.data[++S.top] = '(';
        } else if (infix[i] == ')') {
            while (S.data[S.top] != '(') {
                res.data[++res.top] = S.data[S.top--];
            }
            S.top--;
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            if (S.top == -1 || S.data[S.top] == '(' || getPriority(infix[i]) > getPriority(S.data[S.top])) {
                S.data[++S.top] = infix[i];
            } else {
                res.data[++res.top] = S.data[S.top--];
                continue;   // 指针不后移
            }
        }
        i++;
    }
    while (S.top != -1) {
        res.data[++res.top] = S.data[S.top--];
    }
}

中缀转前缀：操作与中缀转后缀极为相似，但存在以下⼏点重要区别

  • 从右⾄左遍历中缀表达式串，故需知道串的⻓度
  • 左、右括号效果互换
  • 【⽐较】条件修改：当前运算符的优先级⼤于等于栈顶运算符
    • 原理：当前 > 栈顶轮换变量得栈顶 > 当前取反得栈顶 <= 当前即当前 >= 栈顶
  • 将结果栈中元素顺序弹出并进⾏逆序后才成为前缀式
/* 中缀式转前缀式，需要知道串的长度 */
void infixToPrefix(char infix[], Stack &res) {
    Stack S;    // 运算符栈
    initStack(temp);
    for (int i = strlen(infix) - 1; i >= 0;) {  // 从右至左扫描
        if ('0' <= infix[i] && infix[i] <= '9') {
            res.data[++res.top] = infix[i];
        } else if (infix[i] == ')') {   // 左、右括号判定与中缀转后缀相反
            S.data[++S.top] = ')';
        } else if (infix[i] == '(') {
            while (S.data[S.top] != ')') {
                res.data[++res.top] = S.data[S.top--];
            }
            S.top--;
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            if (S.top == -1 || S.data[S.top] == ')' || getPriority(infix[i]) >= getPriority(S.data[S.top])) {   // 比较条件修改
                S.data[++S.top] = infix[i];
            } else {
                res.data[++res.top] = S.data[S.top--];
                continue;
            }
        }
        i--;
    }
    while (S.top != -1) {
        res.data[++res.top] = S.data[S.top--];
    }
}

1.3.2 表达式的计算

手工计算表达式的方法……略

计算中缀表达式——使用使⽤辅助操作数栈与运算符栈（此处由于要进行有理运算，两栈存储的元素类型不同，故分别用不同类型的简单数组实现）：从左⾄右遍历中缀表达式串（操作及原理均与中缀转后缀极为相似）

  1. 遇到操作数：直接⼊操作数栈
  2. 遇到左括号：直接⼊运算符栈
  3. 遇到运算符
    1. （运算符栈）栈空、栈顶为左括号：直接⼊栈
    2. 栈顶为运算符：【⽐较】当前运算符与栈顶运算符的优先级——当前运算符的优先级更⼤则⼊栈，否则弹出栈顶运算符并进行【运算】：
      1. 计算⼦表达式：弹出两个（操作数栈）栈顶操作数，与操作符组合：先出的数在右、后出的数在左、运算符在中间
      2. 做完运算后的结果押回操作数栈，并让当前运算符继续【⽐较】下⼀个运算符栈顶运算符，指针i不后移
  4. 遇到右括号：顺序弹出栈顶运算符并分别执行一次上述【运算】直⾄栈顶为左括号，然后弹出栈顶左括号
  5. 遍历结束后，运算符栈顺序弹出剩余栈顶运算符并分别执行一次上述【运算】；最后操作数栈所剩的那个数即为结果
/* 计算中缀表达式 */
double calInfix(char exp[]) {
    double s1[MAXSIZE]; // 操作数栈
    char s2[MAXSIZE];   // 运算符栈
    int top1 = -1, top2 = -1;
    for (int i = 0; exp[i] != '\0';) {
        if ('0' <= exp[i] && exp[i] <= '9') {
            s1[++top1] = exp[i] - '0';
        } else if (exp[i] == '(') {
            s2[++top2] = '(';
        } else if (exp[i] == ')') {
            while (s2[top2] != '(') {
                bool flag = calStackTopTwo(s1, top1, s2, top2);
                if (!flag) return ERROR;
            }
            top2--;
        } else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/') {
            if (top2 == -1 || s2[top2] == '(' || getPriority(exp[i]) > getPriority(s2[top2])) {
                s2[++top2] = exp[i];
            } else {
                bool flag = calStackTopTwo(s1, top1, s2, top2);
                if (!flag) return ERROR;
                continue;
            }
        }
        i++;
    }
    while (top2 != -1) {
        bool flag = calStackTopTwo(s1, top1, s2, top2);
        if (!flag) return ERROR;
    }
    return s1[top1];
}

计算后缀表达式（最为常用）——只需使⽤操作数栈：从左⾄右遍历后缀表达式（极为简单）

  1. 遇到操作数：⼊栈
  2. 遇到运算符：执⾏同中缀计算所述两步【运算】；运算结果押回栈，继续遍历
  3. 遍历结束之时即运算结束之时
/* 计算后缀表达式 */
double calPostfix(char exp[]) {
    Stack S;    // 操作数栈
    initStack(S);
    for (int i = 0; exp[i] != '\0'; i++) {
        if ('0' <= exp[i] && exp[i] <= '9') {
            S.data[++S.top] = (double) (exp[i] - '0');
        } else {
            double x, y, res;
            y = S.data[S.top--];
            x = S.data[S.top--];
            bool flag = calSub(x, exp[i], y, res);  // 子表达式求值
            if (!flag) {
                puts("ERROR");
                return ERROR;
            }
            S.data[++S.top] = res;
        }
    }
    return S.data[S.top];
}

计算前缀表达式：操作与计算后缀表达式极为相似，只存在以下两点细微区别

  • 从右⾄左遍历前缀表达式串，故同样需知道串的⻓度
  • 微调【运算】操作：先出的数在左、后出的数在右
/* 计算前缀表达式，需要知道串的长度 */
double calPrefix(char exp[]) {
    Stack S;    // 操作数栈
    initStack(S);
    for (int i = strlen(exp) - 1; i >= 0; i--) {
        if ('0' <= exp[i] && exp[i] <= '9') {
            S.data[++S.top] = (double) (exp[i] - '0');
        } else {
            double x, y, res;
            x = S.data[S.top--];
            y = S.data[S.top--];
            bool flag = calSub(x, exp[i], y, res);  // 子表达式求值
            if (!flag) {
                puts("ERROR");
                return ERROR;
            }
            S.data[++S.top] = res;
        }
    }
    return S.data[S.top];
}

1.3.3 括号匹配

括号表达式的合法性判定：每⼀摞括号（某⼀对左右括号及其之间的括号）必须严格对称；⼩括号可套在⼤括号外。【例】\{[]\}[()](\{[]\})是合法的，而()[(])\}、[)\{](\}是不合法的。

括号匹配⽅法——利⽤左括号栈：遍历括号表达式

  1. 遇到左括号：⼊栈
  2. 遇到右括号：与栈顶左括号做配对⽐较——配对则弹出栈顶左括号并继续遍历，不配对则⽴刻结束遍历并返回false
  3. 遍历结束时若栈⾮空则匹配失败，否则匹配成功
/* 检查括号匹配 */
bool checkBrackets(char a[]) {
    Stack S;    // 左括号栈
    initStack(S);
    char match[128] = {0};
    match[')'] = '(', match[']'] = '[', match['}'] = '{';
    for (int i = 0; a[i] != '\0'; i++) {
        switch (a[i]) {
            case '(':
            case '[':
            case '{':
                S.data[++S.top] = a[i];
                break;
            case ')':
            case ']':
            case '}':
                if (isEmpty(S)) return false;
                if (S.data[S.top--] != match[a[i]]) return false;
                break;
        }
    }
    if (isEmpty(S)) return true;
    return false;
}

1.3.4 递归

递归（Recursion）：若某函数、过程或数据结构在其定义中调⽤了其⾃身，则称其为递归定义的。递归需要调⽤系统⼯作栈。

所有的递归都满⾜两部分：递归表达式（递归体）、递归出⼝（递归边界）

递归的特点：

  • 优点：将复杂问题分解为属性相同、操作重复的⼦问题，⼤幅减少思考需求与代码量
  • 缺点：通常时空效率不⾼，且计算量过⼤时易造成栈溢出

递归的应⽤：

  • 进制转换、迷宫求解、计算规律序列（如斐波那契数列）、DFS、DP
  • 调⽤函数时，其局部变量⼀般采⽤栈结构进⾏存储

2 队列

队列（Queue，简称队）：只允许在一端进行插入、在另一端进行删除的输入输出受限的线性表。进行插入的一端称为队尾（Rear），插入操作称为入队（Enqueue）；进行删除的一端称为队首（Front），删除操作称为出队（Dequeue）。

队列的特性——先进先出（First In First Out，FIFO）

ADT Queue {
    数据对象: a_i
    数据关系: <a_{i-1}, a_i>, 只允许在⼀端增加，在另⼀端减少
    基本操作:
        initQueue(&Q)   // 初始化⼀个空队Q
        isEmpty(Q)  // 判空操作，判断⼀个队是否为空
        push(&Q, x) // ⼊队操作，若队未满，则让元素x⼊队
        pop(&Q, &x) // 出队操作，若队⾮空，则队⾸元素出队并⽤x接收
        getFront(&Q, &x)    // 读取队⾸元素，若队⾮空，⽤x返回队⾸元素
        getRear(&Q, &x) // 读取队尾元素，若队⾮空，⽤x返回队尾元素
        destroyQueue(&Q)    // 销毁操作
} ADT Queue

2.1 队列的存储结构

其中顺序队又分为非循环队列与循环队列。

本节中的所有队列均为正常配置。

2.1.1 顺序队

顺序队（Sequetial Queue）：队列的一种顺序存储结构，利用一组连续地址的存储单元自队首至队尾存储元素，用队首指针front、队尾指针rear指示队列的首尾位置。

#define MAXSIZE 110

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

非循环队列（正常配置）：

  • 缺陷：指针无脑前进，易造成假溢出，浪费大量存储空间。
  • 状态表示
    • 初始化：Q.front = Q.rear = 0;——双指针同时指向0号位置
    • 队空：Q.front == Q.rear——双指针同时指向同一位置
    • 队满：无法明确判定
    • 队长：Q.rear - Q.front
  • 操作——先操作元素，再移动指针
    • 入队：Q.data[Q.front++] = x;
    • 出队：Q.data[Q.rear++] = x;

循环队列（正常配置）：

  • 改进：定义在逻辑上的环状队列，移动指针时对数组容量取余，有效规避了假溢出的风险。
  • 状态表示
    • 初始化：Q.front = Q.rear = 0;——双指针同时指向0号位置（同非循环队列）
    • 队满队空（三种方案）
      1. 牺牲一个单元来特判队满，队尾入队时少用一个单元（正常配置，最为常用）：
        • 队空：Q.front == Q.rear——双指针同时指向同一位置（同非循环队列）
        • 队满：(Q.rear + 1) % MAXSIZE == Q.front——队头位于队尾后第1个位置
      2. 结构体增设一个表示元素个数的数据成员Q.size：
        • 队空：Q.size == 0
        • 队满：Q.size == MAXSIZE
      3. 结构体增设一个区分队满与队空的标记成员Q.tag：
        • 每次执行删除时置为0，执行插入时置为1（无论当前状态如何）
        • Q.tag == 0时，因删除导致Q.front == Q.rear，则队空
        • Q.tag == 1时，因插入导致Q.front == Q.rear，则队满
    • 队长：(Q.rear - Q.front + MAXSIZE) % MAXSIZE
  • 操作——先操作元素，再移动指针
    • 入队：Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAXSIZE;
    • 出队：x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAXSIZE;

2.1.2 链队

链队（Linked Queue）：队列的⼀种链式存储结构。采⽤同时带有头指针、尾指针的单链表实现。规定表头为允许进⾏删除操作的队⾸，表尾为允许进⾏插⼊操作的队尾。实际相当于只允许头删、尾插的单链表。

通常带有链队头结点，且封装了队⾸指针Q.front（所指结点通常不存储数据元素，参考链表⾥的头结点）、队尾指针Q.rear

typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
} QueueNode;    // 队列元素结点

typedef struct QueueHead {
    QueueNode *front;   // 队⾸指针，操作上相当于单链表的头结点指针
    QueueNode *rear;    // 队尾指针
} LinkQueue;    // 链队头结点

状态表示（正常配置）：

  • 队空/初始化状态：Q.front == Q.rear
  • 队满：链表⽆表满状态

基本操作：

  • ⼊队：相当于将新结点s尾插至链表尾的操作 
    /* 新结点s⼊队 */
s->next = Q.rear->next;
Q.rear->next = s;
  • 出队：相当于带头链表删除表头元素的操作；当删除链队中最后⼀个元素时需同时修改头尾指针Q.rear = Q.front;，使得队被完全清空 
    /* 队⾸结点出队 */
p = Q.front->next;
Q.front->next = p->next;
if (p == Q.rear) Q.rear = Q.front;
free(p);

2.2 循环队列的配置问题

本文规定满⾜以下特征的配置为循环队列的正常配置：

  1. 队⾮空时双指针重合
  2. 牺牲⼀个空间表示队满
  3. 先操作元素、再移动指针

特点：front始终指向元素，rear始终指向空位

两种常见的⾮正常配置修改⽅式：

  1. 修改操作顺序——先移动指针、再操作元素
    • 入队：Q.rear = (Q.rear + 1) % MAXSIZE; Q.data[Q.rear] = x;
    • 出队：Q.front = (Q.front + 1) % MAXSIZE; x = Q.data[Q.front];

特点：front始终指向空位，rear始终指向元素，其余与正常配置完全一致

  1. 修改状态表示——队⾮空时双指针都指向元素
    • 队空/初始化状态：(Q.rear + 1) % MAXSIZE == Q.front——队头位于队尾后第1个位置（恰好为正常配置的队满条件）
    • 队满：(Q.rear + 2) % MAXSIZE == Q.front——队头位于队尾后第2个位置（比正常配置后移一位）
    • 队长：(Q.rear - Q.front + 1 + MAXSIZE) % MAXSIZE

特点：初始状态双指针不重合

多画图，多体会。这些配置在本站各处皆有广泛应用。

2.3 队列的扩展与应用

队列的简单应⽤：BFS，拓扑排序；缓冲区、⻚⾯调度算法……

详见后述

2.3.1 双端队列

双端队列（Double-ended Queue，Deque）：两端都可进⾏元素的插⼊和删除操作的线性结构。对双端队列左右两端进⾏各种输⼊、输出限制，即输⼊受限、输出受限，可使其退化为线性表、栈、队列或其他特殊结构。

验证出队序列的合法性：

  • 输出受限（仅⼀端可输出）：按输出序列填充队列，再模拟⼊队过程是否可⾏
    `1. 先按输出序列根据出⼝⽅向在队列中填好元素

    1. 遍历输⼊序列，模拟各元素⼊队情形，同时随时按输出序列让两端应出队元素出队，若⽆法从两端⼊队（有⼈想"插队"）则直接判⾮法

  • 输⼊受限（仅⼀端可输⼊）：全体⼊队，根据输出逐⼀出队
    1. 先直接按输⼊序列让所有元素从入口⼊队
    2. 遍历输出队列中各元素，检查应出队元素是否出现在队列两端：是则出队并继续，否则直接判⾮法

输出受限的情形比输入受限要复杂、灵活得多，故请仔细体会。

2.3.2 ⽤栈模拟队列

使用两个并排放置的栈s1与s2模拟队列，操作与状态如下：

  • 元素入队：
    1. 若s1未满，则让该元素直接入s1
    2. 若s1满、s2空，则将s1中全部元素逐一出栈进入s2，然后让该元素入s1
  • 元素出队：
    1. 若s2非空，则直接s2弹出栈顶元素
    2. 若s2空，则将s1中元素全部出栈倒入s2，然后s2弹出栈顶元素
  • 队满：s2满且s1非空，则不能继续入队

A 单调栈*

核心思想：及时弹出必不会作为答案的数，使得容器内各所指元素始终单调。

常见模型：最近极值查找——找出数列中每个数左边离它最近的比它大/小的数。

【例】输出数组a[1 ... n]中每个数左边离它最近的比它小的数，不存在则输出-1（若想求大，只需改变判定弹出的不等号即可）：

int n, a[N];    // a[1 ... n]
int stk[N], tt = -1;    // 栈中存储数组元素下标

// 思想：若a[x] >= a[y] (x < y)，则a[x]必不会是任何一数的答案，可直接剔除
void printNearestMins() {
    for (int i = 0; i < n; i++) {   // 双指针算法，i是子区间右端点
        while (tt != -1 && a[stk[tt]] >= a[i]) {
            tt--;   // 弹出既大又"远"的数
        }

        if (tt != -1) {
            printf("%d ", a[stk[tt]]);
        } else {
            printf("-1 ");
        }

        stk[++tt] = i;
    }
}

B 单调队列*

核心思想同单调栈。容器为输入限制的双端队列。

常见模型：找出滑动窗口中的最大值/最小值。

【例】设数组a[1 ... n]中的滑动窗口长度为k，输出滑动窗口每次前移时窗口内的最小值（若想求大，只需改变判定弹出的不等号即可）：

int n, a[N];    // a[1 ... n]
int k;  // 滑动窗口的长度
int q[N], hh = 0, tt = -1;  // 队列（双端队列）中存储数组元素下标

// 思想：同单调栈，且应输出的最值在队头（单调）
void printWindowMins() {
    for (int i = 0; i < n; i++) {   // 双指针算法，i是子区间右端点
        while (hh <= tt && i - k + 1 > q[hh]) {
            hh++;   // 判断队头是否滑出窗口
        }
        while (hh <= tt && a[q[tt]] >= a[i]) {
            tt--;   // 同单调栈，队尾弹出既大又"远"的数
        }

        q[++tt] = i;    // 先将i从队尾入队

        if (i + 1 >= k) {
            printf("%d ", a[q[hh]]);    // 当窗口长度达到要求时才输出
        }
    }
}

发表评论