数据结构--3章栈和队

《数据结构--3章栈和队》由会员分享，可在线阅读，更多相关《数据结构--3章栈和队（35页珍藏版）》请在装配图网上搜索。

1、2021/3/111 2010-7-21 数据结构2021/3/112 第三章 栈和队列引言：对线性表 L=(a1,a2,.,an),可在任意第i(i=1,2,.n,n+1)个位置插入新元素，或删除任意第i(i=1,2,.n)个元素 受限数据结构-插入和删除受限制的线性表。1.栈(stack),2.队列(queue).3.1栈(stack)3.1.1栈的定义和操作 1.定义和术语 栈-限定在表尾作插入、删除操作的线性表。(a1,a2,.，an）插入元素(进栈)删除元素(出栈）表头 表尾 (栈底)(栈顶）2021/3/113 an a1栈顶(top)栈底(bottom)出栈(pop)进栈(pus

2、h)进栈-插入一个元素到栈中。或:入栈、推入、压入、push。出栈-从栈删除一个元素。或：退栈、上托、弹出、pop。栈顶-表中允许插入、删除元素的一端(表尾)。栈顶元素-处在栈顶位置的元素。栈底-表中不允许插入、删除元素的一端。空栈-不含元素的栈。栈的示意图2021/3/114 栈的元素的进出原则:“后进先出”,“Last In First Out”。栈的别名:“后进先出”表、“LIFO”表、反转存储器、地窖。2021/3/1152.栈的基本操作(1)Initstack(s)-置s为空栈。(2)Push(s,e)-元素e进栈s。若s已满，则发生溢出。若不能解决溢出，重新分配空间失败，则插入失败

3、。(3)Pop(s,e)-删除栈s的顶元素，并送入e。若s为空栈,发生“下溢”(underflow)；为空栈时，表示某项任务未开始或已完成。(4)Gettop(s,e)-栈s的顶元素拷贝到e。若s为空栈，则结束拷贝。(5)Empty(s)-判断s是否为空栈。若s为空栈,则Empty(s)为true；否则为false。2021/3/116(1)输入A,B,C,产生输出A,B,C的过程：A B,C(1)A进栈 B,C(2)A出栈 B C(3)B进栈 (4)B出栈 C(5)C进栈 (6)C出栈CA,B,CAA,BA,BA2021/3/117(2)输入A,B,C,产生输出C,B,A的过程：A B,C(

4、1)A进栈 B A C(2)B进栈 C B A(3)C进栈 B A(4)C出栈 C(5)B出栈 (6)A出栈C,B,ACC,B2021/3/118(3)输入A,B,C,产生输出B,C,A的过程:A B,C(1)A进栈 B A C(2)B进栈 A C(3)B出栈 C A(4)C进栈 A(5)C出栈 (6)A出栈B,C,ABB,CB2021/3/119 当A,B,C依次进栈，C出栈后，由于栈顶元素是B,栈底元素是A,而A不能先于B出栈,所以不能在输出序列中,使A成为C的直接后继,即不可能由输入A,B,C产生输出C,A,B。一般地，输入序列(.,ai,.,aj,.,ak,.)到栈中,不能得到输出序列

5、(.,ak,.,ai,.,aj,.)。(1)初始状态 C B A(2)A,B,C进栈 B A(3)C出栈CA,B,C(4)输入A,B,C,不能产生输出C,A,B:2021/3/1110设依次输入元素A,B,C到栈中,可得哪几种输出?设依次输入元素C,B,A到栈中,可得哪几种输出?A,B,C(1)A,B,C(2)A,C,B(3)B,A,C(4)B,C,A(5)C,A,B(6)C,B,A C,B,A(1)A,B,C(2)A,C,B(3)B,A,C(4)B,C,A(5)C,A,B(6)C,B,A2021/3/1111 讨论：假定输入元素 A,B,C,D 到栈中,能得当哪几种输出?不能得到哪几种输出序

6、列？(1)A,B,C,D (7)B,A,C,D (13)C,A,B,D (19)D,B,C,A (2)A,B,D,C (8)B,A,D,C (14)C,A,D,B (20)D,B,A,C (3)A,C,B,D (9)B,C,A,D (15)C,B,A,D (21)D,C,B,A (4)A,C,D,B (10)B,C,D,A (16)C,B,D,A (22)D,C,A,B (5)A,D,B,C (11)B,D,A,C (17)C,D,A,B (23)D,A,B,C (6)A,D,C,B (12)B,D,C,A (18)C,D,B,A (24)D,A,C,B 共5+5+3+1=14种输出序列。A,

7、B,C,D输入输出5种5种3种1种2021/3/1112 顺序栈的基本操作及算法：顺序栈的类型定义如下所示：#define SackSize100 typedef struct Datatype dataSackSize;int top;SeqStack 定义一个指向顺序栈的指针：SeqStack *s;2021/3/11133.1.2 栈的存储表示和操作实现 1.顺序栈-用顺序空间表示的栈。假设栈空间为data0.SackSize-1(1)顶指针指向顶元素所在位置：top 栈顶指针栈顶栈底SackSize-1 n 1 0/SackSize-1 1 0 -1 自由区自由区(a)非空栈 (b)空

8、栈,stop=-1若删除元素，将发生“下溢”/an.a2 a1 序号 top 序号2021/3/1114top 栈顶栈底SackSize-1 1 0(c)满栈,stop=SackSize-1 若插入元素,将发生“上溢”“Overflow”an.a2 a1 2.操作实现2021/3/1115 (1)置空栈：首先建立栈空间，然后初始化栈顶指针。SeqStack *InitStack()SeqStack *s;s=malloc(sizeof(SeqStack);s-top=-1;return s;(2)判空栈 int StackEmpty(SeqStack*s)return S-top=-1;(3)

9、判满栈int StackFull(SeqStack*s)return s-top=SackSize-12021/3/1116 (4)入栈 void Push(SeqStack*s,datatype x)if(StackFull(s)Error(“Stack overflow”);/*栈满不能入栈*/s-top+;s-datas-top=x;(5)出栈 DataType Pop(SeqStack*s,datatype*x)if (StackEmpty(s)Error(“Stack underflow”);/*栈空不能出栈*/return s-datas-top-;/*返回,栈顶指针减1*/202

10、1/3/1117 (6)取栈顶元素取栈顶元素 datatype Top_SeqStack(SeqStack*s)if(EmptyStack(s)Error(“Stack is empty”);/*栈空栈空*/return(s-datas-top);以下几点说明：以下几点说明：1.对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：为：s-top=StackSize-1，栈满时，不能入栈，栈满时，不能入栈;否则出现空否则出现空间溢出，引起错误，这种现象称为上溢。间溢出，引起错误，这种现象称为上溢。2.出栈和读栈顶元素操作，先判断栈是否为空，为空

11、时不出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。条件。2021/3/11182.链式栈-使用不带表头结点的单链表 (1)结点和指针的定义 struct node ElemType data；/data为抽象元素类型 struct node*next；/next为指针类型 *top=NULL；/初始化,置top为空栈 (2)非空链式栈的一般形式 ana(n-1)a1data nexttop 栈顶栈底2021/3/1119(3)链式栈的进栈算法：/压入元素e到top为顶指针的链式栈st

12、ruct node*push_link(struct node*top,Elemtype e)struct node*p；int leng=sizeof(struct node)；/确定新结点空间的大小 p=(struct node*)malloc(leng)；/生成新结点 p-data=e；/装入元素e p-next=top；/插入新结点 top=p；/top指向新结点 return top；/返回指针top an a1 栈底top epX an a1 栈底top e.栈顶栈顶(1)插入e之前：(2)插入e之后：2021/3/11203.1.3 栈的应用举例 栈的基本用途-保存暂时不用 的数

13、据或存储地址。数制转换问题例.给定十进制数 N=1348,转换为八进 制数 R=25041.依次求余数,并送入栈中：(1)r1=1348%8=4 /求余 n1=1348/8=168 /整除(2)r2=168%8=0 /求余 n2=168/8=21 /整除(3)r3=21%8=5 /求余 n3=21/8=2 /整除(4)r4=2%8=2 /求余 n4=2/8=0 /整除2.依次退栈,得R=2504 4 0 4 5 0 4 2 5 0 4(1)4进栈 (2)0进栈(3)5进栈 (4)2进栈 2021/3/1121十进制数N转换为B进制数算法思想：N0 r=N%B r入栈 N=N/B 算法：type

14、def int DataType;void szzh(int N,int B)int i;SeqStack s;InitStack(&s);/初始化栈 while(N)/N=0转换结束 push(&s,N%B);/余数入栈 N=N/B;while(!StackEmpty(&s)i=Pop(&s);printf(“%d”,i)yn栈非空，出栈显示2021/3/11223.2 队列（排队,queue)3.2.1 队列及其操作 1.定义和术语 队列-只允许在表的一端删除元素,在另一端插入元素 的线性表。空队列-不含元素的队列。队首-队列中只允许删除元素的一端。head,front 队尾-队列中只允许

15、插入元素的一端。rear,tail 队首元素-处于队首的元素。队尾元素-处于队尾的元素。进队-插入一个元素到队列中。又称：入队。出队-从队列删除一个元素。2.元素的进出原则:“先进先出”，“First In First Out”队列的别名:“先进先出”表，“FIFO”表，排队,queue2021/3/1123 队列示意图 a1,a2,.,an head(front)tail(rear)队首 队尾 进队出队 3.队列的基本操作：(1)InitQueue(q)-初始化,将q置为空队列。(2)QueueEmpty(q)-判断q是否为空队列。(3)EnQueue(q,e)-将e插入队列q的尾端。(4)

16、DeQueue(q,e)-取走队列q的首元素,送e。(5)QetHead(q,e)-读取队列q的首元素,送e。(6)QueueClear(q)-置q为空队列。2021/3/1124 A A B C D 0 1 2 3 4 50 1 2 3 4 50 1 2 3 4 5 A进队f r B,C,D进队frfr(3)B,C,D进队后:3.2.2 队列的顺序表示和实现(1)初始化后:(2)A进队后:假设用一维数组Q0.5表示顺序队列1.顺序队列与“假溢出 设f指向队头元素，r指向队尾元素空队列2021/3/1125 D E F 0 1 2 3 4 5 D 0 1 2 3 4 5fr E,F 进队fr

17、G进队,“假溢出”解决假溢出的办法之一:移动元素。(6)D,E,F移到前端后：D E F 0 1 2 3 4 5fr G 进队(4)A,B,C 出队之后：(5)E,F 依次进队之后：2021/3/1126 D E F G 0 1 2 3 4 5fr2.循环队列与解决假溢出的办法之二 (7)G进队之后：解决方法：将存储队列元素的一维数组首尾相接，形成一个环状。将这种形式表示的队列称之为循环队列。（5）中用循环队列表示012345DEFG/rff=(f+1)%QueueSiz；r=(r+1)%QueueSize；QueueSize为数组单为数组单元数目元数目2021/3/1127234501FGD

18、E/H,I进队234501FGDEIHH,I进队之后frfr“满队列”:将Q0.5解释为循环队列的示意图：D,E,F,G,H,I出队，“空队列”fr012345当 f=r 时，怎样判断队列是空还是满？2021/3/1128当f=r，判断队空和满的方法：a.设置一个布尔量以区别队空队满。b.少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，相等，队满。c.使用计数器记录队中元素的总数。下面以第三种方法定义循环队的类型：#define QueueSize 100 typedef char DataType;/DataType类型依赖具体应用 typedef struct

19、datatype dataQueueSize;/*数据的存储区*/int front,rear;int count;/*计数器，记录队中元素的个数*/CirQueue;/*循环队*/循环队列的6种基本运算：/*队头队尾指针；非空时，队尾指针指向队尾元素下一个位 置*/2021/3/1129(1)置队空置队空 void InitQueue (CirQueue *Q)Q-front=Q-rear=0;Q-count=0;(2)判队空判队空 int QueueEmpty(CirQueue *Q)return Q-count=0;(3)判队满判队满 int QueueFull(CirQueue *Q)

20、return Q-count=QueueSize;(4)入队入队 void EnQueue(CirQueue *Q,DataType x )if(QueueFull(Q)Error(“Queue overflow”);/队满上溢队满上溢 Q-count+;Q-dataQ-rear=x;/新元素新元素x入队尾入队尾 Q-rear=(Q-rear+1)%QueueSize;2021/3/1130 (5)出队出队 DataType DeQueue(CirQueue *Q)DataType temp;if(QueueEmpty(Q)Error(“Queue undeflow”);/队空下溢队空下溢 t

21、emp=Q-dataQ-front;Q-count-;Q-front=(Q-front+1)%QueueSize;return temp;(6)取队头元素取队头元素 DataType QueueFront(CirQueue *Q)if(QueueEmpty(Q)Error(“Queue is empty”);return Q-dataQ-front;2021/3/1131 3.2.3链式队列:用不带表头结点的单链表表示队列 1.一般形式 (1)空队列:(2)非空队列:其中：Q-front-队头(首)指针,指向队头结点。Q-rear-队尾指针，指向队尾结点。a1data next a2队头结点a

22、n队尾结点.Q-frontQ-rear*QQ-frontQ-rear*Q2021/3/1132 2.2.定义结点类型定义结点类型 (1)(1)存放元素的结点类型存放元素的结点类型 typedef struct qtypedef struct queuenode node DataType data DataType data；/data/data为抽象元素类型为抽象元素类型 struct qstruct queuenode node*nextnext；/next/next为指针类型为指针类型 QQueueNodeNode；/结点类型结点类型,指针类型指针类型 (2)(2)由头、尾指针组成的结点

23、类型由头、尾指针组成的结点类型 typedef struct typedef struct Q QueueNode Node*frontfront；/头指针头指针 Q QueueNode Node*rearrear；/尾指针尾指针 LinkQueueLinkQueue；/链式队列链式队列类型类型data nextfrontrear2021/3/1133链式队列操作算法：（1）初始化算法 void InitQueue (LinkQueue *Q)Q-front=Q-rear=NULL;(2)判队空算法判队空算法int QueueEmpty(LinkQueue *Q)return Q-front=

24、NULL&Q-rear=NULL;(3)插入算法2021/3/1134 插入新元素x插入到队尾的算法 void EnQueue(LinkQueue Q,DataType x)QueueNode*p；/说明变量p指针 p=(QueueNode*)malloc(sizeof(QueueNode)；/生成新结点 p-data=x；/装入元素x p-next=NULL；/为队尾结点 if(QueueEmpty(Q)Q-front=Q-rear=p;/将将x插入空队插入空队 else /x插入非空队插入非空队 Q-rear-next=p；/将p插入队尾 Q-rear=p；/修改尾指针2021/3/1135（4）出队算法:DataType DeQueue(LinkQueue*Q)DataType x;QueueNode*p；/说明变量p指针 if(QueueEmpty（Q）)/若原队列为空 Error(“queue underflow”)；/队下溢，退出去 p=Q-front；/P指向队头结点 x=p-data；/取出元素,e指向它 Q-front=p-next；/删除队头结点 if(Q-rear=p)/若原队列只有1个结点 Q-rear=NULL；/修改尾指针 free(p)；/释放被删除结点的空间 return x；/返回原队头数据