数据结构与算法-03-栈和队列

栈和队列

栈

基本概念

定义

栈 Stack 是只允许一端进行插入或删除操作的线性表
后进先出 LIFO
栈顶
- 允许插入和删除的一端
栈底
- 不允许插入和删除的一端
空栈

基本操作

创建 InitStack(&S)
- 初始化栈，分配内存空间
销毁 DestoryStack(&L)
- 销毁并释放内存空间
进栈 Push(&S, x) 增
- 栈未满加入元素使其成为栈顶
出栈 Pop(S, &x) 删
- 栈非空弹出栈顶元素
查找 Get(S,&x)
- 读取栈顶元素
  - 大部分场景只访问栈顶元素
常考进栈后合法的出栈顺序，记住后进先出
n 个不同元素进栈，出栈元素的不同排列的个数$\frac{1}{n+1}C^n_{2n} $ 该公式为卡特兰数

基本实现

顺序栈

缺点是栈的大小不可改变

 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


#define MaxSize 10  // 定义 栈中元素的最大个数

typedef struct{    
    ElemType data[MaxSize];  // 静态数组 存放 栈中元素
    int top;                 // 栈顶指针
}SqStack；
    
// 初始化 栈
void InitStack(SqStack &S){
    S.top = -1; // 初始化 栈顶指针
    // 另一种初始化 是 S.top = 0;
    // 对应第一种方式 S.data[S.top] 是无效的 要到data[0] 要先把 S.top + 1
    // 第二种方式  S.data[S.top] =  S.data[0] 
    // 所以 要 注意审题  题目中的 初始化不同 后续的出入站代码会有区别
}
    
// 判断 栈空
bool StackEmpty(SqStack S){
    if(S.top == -1)
        return true;
    else
        return false;
}

// 入栈 Push
bool Push(SqStack &S, ElemType x){
    if(S.top==MaxSize-1)
        return false;   // 栈满
	S.top = S.top + 1;  // 指针先 + 1
    S.data[S.top] = x;  // 新元素入栈
    // 指针+1 新元素入栈 两行 等价于 下面一行被注释的代码
    // S.data[++S.top] = x;
	return true;
}

// 出栈 Pop
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;
}

// 读取栈顶
bool GetPop(SqStack S, ElemType &x){
    if(S.top == -1)
        return false;
    x = S.data[S.top];  // 用 x 返回栈顶元素
    return true;
}


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

共享栈

两个栈共享同一片内内存空间
- 两个栈栈低拼接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


#define MaxSize 10

typedef struct{
    ElemType data[MaxSize];
    int top0;    // 0 号栈 栈顶
    int top1;    // 1 号栈 栈顶
}ShStack;

void InitStack(ShStack &S){
    S.top0 = -1;
    S.top1 = MaxSize;
}

销毁
- 静态分配：栈顶指针返回到初始化的位置
- 动态分配：先释放内存再返回指针

链式栈

类似于头插法单链表，链头作为栈顶，只不过只能在栈顶进行操作

TODO 使用带头结点和不带头结点的都需要会写

 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


// 带头结点的链式栈
// S.top 是 固定的头结点
typedef struct StackNode{
    ElemType *data;
    struct StackNode *next;
} StackNode;

typedef struct{
    StackNode *top;
}LinkStack;

bool InitLStack(LinkStack &S){
    S.top = (StackNode *)malloc(sizeof(StackNode));
    if(!S.top) return false;
    S.top->next = NULL;  
    return true;
}

bool Push(LinkStack &S, ElemType e){
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if(!p) return false;
    p->data = e;
    p->next = S.top->next; // 新结点 指向原来的栈顶
    S.top->next = p;       // 头结点 指向 新的栈顶
    return true;
}

bool Pop(LinkStack &S, ElemType &e){
    if(S.top->next==NULL) return false;
    StackNode *p = S.top->next;
    e = p->data;
    S.top->next = p->next;
    free(p);
    return true;
}

bool GetTop(LinkStack S, ElemType &x){
	if(S.top->next==NULL) return false;
    x = S.top->next->data;
    return true; 
}

bool DestroyStack(LinkStack &S) {
    // 1. 暂存头结点的后继（栈顶元素结点），作为遍历起点
    StackNode *p = S.top->next;
    // 2. 遍历释放所有数据结点（和不带头结点的遍历逻辑一致）
    while (p) {
        S.top->next = p->next; // 头结点指向当前结点的后继
        free(p);               // 释放当前数据结点
        p = S.top->next;       // 移动到下一个数据结点
    }
    // 3. 释放头结点（核心！不带头结点无此步骤）
    free(S.top);
    // 4. 栈顶指针置空（避免野指针，考研采分点）
    S.top = NULL;
    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
46
47
48
49
50


// 不带头结点的链式栈
// S.top 是 栈顶结点

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

typedef struct{
    StackNode *top;
}LinkStack;

bool InitLStack(LinkStack &S){
    S.top = NULL;  
    return true;
}

bool Push(LinkStack &S, ElemType e){
    StackNode *p = (StackNode *)malloc(sizeof(StackNode));
    if(!p) return false;
    p->data = e;
   	p->next = S.top;
    S.top = p;
    return true;
}

bool Pop(LinkStack &S, ElemType &e){
    if(S.top==NULL) return false;
    StackNode *p = S.top;
    e = p->data;
    S.top = p->next;
    free(p);
    return true;
}

bool GetTop(LinkStack S, ElemType &x){
	if(S.top==NULL) return false;  // 空栈判空
	x = S.top->data;
    return true;
}

bool DestroyStack(LinkStack &S) {
    StackNode *p = S.top;
    while(p) {
        S.top = p->next;
        free(p);
        p = S.top;
    }
    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
37
38


#define MaxSize 10

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

// 初始化栈
InitStack(SqStack &S)
// 判断栈是否为空
bool IsEmpty(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(IsEmpty(S))     // 扫描到右括号 且当前栈空
                return false   // 匹配失败
            
            char topElem;
            Pop(topElem);
            if(str[i]==')' && topElem!='(')
                return false;
            if(str[i]==']' && topElem!='[')
                return false;
            if(str[i]=='}' && topElem!='{')
                return false;
        }
    }
    return IsEmpty(S);       // 检索完全部括号后，栈空 说明匹配成功
}

TODO 不用基础操作，实现全部代码

栈的应用—表达式求值

三种算术表达式

中缀表达式
- 由操作数、运算符、界限符（必不可少的、反映计算的先后顺序）组成
- 规则：运算符在两个操作数中间，如 a+b

如何不用界限符也能准确表达运算顺序：

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

栈的应用—递归

函数调用的特点
- 最后被调用的函数最先执行结束 LIFO
函数调用栈（函数调用时需要一个栈来存储）：
- 调用返回地址
- 实参
- 局部变量
递归：把原始问题转化为属性相同，但规模较小的问题
递归调用时，函数调用栈可称为"递归工作栈” 每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应的信息
- 缺点：效率低，太多层递归可能会导致栈溢出：可能包含很多重复计算
- 可以自定义栈将递归算法改造成非递归算法

队列

定义

只允许在一端（队尾）进行插入(入队)，另一端（队头）进行删除(出队) 的线性表
特点：先进先出 FIFO

基本操作

顺序存储实现队列

 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
67
68
69


#define MaxSize 10

typedef strcut{
    Elemtype data[MaxSize];  // 用静态数组存放队列元素
    int front,rear;          //  队头指针和队尾指针
    // 为解决 牺牲一个存储空间 来判断 队满 还是队空
    // 第一种 方法
    int size;                // 记录队列当前长度 
    // 插入成功 size++
    // 删除成功 size--
    // 用size判断 队满（size==MaxSize） 和 队空(size==0)
    // 第二种 方法
    int tag;              // 用于记录 最近进行的操作是 删除还是插入
    // 每次删除操作成功，tag =0;
    // 每次插入操作成功，tag =1;
    // 队满条件  front == rear && tag==1
    // 队空条件 front == rear && tag==0
    
} SqQueue;

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

// 以下代码是基于 队尾指针 指向 队尾元素下一个位置
// 根据 题目要求不同 如 队尾指针就是指向 队尾元素 相关操作代码要改变
// 初始化时  rear = MaxSize-1

// 入队操作
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;
}

// 出队操作
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;
}

// 查找操作 获取队头元素
bool GetHead(SqQueue Q, ElemType &x){
    if(Q.rear==Q.front)  // 判断 队列为空
        return false
	x = Q.data[Q.front]
    return true;
}

// 队列的元素 个数 计算：（rear + MaxSize - front) % MaxSize



void testQueue(){
    SqQueue Q; // 声明一个队列
    InitQueue(Q); // 初始化队列
    //...
}

TODO: 以下6中情况分别分析

rear指向队尾元素下一个位置
- 牺牲一个存储单元
- 增加size变量记录队列长度
- 增加tag变量用于记录近一次操作是删/插
rear 指向队尾元素
- 牺牲一个存储单元
- 增加size变量记录队列长度
- 增加tag变量用于记录近一次操作是删/插

链式存储实现队列

一般情况下链式队列不易出现队满的情况，除非内存不足
要注意题目中是带头结点还是不带头结点
数据操作要注意边界条件，以及处理第一个/最后一个元素入/出队的情况

带头结点

 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


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 IsEmpty(LinkQueue Q){
    if(Q.fornt==Q.rear)
        return false;
    else
        return true;
}

// 入队操作
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;        // 修改表尾指针
}

// 出队操作
bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear==p)   // 最后一个结点 出队
        Q.rear=Q.front;
    free(p);
    return ture;
}


void test(){
    LinkQueue Q;
    InitQueue(Q);
}

不带头结点

 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


typedef struct LinkNode{  // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;

typedef struct{   // 链式队列
    LinkNode *front, *rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    // 初始化时 front rear 都指向头结点
    Q.front = NULL;
    Q.rear = NULL;

}

bool IsEmpty(LinkQueue Q){
    if(Q.front==NULL)
        return true;
    else retrun false;
}

// 入队操作
void EnQueue(LinkQueue &Q, Elemtype x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if(Q.frong==NULL){  // 空队列中插入第一个元素
        Q.front = s;    // 修改头尾指针 
        Q.rear = s;
    }esle{
        Q.rear->next = s;
        Q.rear = s;
    }
    Q.rear->next = s;  // 新结点 插入到 rear 之后 
    Q.rear = s;        // 修改表尾指针
}

// 出队操作
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.rear=NULL;
        Q.front=NULL;
    free(p);
    return ture;
}

如果需要知道队列长度
- 可循环遍历队列
- 或经常访问队列长度时增加一个 length 变量记录，当前队列长度

双端队列

只允许从两端插入、两端删除的线性表
- 输入受限的双端队列
  - 只允许一端插入、两端删除
- 输出受限的双端队列
  - 只允许两端插入、一端删除

考点

判断输出序列的合法性

类似于栈中判断输出序列合法性的判断

队列应用

树的层次遍历
图的广度优先遍历
操作系统中的应用
- 多个进程争抢使用有限资源时 FCFS 先来先服务

特殊矩阵的压缩存储

数组的存储结构

数据各个元素大小相同，且物理上连续存储
除特别说明，否则数组下标默认从0开始

一维数组

数据元素 a[i]的存放地址 = LOC + i* sizeof(ElemType)
- LOC 为起始地址

二维数组

M行N列的二维数组 b[M][N]中

物理结构
- 行优先存储
  - b[i][j]的存储地址 = LOC+(i*N+j)*sizeof(ElemType)
- 列优先存储
  - b[i][j]的存储地址 = LOC+(i+j*N)*sizeof(ElemType)

普通矩阵的存储

注意
- 描述矩阵元素时，行、列通常从1开始
- 而描述数组时通常下标从0开始
- 具体看题目所给条件，注意审题
可用二维数组存储

特殊矩阵

对称矩阵

定义
- 若n阶方阵中任意一个元素 $a{_i},{_j}$
  - 都有 $a{_i},{_j} = a{_j},{_i}$
压缩存储策略
- 只存储主对角线和下/上三角区
- 按行优先原则将各元素存入一维数组中
  - 下三角区 $i>=j$
  - 数组大小：$\frac{n*(n+1)}{2}-1$ ，数组下标从0开始
  - $a{_i},{_j}$ 是第几个元素？
    - $\frac{i*(i+1)}{2}+j$ 个元素
    - 数组下标 $k =\frac{i*(i+1)}{2}+j-1$
  - 数组下标 k
    - 下三角区 $k =\frac{i*(i+1)}{2}+j-1$
    - 上三角区 $k =\frac{j*(j+1)}{2}+i-1$
- 按列有限原则
  
  数组下标 k
  - 下三角区 $k =\frac{j*(2n-j+1)}{2}+(i-j)$
  - 上三角区 $k =\frac{i*(2n-i+1)}{2}+(j-i)$

三角矩阵

上三角矩阵

除了对角线和上三角区，其余元素都相同为常量c

下三角矩阵

除了对角线和下三角区，其余元素都相同为常量c

压缩存储策略

按行优先原则，将主对角线和上/下三角区的元素存入一维数组
- 并在最后一个位置存储常量c

三对角矩阵

也叫带状矩阵
当 $|i-j|>1$时，有 $a{_i},{_j}=0$ (i>=1, j<=n)
- 主对角线元素是非零元素，且主对角线的上下左右的元素是非零元素，其余元素都是0
压缩存储策略
- 一共要存放 3n-2个元素，最后一个元素的数据下标是 3n-3
- 按行优先原则，只存储非零元素
  - $a{_i},{_j}$ |i-j|<=1 时

稀疏矩阵

非零元素的个数远远少于矩阵元素的个数
压缩存储策略
- 三元组<行，列，值>

栈 和 队列

栈

基本概念

定义

基本操作

基本实现

顺序栈

链式栈

栈 的应用—括号匹配问题

栈的应用—表达式求值

三种算术表达式

栈的应用—递归

队列

定义

基本操作

顺序存储实现队列

链式存储实现队列

带头结点

不带头结点

双端队列

考点

判断输出序列的合法性

队列应用

特殊矩阵的压缩存储

数组的存储结构

一维数组

二维数组

普通矩阵的存储

特殊矩阵

对称矩阵

三角矩阵

上三角矩阵

下三角矩阵

压缩存储策略

三对角矩阵

稀疏矩阵

栈和队列

栈的应用—括号匹配问题