第三章 栈和队列

Posted on Edited on In Views:

栈的基本概念

  • 栈（Stack）：一种操作受限的线性表，只允许在一端进行插入和删除操作的线性表。
    • 特点：后进先出（Last In First Out，LIFO）
    • 逻辑结构：与普通线性表相同
    • 数据的运算：插入、删除操作有区别
  • 重要术语：
    • 空栈：栈里面没有任何数据元素
    • 栈顶：允许插入和删除的一端
    • 栈底：不允许插入和删除的一端
  • 基本操作：
    • InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
    • DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
    • Push(&S, x)：进栈，若栈 S 未满，则将 x 加入使其成为新栈顶。
    • Pop(&S, &x)：出栈，若栈 S 非空，则弹出栈顶元素，并用 x 返回。
    • GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
    • StackEmpty(S)：判断一个栈 S 是否为空。若 S 为空，返回 ture，否则返回 false。
  • n 个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}C^n_{2n}$，上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明。

顺序栈的实现

  • 顺序栈的定义

    1
    2
    3
    4
    5
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

  • 初始化操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

    //初始化栈
    void InitStack(Sqtack &S) {
        S.top = -1;	//初始化栈顶指针
    }
    //判断栈空
    bool StackEmpty(SqStack S){
        if(S.top == -1)	//栈空
            return true;
        else 			//不空
            return false;
    }

  • 进栈操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

    //新元素入栈
    bool Push(SqStack &S, ElemType x) {
        if(S.top == MaxSize - 1)	//栈满，报错
            return false;
        S.top = S.top + 1;	//指针先加1
        S.data[S.top] = x;	//新元素入栈
        //以上两行代码等价于 S.data[++S.top] = x;
        return true;
    }

  • 出栈操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

    //出栈操作
    bool Pop(SqStack &S, ElemType &x) {
        if(S.top == -1)	//栈空，报错
            return false;
        x = S.data[S.top];	//栈顶元素先出栈
        S.top = S.top - 1;	//指针再减一
        //以上两行代码等价于 x = S.data[S.top--];
        return true;
    }

  • 读栈顶操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

    //出栈操作
    bool GetTop(SqStack &S, ElemType &x) {
        if(S.top == -1)	//栈空，报错
            return false;
        x = S.data[S.top];	//x记录栈顶元素
        return true;
    }

  • 初始化，入栈，出栈和读栈顶都是O(1)时间复杂度。

  • SqStack S;声明栈时分配内存，函数运行结束后系统自动回收内存。

  • 栈满的条件：top == MaxSize - 1

  • 另一种方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top;	//栈顶指针
    } SqStack;

    //初始化栈
    void InitStack(Sqtack &S) {
        S.top = 0;	//top指向下一个可以插入元素的位置
    }
    //判断栈空
    bool StackEmpty(SqStack S){
        if(S.top == 0)	//栈空
            return true;
        else 			//不空
            return false;
    }
    //进栈
    S.data[S.top] = x;
    S.top = S.top + 1;
    等价于 S.data[S.top++] = x;
    //出栈
    S.top = S.top - 1;
    x = S.data[S.top];
    等价于 x = S.data[--S.top];

    栈满的条件：top == MaxSize

  • 顺序栈的缺点：栈的大小不可变。

  • 共享栈：两个栈共享同一片空间。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemType date[MaxSize];	//静态数组存放栈中元素
    	int top0;	//0号栈栈顶指针
        int top1;	//1号栈栈顶指针
    } SqStack;

    //初始化栈
    void InitStack(Sqtack &S) {
        S.top0 = -1;	//初始化栈顶指针
        S.top1 = MaxSize;
    }

    栈满的条件：top0 + 1 == top1

链栈的实现

  • 链栈：用链式存储方式实现的栈。

  • 链栈的定义

    1
    2
    3
    4
    typedef struct Linknode {
        ElemType data;	//数据域
        struct Linknode *next;	//指针域
    } *LiStack;	//栈类型定义

  • 进栈：对头结点后插操作。

  • 出栈：对头结点“后删”操作。

  • 进栈和出栈操作都只能在栈顶一端进行（链头作为栈顶）。

  • 实现方式推荐不带头结点。

队列的基本概念

  • 队列（Queue）：一种操作受限的线性表，只允许在一端进行插入，在另一端删除的线性表。
    • 特点：先进先出（Firstt In First Out，FIFO）
  • 重要术语：
    • 空队列：队列里面没有任何数据元素。
    • 队尾：允许插入的一端。
    • 队头：允许删除的一端。
  • 基本操作：
    • InitQueue(&Q)：初始化队列。构造一个空队列 Q。
    • DestroyQueue(&Q)：销毁队列。销毁并释放队列 Q 所占用的内存空间。
    • Push(&Q, x)：进队，若队列 Q 未满，则将 x 加入使其成为新的队尾。
    • Pop(&Q, &x)：出队，若队列 Q 非空，则弹出队顶元素，并用 x 返回。
    • GetTop(Q, &x)：读队头元素。若队列 Q 非空，则用 x 返回队头元素。
    • QueuekEmpty(Q)：判断一个队列 Q 是否为空。若 Q 为空，返回 ture，否则返回 false。

队列的顺序实现

  • 队列的顺序实现

    1
    2
    3
    4
    5
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemeType date[MaxSize];	//静态数组存放队列元素
    	int front, rear;	//队头指针和队尾指针
    } SqQueue;

    队头指针指向头元素；队尾指针指向下一个应该插入的位置

  • 初始化操作

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemeType date[MaxSize];	//静态数组存放队列元素
    	int front, rear;	//队头指针和队尾指针
    } SqQueue;

    //初始化队列
    void InitQueue(SqQueue &Q) {
        //初始时 队头、队尾指针指向0
        Q.rear = Q.front = 0;
    }
    //判断队列是否为空
    bool QueueEmpty(SqQueue) {
        if (Q.rear == Q.front)
            return true;
        else
            return false;
    }

  • 入队操作（循环队列）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    #define MaxSize 10	//定义栈中元素的最大个数
    typedef struct {
    	ElemeType date[MaxSize];	//静态数组存放队列元素
    	int front, rear;	//队头指针和队尾指针
    } SqQueue;

    //入队（循环队列）
    bool EnQueue(SqQueue &Q, ElemType x) {
        if ((Q.rear + 1) % MaxSize == Q.front)
            return false;	//队满则报错
        Q.data[Q.rear] = x;	//新元素插入队尾
        Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针加1取模
        return true;
    }

  • 出队操作（循环队列）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //出队（删除一个队头元素，并用x返回）
    bool DeQueue(SqQueue &Q, ElemType &x) {
        if (Q.rear == Q.front)
            return false;	//队空则报错
        x = Q.data[Q.front];
        Q.front = (Q.front + 1) % MaxSize;
        return true;
    }
    //获取队头元素的值，用x返回
    bool GetHead(SqQueue Q, ElemType &x) {
        if (Q.rear == Q.front)
            return false;	//队空则报错
        x = Q.data[Q.front];
        return true;
    }

  • 判断队列已满/已空

    • 方案一：

      • 队满条件：队尾指针的下一个位置是队头(Q.rear + 1) % MaxSize == Q.front
      • 队空条件：Q.rear == Q.front
      1
      2
      3
      4
      5
      #define MaxSize 10	//定义栈中元素的最大个数
      typedef struct {
      	ElemeType date[MaxSize];	//静态数组存放队列元素
      	int front, rear;	//队头指针和队尾指针（初始化时 rear = front = 0)
      } SqQueue;

    • 方案二：

      • 队满条件：size == MaxSize
      • 队空条件：size == 0
      • 插入成功 size++；删除成功 size–
      1
      2
      3
      4
      5
      6
      #define MaxSize 10	//定义栈中元素的最大个数
      typedef struct {
      	ElemeType date[MaxSize];	//静态数组存放队列元素
      	int front, rear;	//队头指针和队尾指针
          int size;	//队列当前长度（初始化时：size = 0）
      } SqQueue;

    • 方案三：

      • 队满条件：front == rear && tag == 1
      • 队空条件：front == rear && tag == 0
      • 插入成功 tag = 0；删除成功 tag = 1
      1
      2
      3
      4
      5
      6
      #define MaxSize 10	//定义栈中元素的最大个数
      typedef struct {
      	ElemeType date[MaxSize];	//静态数组存放队列元素
      	int front, rear;	//队头指针和队尾指针
          int tag;	//最近进行的是删除/插入（初始化时：tag = 0）
      } SqQueue;

  • 注意：

    • 队尾指针指向队尾元素下一个位置
    • 队尾指针指向指向队尾元素
      • 初始化：front = 0；rear = n-1
      • 插入：队尾指针先后移，再插入元素
      • 判空：(Q.rear+1)%MaxSize == Q.front
      • 判满：
        • 牺牲一个存储单元
        • 增加辅助变量

队列的链式实现

  • 队列的链式实现

    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct Linknode {	//链式队列结点
        ElemType data;
        struct Linknode *next;
    } LinkNode;

    typedef struct {	//链式队列
        LinkNode *front, *rear;	//队列的队头和队尾指针
    } LinkQueue;

  • 初始化（带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    typedef struct Linknode {	//链式队列结点
        ElemType data;
        struct Linknode *next;
    } LinkNode;

    typedef struct {	//链式队列
        LinkNode *front, *rear;	//队列的队头和队尾指针
    } LinkQueue;

    //初始化队列（带头结点）
    void InitQueue(LinkQueue &Q) {
        //初始时 front 和 rear 都指向头结点
        Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
        Q.front->next = NULL;
    }
    //判断队列是否为空
    bool isEmpy(LinkQueue Q) {
        if (Q.front == Q.rear)
            return true;
        else
            return false;
    }

    初始化（不带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //初始化队列（不带头结点）
    void InitQueue(LinkQueue &Q) {
        //初始时 front 和 rear 都指向NULL
        Q.front = NULL;
        Q.rear= NULL;
    }
    //判断队列是否为空
    bool isEmpy(LinkQueue Q) {
        if (Q.front == NULL)
            return true;
        else
            return false;
    }

  • 入队（带头结点）

    1
    2
    3
    4
    5
    6
    7
    void EnQueue(LinkQueue &Q, ElemType x) {
        LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = x;
        s->next = NULL;
        Q.rear->next = s;	//新结点插入到rear之后
        Q.rear = s;	//修改表尾指针
    }

    入队（不带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    void EnQueue(LinkQueue &Q, ElemType x) {
        LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
        s->data = x;
        s->next = NULL;
        if (Q.front == NULL) {	//在空队列中插入第一个元素
            Q.front = s;	//修改队头队尾指针
            Q.rear = s;
        } else {
    		Q.rear->next = s;	//新结点插入到 rear 结点之后
            Q.rear = s;	//修改 rear 指针
        }

  • 出队（带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //队头元素出队（带头结点）
    bool DeQueue(LinkQueue &Q, ElemType &x) {
        if(Q.front == Q.rear)
            return false;	//空队
        LinkNode *p = Q.front->next;
        x = p->data;	//用变量 x 返回队头元素
        Q.front->next = p->next;	//修改头结点的 next 指针
        if(Q.rear == p)	//此次是最后一个极点出队
            Q.rear == Q.front;	//修改 rear 指针
        free(p);	//释放结点空间
        return true;
    }

    出队（不带头结点）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    //队头元素出队（不带头结点）
    bool DeQueue(LinkQueue &Q, ElemType &x) {
        if(Q.front == NULL)
            return false;	//空队
        LinkNode *p = Q.front;	//p 指向此次出队的结点
        x = p->data;	//用变量 x 返回队头元素
        Q.front = p->next;	//修改 front 指针
        if(Q.rear == p)	//此次是最后一个极点出队
            Q.front == NULL;	//front 指向 NULL
            Q.rear == NULL;	//rear 指针 NULL
        free(p);	//释放结点空间
        return true;
    }

  • 链式存储——一般不会队满，除非内存不足。

双端队列

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

栈的应用——括号匹配问题

  • 最后出现的左括号最先被匹配（LIFO）

  • 算法实现：依次扫描所有字符，遇到左括号进栈，遇到右括号则弹出栈顶元素检查是否匹配。

    • 匹配失败情况：
      • 剩余左（右）括号
      • 左右括号不匹配
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #define MaxSize 10	//定义栈中元素的最大个数（存在存满情况可用 链栈）
    typedef struct {
        char date[MaxSize];	//静态数组存放栈中元素
        int top;	//栈顶指针
    } SqStack;

    //初始化栈
    void InitStack(SqStack &s);
    //判断栈是否为空
    bool StackEmpty(SqStack S);
    //新元素入栈
    bool Push(SqStack &S, char x);
    //栈顶元素出栈，用 x 返回
    bool Pop(SqStack &S, char &x);

    bool bracketCheck(char str[], int length) {
        SqStack S;
        InitStack(S);	//初始化一个栈
        for (int i = 0; i < length; i++) {
            if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
                Push(S, str[i]);	//匹配到左括号，入栈
            } else {
                if(StackEmpty(S))	//匹配到右括号，且当前栈空
                    return false;	//匹配失效
                char topElem;
                Pop(S, topElem);	//栈顶元素出栈
                if(str[i] == ')' && topElem!='(')
                    return false;
                if (str[i] == ']' && topElem != '[')
                    return false;
                if (str[i] == '}' && topElem != '{')
                    return false;
            }
        }
        return StackEmpty(S);
    }

栈的应用——表达式求值

  • 中缀表达式：运算符在两个操作数中间
  • 后缀表达式（逆波兰表达式）：运算符在两个操作数后面
  • 前缀表达式（波兰表达式）：运算符在两个操作数前面
  • 中缀转后缀的手算方法：
    1. 确定中缀表达式中各个运算符的运算顺序
    2. 选择下一个运算符，按照（左操作数 右操作数 运算符）的方式组成一个新的操作数
    3. 如果还有运算符没被处理，就继续上一步
  • “左优先“原则：只要左边的运算符能先计算，就优先算左边的。保证手算和机算结果相同。
  • 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对运算，合体为一个操作数。
  • 用栈实现后缀表达式的计算：
    1. 从左往右扫描下一个元素，直到处理完所有元素
    2. 若扫描到操作数则压入栈，回到上一步；否则执行下一步
    3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“右操作数”），执行相应运算，运算结果压回栈顶，回到第一步
  • 中缀转前缀的手算方法：
    1. 确定中缀表达式中各个运算符的运算顺序
    2. 选择下一个运算符，按照（运算符 左操作数 右操作数）的方式组成一个新的操作数
    3. 如果还有运算符没被处理，就继续上一步
  • “右优先“原则：只要右边的运算符能先计算，就优先算右边的。保证手算和机算结果相同。
  • 用栈实现前缀表达式的计算：
    1. 从右往左扫描下一个元素，直到处理完所有元素
    2. 若扫描到操作数则压入栈，回到上一步；否则执行下一步
    3. 若扫描到运算符，则弹出两个栈顶元素（先出栈的是“左操作数”），执行相应运算，运算结果压回栈顶，回到第一步
  • 中缀表达式转后缀表达式（机算）
    1. 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
    2. 从左到右处理各个元素，直到末尾。可能遇到三种情况：
      • 遇到操作数。直接假如后缀表达式。
      • 遇到界限符。遇到 “(“ 直接入栈；遇到 “)” 则依次弹出栈内运算符并加入后缀表达式，直到弹出 “(“ 为止。注意：”(“ 不加入后缀表达式。
      • 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 “(“ 或栈空则停止。之后再把当前运算符入栈。
    3. 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
  • 中缀表达式的计算（用栈实现）：
    1. 初始化两个栈，操作数栈和运算符栈
    2. 若扫描到操作数，压入操作数栈
    3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应元素，运算结果再压回操作数栈）

栈的应用——递归

  • 函数调用的特点：最后被调用的函数最先执行结束（LIFO）
  • 函数调用时，需要用到一个栈存储：
    • 调用返回地址
    • 实参
    • 局部变量
  • 适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题。例如：
    • 计算正整数的阶乘！
    • 求斐波那契数列
  • 递归调用时，函数调用栈可称为“递归工作栈”。
    • 每进入一层递归，就将递归调用所需信息压入栈顶。
    • 每退出一层递归，每退出一层递归，就从栈顶弹出相应信息。
  • 缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算。
  • 可以自定义栈将递归算法改造成非递归算法。

队列的应用

  • 树的层次遍历
  • 图的广度优先遍历
  • 队列在操作系统中应用
    • 多个进程争抢着使用有限的系统资源，FCFS（First Come First Service，先来先服务）是一种常用策略。
    • 打印数据缓冲区。

特殊矩阵压缩存储

数组的存储结构

  • 一维数组的存储结构
    • ElemType a[10];
    • 起始地址：LOC
    • 各组元素大小相同，且物理上连续存放。
      • 数组元素 a[i] 的存放地址 = LOC+ i*sizeof(Elemtype)
      • 数组下标默认从0开始。
  • 二维数组的存储结构
    • 两种存储策略：行优先存储；列优先存储。
    • 起始地址：LOC
    • 在M行N列的二维数组中
      • 若行优先存储，b[ i ] [ j ]的存储地址 = LOC + (i * N + j) * sizeof(ElemType)
      • 若列优先存储，b[ i ] [ j ]的存储地址 = LOC + (i * M + i) * sizeof(ElemType)

普通矩阵的存储

  • 可用二维数组存储
  • 描述矩阵元素时行和列通常从1开始，描述数组时通常从0开始。

对称矩阵的压缩存储

  • 对称矩阵：元素值关于主对角线对称。
  • 策略：只存储主对角线 + 下三角区。
  • 按行优先原则将各元素存入一维数组中。
    • 共有$\frac{n * (n+1)}{2}$个元素，按行优先原则ai,j是第$\frac{i * (i -1)}{2} + j$个元素。
    • 找上三角区元素：找aj,i
  • 按列优先原则将各元素存入一维数组中。
    • 共有$\frac{n * (n+1)}{2}$个元素，按行优先原则ai,j是第[n + (n-1) + … + (n-j+2)] + (i-j) +1个元素。
    • 找上三角区元素：找aj,i

三角矩阵的压缩存储

  • 下三角矩阵：除了主对角线和下三角区，其余的元素都相同

  • 压缩存储策略：

    • 按行优先原则将下三角区存入一维数组中。并在最后一个位置存储常量C。

    • 共有$\frac{n * (n+1)}{2} + 1$个元素，按行优先原则：

      • 若i >= j，ai,j是第$\frac{i * (i -1)}{2} + j$个元素。
      • 若i < j，ai,j是第$\frac{n * (n + 1)}{2} + j$个元素。

    • 按行优先原则将上三角区存入一维数组中。并在最后一个位置存储常量C。

    • 共有$\frac{n * (n+1)}{2} + 1$个元素，按行优先原则：

      • 若i <= j，ai,j是第[n + (n - 1) + … + (n - j + 2)] + (i - j) +1个元素。
      • 若i > j，ai,j是第$\frac{n * (n + 1)}{2} + j$个元素。

三对角矩阵的压缩存储

  • 三对角矩阵：又称带状矩阵。主对角线及其相邻对角线元素可以不为0，其余元素均为0。（除了第一行和最后一行至多有两个不为0元素，其余行至多有三个不为0元素。
  • 共有3n-2个元素，按行优先原则，ai,j是第2*i+j-2个元素。
  • 第 k 个元素在第(k+2) /3行，第k-2*i+3列。

稀疏矩阵的压缩存储

  • 稀疏矩阵：非零元素远远少于矩阵元素的个数。
  • 策略：
    • 顺序存储——三元组<行，列，值>（struct）
    • 链式存储——十字链表法
      • 向下域down：指向同列的下一个非零元素
      • 向右域right：指向同行的下一个非零元素