DataStructure2（栈和队列）

第三章：栈和队列

3.1栈（stack）

3.1.1栈的基本概念

1.栈的定义

  • 栈是特殊的线性表：==只允许在一端进行插入或删除操作==， 其逻辑结构与普通线性表相同；

  • 栈顶（Top）：允许进行插入和删除的一端 （最上面的为栈顶元素）；

  • 栈底（Bottom）：固定的，不允许进行插入和删除的一端 （最下面的为栈底元素）；

  • 空栈：不含任何元素的空表；

  • 特点：==后进先出==（后进栈的元素先出栈）（LIFO: Last In First Out）

  • 缺点：栈的大小不可变，解决方法——共享栈；

2.栈的基本操作

“创建&销毁”

  • 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为空，则返回true,否则返回false；
3.栈的常考题型：进栈与出栈顺序问题

进栈顺序：a → b → c → d → e

问：有哪些合法的出栈顺序？

出栈排列数的卡特兰数公式

  • n 个不同元素进栈，出栈元素不同排列的个数为：$$ \frac{1}{n+1}C_{2n}^n $$

示例计算（n=5 时）

$$\frac{1}{5+1}C_{10}^5 = \frac{10 \times 9 \times 8 \times 7 \times 6}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = 42$$

$$C_{m}^k = \frac{m!}{k! \cdot (m-k)!}$$

3.1.2 栈的顺序存储

1.顺序栈的定义
1
2
3
4
5
6
7
8
9
10
11
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素
}SqStack;

void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
                     //连续的存储空间大小为 MaxSize*sizeof(ElemType)
}

sqStack中的sq：sequence顺序

2.顺序栈的基本操作
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top;                      //栈顶元素(也叫栈顶指针，这里存的是数组下标，相当于指针)
}SqStack;

//初始化栈
void InitStack(SqStack &S){
    S.top = -1;                   //初始化栈顶指针
}

//判栈空
bool StackEmpty(SqStack S){
    if(S.top == -1)      //栈空
        return true;
    else                 //栈不空
        return false;
}

//新元素进栈
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;
}

//出栈
bool Pop(SqStack &x, ElemType &x){
    if(S.top == -1)          //栈空
        return false;
    
    x = S.data[S.top];       //先出栈
    S.top = S.top - 1;       //栈顶指针减1
    return true;

    /*
    x = S.data[S.top--];
    */

    //只是逻辑上的删除，数据依然残留在内存里

}

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


void testStack(){
    SqStack S;       //声明一个顺序栈(分配空间)
    InitStack(S);
    //...
}

法二：注意：==也可以==初始化时定义 S.top = 0 ：top指针指向==下一个可以插入==元素的位置(栈顶元素的后一个位置)；

  • 进栈操作 ：栈不满时，栈顶指针先加1，再送值到栈顶元素。S.data[S.top++] = x;
  • 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。x = S.data[–S.top];
  • 栈空条件：S.top==-1
  • 栈满条件：S.top==MaxSize-1
  • 栈长：S.top+1
  • 栈的顺序存储是使用静态数组存放元素，容量改变不了，很容易满
  • 改进：
    • 分配大量的存储空间，很浪费
    • 使用链栈
    • 使用共享栈：
3.共享栈
  • 使用两个栈顶指针

image-20251021213555350

**定义：**利用栈底位置相对不变的特性，可以让==两个顺序栈共享==一个一维数组空间，将两个栈的栈底 分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。

  • 存取数据的时间复杂度均为O（1）
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MaxSize 10         //定义栈中元素的最大个数

typedef struct{
    ElemType data[MaxSize];       //静态数组存放栈中元素
    int top0;                     //0号栈栈顶指针
    int top1;                     //1号栈栈顶指针
}ShStack;

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

栈满条件：top1-top0=1

image-20251021213626022

3.1.3栈的链式存储

1.定义：采用链式存储的栈称为链栈。
2.优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
3.特点：

  • 进栈和出栈都只能在栈顶一端进行(链头作为栈顶)

  • 链表的头部作为栈顶，意味着：

    • 在实现数据”入栈”操作时，需要将数据从==链表的头部插入==；

    • 在实现数据”出栈”操作时，需要删除==链表头部的首元节点==；

      因此，链栈实际上就是一个只能采用==头插法==插入或删除数据的链表;
      栈的链式存储结构可描述为：

    1
    2
    3
    4
    typedef struct Linknode{
        ElemType data;              //数据域
        struct Linknode *next;      //指针域
    }*LiStack;                      //栈类型的定义
  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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode *next;       //指针域
}Linknode,*LiStack;   

typedef Linknode *Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

//1. 初始化
void InitStack(LiStack &L){   //L为头指针
    L = new Linknode; 
    L->next = NULL;
}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L->next == NULL){
        return true;
    }
    else
        return false;
}

//3. 进栈：(链栈基本上不会出现栈满的情况)
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;
    s->data = x;

    //头插法
    s->next = L->next;
    L->next = s;
}

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s;
    if(L->next == NULL) //栈空不能出栈
        return false;
    
    s = L->next;
    x = s->data;
    L->next = L->next->next;
    delete(s);

    return true;
}

不带头结点的链栈基本操作：

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
37
38
39
40
41
42
43
44
45
#include<stdio.h>

struct Linknode{
    int data;             //数据域
    Linknode *next;       //指针域
}Linknode,*LiStack;   

typedef Linknode *Node;   //结点结构体指针变量
typedef Node List;        //结点结构体头指针变量

//1.初始化 
void initStack(LiStack &L){
    L=NULL;
}

//2.判栈空
bool isEmpty(LiStack &L){
    if(L == NULL)
        return true;
    else
        teturn false;
}

//3.进栈
void pushStack(LiStack &L, int x){
    Linknode s;          //创建存储新元素的结点
    s = new Linknode;

    s->next = L;
    L = s;
}

//4.出栈
bool popStack(LiStack &L, int &x){
    Linknode s; 
    if(L = NULL)     //栈空不出栈
        return false;

    s = L;
    x = s->data;
    L = L->next;
    delete(s);
    
    return true;
}

3.2队列（Queue）

3.2.1队列的基本概念

1.定义：队列（Queue）简称队，是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。

2.特点

  • 队列是操作受限的线性表，==只允许在一端进行插入 (入队)，另一端进行删除 (出队)==
  • 操作特性：先进先出 FIFO（First In First Out）
  • 队头：允许删除的一端
  • 队尾：允许插入的一端
  • 空队列：不含任何元素的空表

3.队列的基本操作

  • “创建&销毁”

    • InitQueue(&Q): 初始化队列，构造一个空列表Q
    • DestroyQueue(&Q): 销毁队列，并释放队列Q所占用的内存空间

  • “增&删”

    • EnQueue(&Q, x): 入队，若队列Q未满，将x加入，使之成为新的队尾
    • DeQueue(&Q, &x): 出队，若队列Q非空，删除队头元素，并用x返回

  • “查&其他”

    • GetHead(Q,&): 读队头元素，若队列Q非空，则将队头元素赋值给x
    • QueueEmpty(Q): 判队列空，若队列Q为空，则返回
3.2.2队列的顺序存储结构
  • 队头指针：指向队头元素
  • 队尾指针：指向队尾元素的下一个位置
  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
26
27
//队列的顺序存储类型
# define MaxSize 10;     //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];   //用静态数组存放队列元素
                              //连续的存储空间，大小为——MaxSize*sizeof(ElemType)
    int front, rear;          //队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始化时，队头、队尾指针指向0
    Q.rear = Q.front = 0;
}

void test{
    SqQueue Q;                //声明一个队列
    InitQueue(Q);
    //...
}

// 判空
bool QueueEmpty(SqQueue 0){
    if(Q.rear == Q.front)    //判空条件后
        return true;
    else 
        return false;
}

image-20251023091401635

image-20251023091908893

  • 实际上没有满，前面分配的空间会被浪费，怎么办：循环队列（队尾指针rear是9，新元素插入到9，rear+1再取余10，到0，类似晚上十一点，过一个小时是0点）
  1. 循环队列
    定义：将循环队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。
    基本操作：
1
2
3
4
5
6
7
8
9
10
a%b == a除以b的余数

初始：Q.front = Q.rear = 0;

队首指针进1：Q.front = (Q.front + 1) % MaxSize

队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移，当移到最后一个后，下次移动会到第一个位置

队列长度：(Q.rear + MaxSize - Q.front) % MaxSize
    （类比下午3点减早上11点，三点先借12：3+12-11）

区分队空还是队满的情况：
方案一: 牺牲一个单元来区分队空和队满（判断队满 不能对头==队尾，因为这是队空的情况）
队尾指针的再下一个位置就是队头，即 (Q.rear+1)%MaxSize == Q.front

取模是因为如果MaxSize是5，front是0，rear是4

  • 循环队列——入队：只能从队尾插入（判满使用方案一）
1
2
3
4
5
6
7
8
bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front)        //队满
        return false;
    Q.data[Q.rear] = x;                      //将x插入队尾
    Q.rear = (Q.rear + 1) % MaxSize;         //队尾指针加1取模

    return true;
}
  • 循环队列——出队：只能让队头元素出队
1
2
3
4
5
6
7
8
9
10
//出队，删除一个队头元素，用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;
}
  • 循环队列——获得队头元素
1
2
3
4
5
6
7
bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)              //队空报错
        return false;  

    x = Q.data[Q.front];
    return true;
}

方案二: 不牺牲存储空间，设置size
定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队成功 size++，出队成功size--，根据size的值判断队满与队空

队满条件：size == MaxSize

队空条件：size == 0

1
2
3
4
5
6
7
8
9
10
11
12
# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int size;               //队列当前长度
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    Q.rear = Q.front = 0;
    size = 0;
}

方案三: 不牺牲存储空间，设置tag
定义一个变量 tag，tag = 0 –最近进行的是删除操作；tag = 1 –最近进行的是插入操作；

每次删除操作成功时，都令tag = 0；只有删除操作，才可能导致队空；
每次插入操作成功时，都令tag = 1；只有插入操作，才可能导致队满；

队满条件：Q.front == Q.rear && tag == 1

队空条件：Q.front == Q.rear && tag == 0

1
2
3
4
5
6
# define MaxSize 10;     
typedef struct{
    ElemType data[MaxSize];   
    int front, rear;        
    int tag;               //最近进行的是删除or插入
}SqQueue;
3.2.3队列的链式存储结构

1.定义：队列的链式表示称为链队列，它实际上是一个==同时带有队头指针和队尾指针的单链表==。

  • 链队列：用链表表示的队列，是限制仅在==表头删除==和==表尾插入==的单链表。
    队列的链式存储类型可描述为:
1
2
3
4
5
6
7
8
typedef struct LinkNode{      //链式队列结点
    ElemType data;
    struct LinkNode *next;
}

typedef struct{               //链式队列
    LinkNode *front, *rear;   //队列的队头和队尾指针
}LinkQueue;
  • 一个链队列只需要一套头指针和尾指针，但需要很多套结点，所以头尾指针需要另起一套结构体来写

2.链式队列的基本操作——带头结点

  • 初始化 & 判空

image-20251023094856975

1
2
3
4
5
6
7
8
9
10
11
12
13
void InitQueue(LinkQueue &Q){
    //初始化时，front、rear都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front -> next = NULL;
}

//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)     //也可用 Q.front -> next == NULL
        return true;
    else
        return false;
}

  • 入队操作

    image-20251023095046267

1
2
3
4
5
6
7
8
//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //申请一个新结点
    s->data = x;
    s->next = NULL;     //s作为最后一个结点，指针域指向NULL
    Q.rear->next = s;   //新结点插入到当前的rear之后
    Q.rear = s;         //表尾指针指向新的表尾
}
  • 出队操作

image-20251023095400524

image-20251023095411603

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front == Q.rear)
        return false;                    //空队
    
    LinkNode *p = Q.front->next;         //p指针指向即将删除的结点 (头结点所指向的结点)
    x = p->data;
    Q.front->next = p->next;             //修改头结点的next指针
    if(Q.rear == p)                      //此次是最后一个结点出队
        Q.rear = Q.front;                //修改rear指针
    free(p);                             //释放结点空间

    return true;
}

  • 队列满的条件

    • 顺序存储：预分配存储空间
    • 链式存储：一般不会队满，除非内存不足

  • 计算链队长度 (遍历链队)
    设置一个int length 记录链式队列长度

  • 初始化 & 判空

  • 入队操作（不带头结点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//新元素入队 (表尾进行)
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指针指向新的表尾结点
    }
}
3.2.4双端队列

1.定义：双端队列是指允许==两端都可以进行入队和出队==操作的队列

  • 双端队列允许从两端插入、两端删除的线性表；
  • 如果只使用其中一端的插入、删除操作，则等同于栈；
  • 输入受限的双端队列：允许一端插入，两端删除的线性表；
  • 输出受限的双端队列：允许两端插入，一端删除的线性表；

在这里插入图片描述

3.2.5循环队列

详细见3.2.2

利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的。所以：设头、尾指针。

求循环队列的长度：

在这里插入图片描述

3.3栈的应用

3.3.1栈在括号匹配中的应用

用栈实现括号匹配

  • ((())) ==最后出现==的左括号==最先被匹配== (栈的特性—LIFO);

  • 遇到左括号就入栈;

  • 遇到右括号，就“消耗”一个左括号 (出栈);

    匹配失败情况：

  • 扫描到右括号且栈空，则该右括号单身;

  • 扫描完所有括号后，栈非空，则该左括号单身;

  • 左右括号不匹配;

image-20251023103708498

代码：

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
37
38
39
40
41
42
43
44
45
46
47
48
#define MaxSize 10   

typedef struct{
    char data[MaxSize];
    int top;
} SqStack;

//初始化栈
InitStack(SqStack &S)

//判断栈是否为空
bool StackEmpty(SqStack &S)

//新元素入栈
bool Push(SqStack &S, char x)

//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)


// str里面已经有完整的括号了
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);                //栈空说明匹配成功
}

万一存满了怎么办——可用链栈

3.3.2栈在表达式求值中的应用

image-20251023104915394

image-20251023105110844

image-20251023105126947

1. 中缀表达式 (需要界限符)

运算符在两个操作数==中间==:

1
2
3
4
5
① a + b
② a + b - c
③ a + b - c*d
④ ((15 ÷ (7-(1+1)))×3)-(2+(1+1))
⑤ A + B × (C - D) - E ÷ F
2. 后缀表达式 (逆波兰表达式)

运算符在两个操作数后面:

1
2
3
4
5
6
① a b +
② ab+ c - / a bc- +
③ ab+ cd* -
④ 15 7 1 1 + - ÷ 3 × 2 1 1 + + -
⑤ A B C D - × + E F ÷ - (机算结果)
  A B C D - × E F ÷ - + (不选择)

中缀表达式 转 后缀表达式——手算（自己写纸上算）

  • 步骤1： 确定中缀表达式中各个运算符的运算顺序

  • 步骤2： 选择下一个运算符，按照**[左操作数 右操作数 运算符]**的方式组合成一个新的操作数

  • 步骤3： 如果还有运算符没被处理，继续步骤2

“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；（能保证和机算的一样——唯一性）

1
2
3
中缀：A + B - C * D / E + F
       ①   ④   ②   ③   ⑤     
后缀：A B + C D * E / - F +
重点：中缀表达式转后缀表达式——机算（用算法，就有唯一答案）

image-20251023213507198

  • 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

    • 遇到==操作数==: 直接加入后缀表达式。
    • 遇到==界限符==: 遇到 ‘(’ 直接入栈; 遇到 ‘)’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘(’ 为止。注意: ‘(‘ 不加入后缀表达式。
    • 遇到==运算符==: 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘(’ 或栈空则停止。之后再把当前运算符入栈。（栈顶与读的pk，读的狠些就压栈顶，不很就出来）

  • 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算——手算:

image-20251023105930487

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数；

1
注意： 两个操作数的左右顺序

重点：后缀表达式的计算——机算

给计算机是后缀表达式的话，可以直接算

如果给计算机是中缀表达式，则还需要判断哪个先生效，哪个后生效

image-20251023110315437

image-20251023110343209

用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）

  • 步骤1: 从左往后扫描下一个元素，直到处理完所有元素;

  • 步骤2: 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3;

  • 步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1;

==注意: 先出栈的是“右操作数”==（想象32-，2先出栈，放右边）

3.前缀表达式 (波兰表达式)

运算符在两个操作数前面:

1
2
3
① + a b
② - +ab  c
③ - +ab *cd

中缀表达式转前缀表达式——手算

  • 步骤1： 确定中缀表达式中各个运算符的运算顺序

  • 步骤2： 选择下一个运算符，按照**[运算符 左操作数 右操作数]**的方式组合成一个新的操作数

  • 步骤3： 如果还有运算符没被处理，就继续执行步骤2

“右优先”原则: 只要右边的运算符能先计算，就优先算右边的;

image-20251023112939152

1
2
3
中缀：A + B * (C - D) - E / F
       ⑤   ③    ②    ④   ①
前缀：+ A - * B - C D / E F

前缀表达式的计算——机算
用栈实现前缀表达式的计算

image-20251023113057885

image-20251023113132538

  • 步骤1: 从右往左扫描下一个元素，直到处理完所有元素；

  • 步骤2: 若扫描到操作数则压入栈，并回到步骤1，否则执行步骤3

  • 步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到步骤1；

==注意: 先出栈的是“左操作数”==

4.中缀表达式的计算(用栈实现)

image-20251023214844067

两个算法的结合： 中缀转后缀 + 后缀表达式的求值

  • 初始化两个栈，==操作数栈==和==运算符栈==

  • 若扫描到==操作数==，压入操作数栈

  • 若扫描到==运算符或界限符==，则按照“中缀转后缀”相同的逻辑压入运算符栈（狠的就压上去，不狠的话，栈里面的就先出来做计算，再放新的进去） (期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈项元素并执行相应运算，运算结果再压回操作数栈)

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
OperandType EvaluateExpression() {
    // 算术表达式求值的算符优先算法。设 OPTR 和 OPND 分别为运算符栈和运算数栈，
    // OP 为运算符集合。
    InitStack(OPTR);  
    Push(OPTR, '#');
    InitStack(OPND);  
    c = getchar();
    while (c != '#' || GetTop(OPTR) != '#') {
        if (!In(c, OP)) {
            Push(OPND, c); 
            c = getchar();
        }  // 不是运算符则进栈
        else {
            switch (Precede(GetTop(OPTR), c)) {
                case '<':  // 栈顶元素优先权低
                    Push(OPTR, c);  
                    c = getchar();
                    break;
                case '=':  // 脱括号并接收下一字符
                    Pop(OPTR, x);  
                    c = getchar();
                    break;
                case '>':  // 退栈并将运算结果入栈
                    Pop(OPTR, theta);
                    Pop(OPND, b);  
                    Pop(OPND, a);
                    Push(OPND, Operate(a, theta, b));
                    break;
            }// switch
        }
    }// while
    return GetTop(OPND);
}// EvaluateExpression

3.3.3栈在递归中的应用

image-20251027134208717

函数调用的特点：最后被调用的函数最先执行结束(LIFO)

函数调用时，需要用一个栈存储：

  • 调用返回地址
  • 实参
  • 局部变量

递归调用时，函数调用栈称为 “递归工作栈”:

  • 每进入一层递归，就将递归调用所需信息压入栈顶；
  • 每退出一层递归，就从栈顶弹出相应信息；

**缺点：**太多层递归可能回导致栈溢出；

适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题；

3.4特殊矩阵的压缩存储

  • 矩阵定义： 一个由m*n个元素排成的m行(横向)n列(纵向)的表。
  • 矩阵的常规存储：将矩阵描述为一个二维数组。

3.4.1数组的存储结构

1.一维数组

1
Elemtype a[10];

各数组元素大小相同，物理上连续存放；

起始地址：LOC

数组下标：默认从0开始！

数组元素 a[i] 的存放地址 = LOC + i × sizeof(ElemType)

2.二维数组

1
Elemtype b[2][4]; //2行4列的二维数组

image-20251027135741980

行优先/列优先存储优点：实现随机存储

起始地址：LOC

M行N列的二维数组 b[M][N] 中，b[i][j]的存储地址：

行优先存储: LOC + (i×N + j) × sizeof(ElemType)
列优先存储：LOC + (j×M + i) × sizeof(ElemType)

3.4.2普通矩阵的存储

二维数组存储：

  • 描述矩阵元素时，行、列号通常从1开始；
  • 描述数组时，通常下标从 0 开始；

3.4.3特殊矩阵的存储

特殊矩阵——压缩存储空间（只存有用的数据）

矩阵的压缩存储：为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。

1.对称矩阵(方阵)

在一个n阶方阵A中，若元素满足下述性值：
在这里插入图片描述

在这里插入图片描述

image-20251027140130059

2.三角矩阵(方阵)

以主对角线划分，三角矩阵有上（下）三角两种。上（下）三角矩阵的下（上）三角（不含主对角线）中的元素均为常数。在大多数情况下，三角矩阵常数为零。

在这里插入图片描述

3.三对角矩阵(方阵)

在这里插入图片描述

对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一维数组中，且也能找到每个非零元素和向量下标的对应关系。

4.稀疏矩阵

设在m*n的矩阵中有t个非零元素，令c=t/(m*n),当c<=0.05时称为稀疏矩阵。
压缩存储原则：存各非零元的值、行列位置和矩阵的行列数。

  • 顺序存储——三元组

在这里插入图片描述

  • 链式存储——十字链表法
    优点：它能够灵活得插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的运算。
    十字链表中结点的结构示意图：

在这里插入图片描述

image-20251027141026441

right:用于链接同一行中的下一个非零元素；
down:用于链接同一列中的下一个非零元素。

在这里插入图片描述