数据结构 栈和队列

第3章栈和队列

3.1栈

3.2队列

本章小结2023/2/11/403.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算的实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用3.1栈（Stack）

a1a2a3a4a5a6插入xi删除xj插入删除2023/2/12/40栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的当前位置是动态的，由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为压栈或进栈，栈的删除操作通常称为退栈或出栈。栈的主要特点是“后进先出”。也称为后进先出表。3.1.1栈的定义

2023/2/13/40a1a2a3入栈栈底栈顶插入：入栈、进栈、压栈栈顶栈顶栈的操作示意图2023/2/14/40后进先出a1a3入栈出栈栈底栈顶删除：出栈、退栈、弹栈栈顶栈的操作示意图a2栈顶2023/2/15/40【例3.3】设一个栈的输入序列为A,B,C,D，则借助一个栈所得到的输出序列不可能是

。

(A)A,B,C,D(B)D,C,B,A(C)A,C,D,B(D)D,A,B,C

答案：D【例3.1】若元素进栈顺序为1-2-3-4，能否得到3142的出栈顺序？答案：否【例3.2】用S表示进栈操作，X表示出栈操作，若元素进栈顺序为1234，为了得到1342的出栈顺序，给出相应的S和X操作串。答案：SXSSXSXX2023/2/16/40抽象数据类型栈的定义：《教材P65》基本运算：InitStack(&s)：初始化栈，构造一个空栈s。DestroyStack(&s)：销毁栈，释放栈s占用的存储空间。StackEmpty(s)：判断栈是否为空：为空，则返回真；否则返回假。Push(&s,e)：进栈，将元素e插入到栈s中作为栈顶元素。Pop(&s,&e)：出栈，从栈s中退出栈顶元素，将其值赋给e。GetTop(s,&e)：取栈顶元素，返回当前的栈顶元素，并将其值赋给e。2023/2/17/403.1.2栈的顺序存储结构及其基本运算的实现

假设栈的元素个数最大不超过正整数MaxSize，所有元素都具有同一数据类型ElemType，则可用下列方式来定义顺序栈类型SqStack:

typedef

struct{

ElemType

data[MaxSize]；

inttop；//栈顶指针

}SqStack；2023/2/18/40栈空条件：top==-1

栈满条件：top==MaxSize-1

进栈操作：top++;再将元素放在top处退栈操作：从top处取出元素，再将top--;例如：2023/2/19/40在顺序栈中实现栈的基本运算算法:(1)初始化栈InitStack(s)：s->top=-1;(2)销毁栈DestroyStack(s)：

free(s);(3)判断栈是否为空StackEmpty(s)：

s->top==-1(4)进栈Push(s,e)：s->top++;s->data[s->top]=e;(5)出栈Pop(s,e)：e=s->data[s->top];s->top--;(6)取栈顶元素GetTop(s,e)：e=s->data[s->top];注意栈空、栈满的条件！2023/2/110/40【例3.4】编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。串1：abcba串2：abcdabool

symmetry(ElemType

str[]){………}for(i=0;str[i]!=‘\0’;i++)

Push(st,str[i]);for(i=0;str[i]!=‘\0’;i++){

Pop(st,e);if()……}2023/2/111/403.1.3栈的链式存储结构及其基本运算的实现链栈的优点是不存在栈满的情况。链式栈的栈顶在链表的表头，规定栈的所有操作都是在单链表的表头进行的。

链栈中数据结点的类型LiStack定义如下:

typedef

struct

linknode{

ElemTypedata;

struct

linknode*next;}LiStack;

栈空条件：s->next==NULL

栈满条件：不考虑进栈操作：在头结点之后插入退栈操作：删除头结点之后的数据结点2023/2/112/40在链栈中的基本运算算法:^ssa1a2an…(1)初始化栈InitStack(s)(2)销毁栈DestoryStack(s)(3)判断栈是否为空StackEmpty(s)(4)进栈Push(s,e)

(5)出栈Pop(s,e)

(6)取栈顶元素GetTop(s,e)pe2023/2/113/40【例3.5】编写一个算法判断输入的表达式中的括号是否正确配对。（假设只含有左、右圆括号）算法思路：

设置一个括号栈，扫描表达式：遇到左括号进栈，遇到右括号，若栈顶是左括号，则出栈。否则返回false。当表达式扫描完毕，栈为空时返回true——表示括号正确匹配，否则返回false。①((3+5)*2-3)/2②((3+5)*2-3/2③(3+5)*2-3)/22023/2/114/403.1.4栈的应用回文验证括号匹配检验表达式求值迷宫问题递归（ch5）数制转换行编辑程序2023/2/115/401.表达式求值【问题描述】用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式，计算该表达式的运算结果。一个表达式由操作数（亦称运算对象）、操作符（亦称运算符）和分界符组成。算术表达式有三种表示：中缀(infix)表示

<操作数><操作符><操作数>，如A+B；前缀(prefix)表示

<操作符><操作数><操作数>，如+AB；后缀(postfix)表示

<操作数><操作数><操作符>，如AB+；2023/2/116/40中缀表达式

a+b*(c-d)-e/f后缀表达式abcd-*+ef/-前缀表达式

-+a*b–cd/ef编译程序一般使用后缀表示求解表达式的值！问题：中缀表示如何转换为后缀表示？把每个运算符都移到它的两个运算对象的后面，然后删除掉所有的括号即可。中缀表达式

(A+B)*D-E/(F+A*D)+C后缀表达式

AB+D*EFAD*+/-C+2023/2/117/40假设用exp字符数组存储算术表达式，其对应后缀表达式存放在字符数组postexp中。在将算术表达式转换成后缀表达式的过程中用一个字符数组op作为运算符栈。具体步骤如下:初始化运算符栈op，将“=”进栈作为栈底元素。while(从exp读取字符ch，ch!='\0'){

若ch为数字，将后续所有数字依次存放到postexp中，并以字符“#”标志数值串结束。

若ch为左括号“(”，则将此括号进栈到运算符栈op中。

若ch为右括号“)”，则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中，然后将左括号“(”删除。

若ch运算符优先级小于op栈顶运算符优先级，则依次出栈并存入到postexp中。

若ch运算符优先级大于op栈顶运算符优先级，将ch进栈。}若字符串exp扫描完毕，则将运算符栈op中“=”之前的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。2023/2/118/40a+bcd/ef`\0`exppostexp+abcdef运算符栈opchchchchchch-/2023/2/119/40表达式“(56-20)/(4+2)”转换成后缀表达式的过程：2023/2/120/40后缀表达式求值从左向右顺序扫描表达式的每一项，根据它的类型做如下相应操作：如果该项是操作数，则将其压入数值栈中；如果该项是操作符op，则连续从栈中退出两个操作数Y和X，形成运算指令XopY，并将结果重新压入栈中。当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。【例】计算56#20#-4#2#+/

(56–20)/(4+2)2023/2/121/40【问题描述】给定一个M×N的迷宫图，求一条从指定入口到出口的路径。2.求解迷宫问题图中每个方块，空白表示通道，阴影表示墙。所求路径必须是简单路径，即在求得的路径上不能重复出现同一通道块。

2023/2/122/403.2队列

3.2.1队列的定义3.2.2队列的顺序存储结构及其基本运算的实现3.2.3队列的链式存储结构及其基本运算的实现3.2.4队列的应用3.2.5双端队列2023/2/123/40队列（Queue）简称队，它也是一种运算受限的线性表，其限制为仅允许在表的一端进行插入，在另一端进行删除。把进行插入的一端称做队尾（rear），进行删除的一端称做队首（front）。向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。3.2.1队列的定义

特点：先进先出(FIFO,

FirstInFirstOut)a0

a1

a2

an-1frontrear2023/2/124/40队列的基本运算：InitQueue(&q)：初始化队列。构造一个空队列q。DestroyQueue(&q)：销毁队列。释放队列q占用的存储空间。QueueEmpty(q)：判断队列是否为空。若队列q为空，则返回真；否则返回假。enQueue(&q,e)：进队列。将元素e进队作为队尾元素。deQueue(&q,&e)：出队列。从队列q中出队一个元素，并将其值赋给e。【例3.6】若元素进队顺序为1-2-3-4，能否得到3142的出队顺序？答案：否2023/2/125/40

3.2.2队列的顺序存储结构及其基本运算的实现假设队列的元素个数最大不超过整数MaxSize，所有元素都具有同一数据类型ElemType，则顺序队列类型SqQueue定义如下:

typedef

struct{

ElemType

data[MaxSize];

int

front,rear;//队首和队尾指针}SqQueue;

初始时，设front=rear=-1。

rear指向队尾；front指向队首的前一个位置。2023/2/126/401.基于顺序存储的队列的基本运算frontrearA入队AfrontrearB入队ABfrontrearC,D入队ABCDfrontrearA出队BCDfrontrearB出队CDfrontrearE,F,G入队CDEFGCDEFGfrontrearH入队,“溢出”frontrear空队列MaxSize-12023/2/127/40基于顺序存储队列的基本运算初始化队列：销毁队列：队空条件：队满条件：入队操作：出队操作：解决假溢出的办法之一：将存放队列元素的数组首尾相接，形成一个循环（环形）队列。front==rearrear==MaxSize－1front=rear=-1free(q);先将队尾指针加1，再将新元素加入该位置。

——队尾指针指示实际队尾的位置。先将队头指针加1，再取出该位置元素。——队头指针指示实际队头位置的前一位置。队满时再入队将溢出（“假溢出”）。队空时出队需要进行队空处理。2023/2/128/40rear

0

1

2

3

4

front

(a)空队

(b)a,b,c入队

rear

0

1

2

3

4

front

a

b

c

队满rear

0

1

2

3

4

a

b

c

d

front

(c)d入队,rear

0

1

2

3

4

c

d

front

(d)出队2次

rear

0

1

2

3

4

front

(e)出队2次,队空

2.环形队中实现队列的基本运算2023/2/129/40环形队列首尾相连，当队首指针front满足front==MaxSize-1后，再前进一个位置就自动到0，可以利用求余运算（%）来实现。队首指针进1：front=(front+1)％MaxSize队尾指针进1：rear=(rear+1)％MaxSize指针初始化：front=rear=0队满条件:(q->rear+1)%

MaxSize==q->front队空条件:q->rear==q->front注意：环形队列最多存放MaxSize-1个元素！问题：如何求环形队列中的元素个数？2023/2/130/40已知front、rear，求count：

已知front、count，求rear：

已知rear、count，求front：

count=4count=3MaxSize＝5【例3.7】对于环形队列来说，如果知道队头指针和队列中元素个数，就可以计算出队尾指针。也就是说，可以用队列中元素个数代替队尾指针。设计出这种环形队列的初始化、入队、出队和判空算法。count=(rear-front+MaxSize)%MaxSizerear=(front+count)%MaxSizefront=(rear-count+MaxSize)%MaxSize2023/2/131/40解:已知队头指针front和队列中元素个数count。环形队列的类型定义如下:

typedef

struct{

ElemType

data[MaxSize];

intfront; //队首指针

intcount; //队列中元素个数}QuType;count==0count==MaxSizerear=(front+count)%MaxSize队空的条件：队满的条件：队尾指针rear：初始化：入队：出队：判空：rear=(q->front+q->count+MaxSize)%MaxSize;rear=(rear+1)%MaxSize;q->data[rear]=x;q->count++;q->front=(q->front+1)%MaxSize;x=q->data[q->front];q->count--;2023/2/132/403.2.3队列的链式存储结构及其基本运算的实现队列的队首指针指向单链表的第一个结点，队尾指针指向单链表的最后一个结点。只允许在单链表的表头进行删除操作、在单链表的表尾进行插入操作。链式队列特别适合于数据元素变动比较大的情形。在进队时无队满问题，但有队空问题。frontrear链队中数据结点的类型QNode定义如下:typedef

struct

qnode{

ElemTypedata;

struct

qnode*next;}QNode;链队中头结点的类型LiQueue定义如下:typedef

struct{

QNode*front;

QNode*rear;}LiQueue;

2023/2/133/40链队的入队和出队操作示意图

∧

∧

front

rear

q

(a)链队初态

front

rear

q

(b)入队3个元素

a

b

∧

c

front

rear

q

(c)出队1个元素

b

∧

c

2023/2/134/40链队存储中的基本运算算法(1)初始化队列InitQueue(q)：(2)销毁队列DestroyQueue(q