数据结构(三)——栈与队列


定义

线性表是具有相同数据类型的n个数据元素的有限序列

栈(Stack)是只允许在一端进行插入或删除操作的线性表(操作受限的线性表)。

相关术语:

  • 栈顶:允许插入和删除的一端
  • 栈底:不允许插入和删除的一端

特点

特点:后进先出

栈的基本操作

  • InitStack(&S):初始化栈。构成一个空栈S,分配内存空间。
  • DestroyStack(&L):销毁栈,销毁并释放栈S所占用的内存空间。
  • Push(&S,x):进栈,若栈S未满,则将x加入使之成为新堆栈。
  • Pop(&S,&x):出栈,若栈S非空,则弹出栈顶元素,并用x返回。
  • GetTop(S,&x):读栈顶元素。若栈非空,则用x返回栈顶元素。
  • StackEmpty(S):判断一个栈S是否为空。若S为空,则返回true,否则返回false。

卡特兰数

卡特兰数公式可以帮助我们快速得出一个栈结构有多少种合法的出栈序列:

顺序栈

定义

用顺序存储方式实现的栈

基本操作

顺序栈的定义

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

栈顶指针一般来说记录的是数组的下标,即一般是从0开始的。

顺序栈的初始化

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

判断栈空

1
2
3
4
5
6
7
//判断栈空
bool StackEmpty(SqStack S){
if(S.top==-1)
return true;
else
return false;
}

新元素入栈

1
2
3
4
5
6
7
//新元素入栈
bool Push(SqStack &S,ElemType x){
if(S.top==MaxSize-1) //栈满,报错
return false;
S.data[++S.top]=x; //新元素入栈
return true;
}

元素出栈

1
2
3
4
5
6
7
//出栈操作
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1) //栈空,报错
return false;
x=S.data[S.top--]; //栈顶元素先出栈
return true;
}

得到栈顶元素

1
2
3
4
5
6
7
//读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top==-1) //栈空,报错
return false;
x=S.data[S.top]; //x记录栈顶元素
return true;
}

这里我们的设计是让栈顶指针指向了栈的最上面的元素的数组下标(类似于处理器中的SP寄存器——堆栈指针,是时刻指向最上面的元素的),其实往往还有另一种设计思路是让栈顶指针指向最上面的元素的下一个位置,如上的代码就都要有所改动,这里不再赘述。

共享栈

为了提高空间利用率,还可以在一个结构体中设计两个指针,一个初始化时指向-1,另一个指向MaxSize,一个从上往下、一个从下往上,判断栈满就判断两个指针是否即将相遇即可。

链栈

定义

用链式存储方式实现的栈

基本操作

定义

1
2
3
4
5
6
7
8
9
#include <stdio.h>
#include<stdlib.h>

typedef int ElemType;

typedef struct LNode{
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一个结点
}LNode,*LinkList;

初始化(不带头结点)

1
2
3
4
5
6
//初始化一个空的单链表
bool InitList(LinkList &L){
L=NULL; //空表,暂时还没有任何结点
return true;
}

入栈操作(不带头结点)

1
2
3
4
5
6
7
8
9
bool Push(LinkList &L,ElemType e){
LNode *s=(LNode *)malloc(sizeof(LNode));
if(s==NULL) //空间分配失败
return false;
s->data=e;
s->next=L;
L=s;
return true;
}

出栈(不带头结点)

1
2
3
4
5
6
7
8
//出栈
bool Pop(LinkList &L,ElemType &e){
if(!L) //如果栈为空
return false;
e=L->data;
L=L->next;
return true;
}

其他操作并不难,就请读者自行实现。


队列

队列的定义

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

相关术语:

  • 队头:允许插入的一端
  • 队尾:允许删除的一端
  • 空队列:没有元素的队列

特点

特点:先进先出

队列的基本操作

  • InitQueue(&Q):初始化队列,构造一个空队列Q。
  • DestroyQueue(&Q):销毁队列。销毁并释放队列Q所占用的内存空间。
  • EnQueue(&Q,x):入队,若队列Q未满,将x加入,使之成为新的队尾。
  • DeQueue(&Q,&x):出队,若队列Q非空,删除队头元素,并用x返回。
  • GetHead(Q,&x):读队列元素,若队列Q非空,则将队头元素赋值给x。

顺序队列

定义

用顺序存储方式实现的队列。

基本操作

队列的顺序实现

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

初始化

1
2
3
4
void InitQueue(SqQueue &Q){
//初始时,队头、队尾指针指向0
Q.rear=Q.front=0;
}

我们的设计中,通常队头指针是指向队头元素;队尾指针则是指向即将添加的位置。

判空

1
2
3
4
5
6
bool QueueEmpty(SqQueue Q){
if(Q.rear==Q.front)
return true;
else
return false;
}

入队操作

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; //队尾指针后移
return true;
}

我们的队列需要利用取余操作使得队尾指针回到前面的内存中,从而确保出队后的前面的空间也可以被很好地利用。

另外,这边相信你也看出来了,我们的牺牲掉了一个空间不存放数据来方便判满,为什么不让front和rear指向一处来判满呢?因为这样就和判空的条件一样了,从而不能正确地实现逻辑。

如果要求不浪费该存储空间,则可以在顺序队列的定义时附加一个size变量来记录长度,当rear等于front时,size为MaxSize则队满,size为0则队空。

又或者可以定义个tag标记变量,每次删除操作成功时,令tag为0,;每次插入操作成功时,令tag为1。当rear等于front,通过tag的最后一次操作即可知道队列是满还是空

出队操作

1
2
3
4
5
6
7
8
//出队(删除一个队头元素,并用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
bool GetHead(SqQueue Q,ElemType &x){
if(Q.rear==Q.front)
return false; //队空则报错
x=Q.data[Q.front];
return true;
}

如果我们想要计算队列中元素的个数:
(rear+MaxSize-front)%MaxSize

链队列

定义

用链式存储方式实现的队列。

基本操作

定义

1
2
3
4
5
6
7
8
9
10
11
12
#include <stdlib.h>

typedef int ElemType;

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

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

初始化队列(带头结点)

1
2
3
4
5
6
//初始化队列(带头结点)
void InitQueue(LinkQueue &Q){
//初始时,front、rear都指向头结点
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
Q.front->next=NULL;
}

判空(带头结点)

1
2
3
4
5
6
bool IsEmpty(LinkQueue Q){
if(Q.front==Q.rear)
return true;
else
return false;
}

初始化队列(不带头结点)

1
2
3
4
5
6
//初始化队列(带头结点)
void InitQueue(LinkQueue &Q){
//初始时,front、rear都指向NULL
Q.front=NULL;
Q.rear=NULL;
}

判空(不带头结点)

1
2
3
4
5
6
bool IsEmpty(LinkQueue Q){
if(!Q.front)
return true;
else
return false;
}

入队(带头结点)

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;
Q.rear->next=s; //新结点插入到rear之后
Q.rear=s; //修改表尾指针
}

这里可以看出,我们的案例中,顺序队列里rear尾指针是指向下一个待插空间的;而链队列里rear尾指针是指向最后一个元素的

入队(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
//入队
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;
}

front永远指向头结点

出队(不带头结点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//出队
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==NULL)
return false; //空队
LinkNode *p=Q.front;
x=p->data; //用变量x返回队头元素
Q.front=p->next;
if(Q.rear==p){
Q.rear=NULL;
Q.front=NULL;
}
free(p); //释放结点空间
return true;
}

栈的应用

括号匹配问题

定义

分析一串字符串中的“()”、“[]”、“{}”是否成双出现。

我们通过分析可以发现两个括号分析的特点:

  1. 最后出现的左括号最先被匹配
  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
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(str[i]==')'||str[i]==']'||str[i]=='}'){
if(StackEmpty(S)) //扫描到右括号,且当前栈空
return false;

ElemType topElem;
Pop(S,topElem); //栈顶元素出栈
if(str[i]==')'&&topElem!='(')
return false;
if(str[i]==']'&&topElem!='[')
return false;
if(str[i]=='}'&&topElem!='{')
return false;
}
}
}
return true;
}

表达式求值

三种算术表达式

表达式:表达算术运算的式子,往往由三个部分组成:操作数、运算符、界限符

  • 中缀表达式:即普通的表达式。运算符在两个操作数的中间。中缀表达式中界限符(即括号)是必要的,表明了计算优先顺序。
  • 后缀表达式:又称逆波兰表达式。运算符在两个操作数的后面。
  • 前缀表达式:又称波兰表达式。运算符在两个操作数的前面。

逆波兰表达式/波兰表达式换算

以逆波兰表达式为例,将当前运算中的运算符移至右边,如此往复:

  1. 确定中缀表达式中各个运算符的运算顺序
  2. 选择下一个运算符,按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
  3. 如果还有运算符没有被处理,则重复2

如:a+b-c*d –> ab+cd*-

注意:严格意义上后缀表达式并不唯一,如下图所示,为了确保算法的“唯一性”,我们默认转换表达式时,只要左边的运算符能被先运算,就优先从左运算(左优先原则),如果是前缀表达式,则遵循右优先原则

后缀表达式运算(用栈实现)

  1. 将数1加入栈
  2. 将数2加入栈
  3. 遇到符号,将数1、数2取出和符号运算,然后将运算结果放入栈作新的数1
  4. 如此往复

计算机更适合用后缀表达式去计算,故很多基于栈的编程语言:Forth、PostScribe都是用后缀表达式来运算的

中缀表达式转后缀表达式(用栈实现)

主要思路:

  1. 初始化一个栈,用于保存暂时还不确定运算顺序的运算符。
  2. 从左到右处理各个元素,直到末尾。可能遇到三种情况:
    1. 遇到操作数,直接加入后缀表达式。
    2. 遇到界限符,遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式,知道弹出“(”为止。注意:“(”不加入后缀表达式。
    3. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符,并加入后缀表达式。若碰到“(”或栈空则停止。之后再把当前运算符入栈。
  3. 按上述方法处理完所有字符后,将栈中剩余运算符依次弹出,并加入后缀表达式。

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

前面我们了解过利用栈来进行后缀表达式的计算,可以发现很简单,也正因如此说计算机更适合用后缀表达式运算,现在我们来了解一下用中缀表达式计算,其实也就是上面两个算法的集合。


  1. 初始化两个栈,操作数栈和运算符栈。
  2. 若扫描到操作数,压入操作数栈。
  3. 若扫描到运算符或者界限符,则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符,每弹出一个运算符时,就需要再弹出两个操作数栈的栈顶元素并执行相应运算,运算结果再压回操作数栈)
  4. 扫描完成后,弹出运算符栈的所有运算符,每弹出一个,就弹出两个操作数进行运算。

栈与递归

函数调用的背后

函数调用时,需要一个栈存储:

  1. 调用返回地址:函数执行完成后返回的地址,即调用函数的那条语句的下一条语句的地址。当程序返回后,调用函数的语句的下一条语句就会被执行(地址被赋给CS、IP寄存器,即将被CPU执行)
  2. 实参:调用函数传来的参数,这两个参数放在栈中被临时保存,这也就是为什么一般传参是“值传递”,因为子函数下的参数是栈中的“临时数据”
  3. 局部变量:子函数中定义的局部变量,在子函数执行完成后会被回收。

递归调用时,函数调用栈可称为“递归工作栈”

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

栈在递归中的应用

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

递归缺点:太多层递归可能会导致栈溢出

递归缺点:递归可能会包含很多重复计算

队列的应用

双端队列

定义

只允许从两端插入、两端删除的线性表

延伸出更多的变种:

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

关于这种问题只要知道哪种输出顺序是可能实现的即可,这里不再赘述

树的层次遍历

遍历规则

  1. 将树的头结点放入队列。
  2. 从队头中拿出当前结点,将其子节点(如果有的话)插入队尾
  3. 重复2,即可遍历树的全部结点

图的广度优先遍历

遍历规则

  1. 将某个结点放入队列
  2. 从队头中拿出当前结点,检查当前结点相邻的结点有没有遍历过,将没有遍历过的结点插入队尾
  3. 重复2,即可遍历图的全部结点

应用于操作系统————先来先服务

介绍

多个进程争抢着有限的系统资源时,FCFS(First Come First Service,先来先服务)是一种常用策略。

矩阵的压缩存储

数组的存储结构

一维数组的存储结构

各数组元素大小相同,且物理上连续存放。

以0为起始下标的数组元素a[i]的存放地址:LOC+i*sizeof(ElemType);

二维数组的存储结构

在逻辑上,我们的二维数组是像一个表格一样存储的;但是在实际内存中,存储只能是线性的,一般有两种方法:

  1. 行优先存储:将二维数组按行优先一行一行地存储。
  2. 列优先存储:将二维数组按列优先一列一列地存储。

若按行优先存储,则M行N列的二维数组中,以0为起始下标的数组元素a[i][j]的存放地址:LOC+(i*N+j)*sizeof(ElemType);若是列优先,则:LOC+(j*M+j)*sizeof(ElemType)

矩阵存储

普通矩阵

对于普通的矩阵,我们往往利用二维数组来存储。

对于下面的特殊矩阵,我们就可以利用特殊的存储方式来压缩存储空间

对称矩阵

若n阶方阵中任意一个元素aij都有aij=aji,则该矩阵为对称矩阵。

压缩存储策略:只存储主对角线+下三角区(或主对角线+上三角区,我们以前者为例)

我们按照行优先原则将各元素存入一维数组。

即我们是n阶矩阵,则我们的数组存储总大小应该是:(1+n)*n/2。

我们需要来创建一个映射函数,来将矩阵的下标映射为一维数组里的某个元素。

根据行优先原则,我们可以推出:

  • 当i>=j时,aij对应的一维数组的是第[1+2+……+(i-1)]+j个元素,即(i-1)*i/2+j个元素(这里是位序,如果按下标去考虑则还要减一)。
  • 当i<j时,我们可以利用对称矩阵的性质,将aij转换为aji

三角矩阵

以下三角矩阵为例:除了主对角线和下三角区,其余的所有元素都是一个常数。

压缩存储策略:按行优先原则将主对角线和下三角区域存放在一维数组中。并在最后一个位置存储常数C。

即相比于对称矩阵来说,我们需要多一个存储单元

下面我们来思考映射思路:

根据行优先原则,我们可以推出:

  • 当i>=j时,aij对应的一维数组的是第[1+2+……+(i-1)]+j个元素,即(i-1)*i/2+j个元素(这里是位序,如果按下标去考虑则还要减一)。
  • 当i<j时,位序直接就是n*(n+1)/2+1。

在三角矩阵的存储中,我们还需要考虑一下上三角矩阵的情况:
即当i<=j时,访问元素aij的话,前面的行(即第1行至i-1行)共有n+(n-1)+……+(n-i+2)个元素(第1行n个、第2行n-1个,数字规律推得第(n-1)行有(n-i+2)个元素),而第i行的第j个元素在一维数组中是这行的第(j-i)+1个元素,故:

  • 当i<=j,k=(i-1)*(2n-i+2)/2+(i-j)+1(这里是位序)
  • 当i>j,k=(n+1)*n/2+1

三对角矩阵

三角矩阵,又称带状矩阵:
当[i-j]>1时,有aij=0(i<=i,j<=n)

由图可知,除了第一行和最后一行,其他每一行有效元素都是三个,故我们的一维数组总长度就是:3*n-2。

下面我们来考虑映射思路:
按行优先原则,aij是第几个元素?
前i-1个行共3*(i-1)-1个元素;aij是第i行第j-i+2个元素;故aij是2*i+j-2个元素。

稀疏矩阵

非零元素远远小于矩阵元素的个数。

压缩存储策略:

  • 顺序存储——三元组<行,列,值>
  • 链式存储——十字链表法





商业转载 请联系作者获得授权,非商业转载 请标明出处,谢谢