数据结构-使用C语言 朱战立 第3章堆栈和队列

1、1 3.1 堆栈（Stack） 基本概念、抽象数据类型 顺序表示和实现 链式表示和实现 3.2 堆栈应用 括号匹配问题 3.3 队列（Queue） 基本概念、抽象数据类型 顺序队列、顺序循环队列、链式队列、队列的应用 第三章第三章 堆栈和队列堆栈和队列2定义：只能在表的进行插入和删除操作的线性表。特点： 逻辑结构与线性表相同，为一比一（1:1）关系。 堆栈中允许进行插入和删除数据元素的一端为栈顶，另一端称为栈底。 插入元素到栈顶的操作称为进栈或入栈，从栈顶删除元素的操作通常称为出栈或退栈。 堆栈中的数据元素实行后进先出或先进后出。3存储结构：用或存储均可，但以顺序栈更常见。栈“上溢”：在栈满时

2、还进行入栈运算栈“下溢”：当栈空时仍进行出栈运算4是仅在表尾进行插入、删除操作的线性表。表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base例如： 栈 = (a , a2 , a3 , .,an-1 , an )a an n称为栈顶元素称为栈顶元素a a1 1称为栈底元素称为栈底元素强调：强调：插入和删除都只能在表的一插入和删除都只能在表的一 端（栈顶）进行！端（栈顶）进行！出栈出栈a1a2an-1an栈底栈底 bottom栈顶栈顶 top栈栈举例举例1：家里吃饭的碗，通常在洗干净：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，后一个一个地落在一起

3、存放，在使用时，若一个一个地拿，一定最先拿走最上面若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。的那只碗，而最后拿出最下面的那只碗。大家举例？大家举例？n注：堆栈可以完成比较复杂的数据元素注：堆栈可以完成比较复杂的数据元素特定序列的转换任务，但它不能完成任特定序列的转换任务，但它不能完成任何输入输出序列的转换任务。何输入输出序列的转换任务。78例例1、一个栈的输入序列为一个栈的输入序列为1,2,3，若在，若在入栈的过入栈的过程中允许出栈程中允许出栈，则可能得到的出栈序列是什么？，则可能得到的出栈序列是什么？解：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3

4、出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321；合计有5种可能性。9例例2、一个栈的输入序列是一个栈的输入序列是12345，若在，若在入栈的入栈的过程中允许出栈过程中允许出栈，则栈的输出序列则栈的输出序列43512可能实可能实现吗？现吗？12345的输出呢？的输出呢？解： 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，每压入一数便立即弹出即可。 10问：堆栈是什么？它与一般线性表有什么不同？问：堆栈是什么？它与一般线性表

5、有什么不同？ 堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。与一般线性表的区别：仅在于不同。一般线性表一般线性表堆栈堆栈逻辑结构：逻辑结构：1:1 逻辑结构：逻辑结构： 1:1 存储结构：顺序存储结构：顺序表表、链、链表表 存储结构：顺序栈、链栈存储结构：顺序栈、链栈运算规则：运算规则：随机存取随机存取 运算规则：运算规则：后进先出后进先出(LIFO)“进进”插入插入= =压入压入“出出”删除删除= =弹弹出出11数据集合： a0, a1, , an-1 ai的数据类型为DataType操作集合： (1)StackInitiate(S) 初始化堆栈S (2)StackN

6、otEmpty(S) 堆栈S非空否 (3)StackPush(S,x) 入栈 (4)StackPop(S,d) 出栈 (5)StackTop(S,d) 取栈顶数据元素121、顺序（堆）栈 顺序存储结构的堆栈。2、顺序栈的存储结构 它是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时设指针top指示当前栈顶位置。 a0 a1 an-1顺序栈顺序栈S ai an栈底栈底栈顶栈顶133、C语言描述：typedef struct DataType stackMaxStackSize; int top;SeqStack;14 a0 a1 an-1顺序栈顺序栈S ai问：顺序表和顺序栈的操作

7、有何区别？问：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si= ai读出：读出： e= Si压入压入(SStop+top+=a=an n弹出弹出( e=Se=S-top-top 低地址低地址高地址高地址Si a0 a1 ai an-1 顺序表顺序表S an以线性表以线性表 S= (a0 , a1 , . , an-2 , an-1)为例为例栈底栈底栈顶栈顶前提：一定要前提：一定要栈顶指针栈顶指针栈顶栈顶15栈不存在的条件：栈不存在的条件： base=NULL;栈为空的条件栈为空的条件 ： base=top或或top=MaxStackSize a0 a1

8、an-1顺序栈顺序栈S ai低地址低地址高地址高地址 an栈底栈底栈顶栈顶入栈入栈口诀：堆栈指针口诀：堆栈指针top “先先压后加压后加” : Stop+=an出栈出栈口诀：堆栈指针口诀：堆栈指针top “先先减后弹减后弹” : e=S-top16例3：用堆栈存放（A，B，C，D）AACBABAtop 顺序栈入栈函数的核心语句：顺序栈入栈函数的核心语句：S-stackS-top = x; S-top +;toptoptoptop低地址低地址L高地址高地址MBCD17例4：从栈中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD顺序栈出栈函数的核心语句：

9、顺序栈出栈函数的核心语句：S-top -;d = S-stackS-top;18例例5、设依次进入一个栈的元素序列为设依次进入一个栈的元素序列为c，a，b，d，则则可得到出栈的元素序列是：可得到出栈的元素序列是： ）a a，b b，c c，d d ）c c，d d，a a，b b ）b b，c c，d d，a a ）a a，c c，d d，b bA）、）、D）可以，）可以， B）、）、C）不行。）不行。讨论：有无通用的判别原则？有！有！若输入序列是若输入序列是 ,PjPkPi (PjPktop = 0; /*定义初始栈顶下标值*/ 20(2) 判栈非空否 int StackNotEmpty(S

10、eqStack S)/*判顺序堆栈S非空否，非空则返回1，否则返回0*/ if(S.top top = MaxStackSize)printf(堆栈已满无法插入! n); return 0;else S-stackS-top = x; S-top +; return 1; 22(4)出栈int StackPop(SeqStack *S, DataType d)/*弹出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/ if(S-top top -; d = S-stackS-top; return 1; 23(5)取栈顶数据元素int StackTop(SeqStack S

11、, DataType d)/*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/ if(S.top next = NULL;链式堆栈的操作实现链式堆栈的操作实现headhead-nextNULL30（2）非空否StackNotEmpty(head) int StackNotEmpty(LSNode *head) if(head-next = NULL) return 0; else return 1; 31int StackPush(LSNode *head, DataType x) LSNode *p;p-data = x;p-next = head-next;head

12、-next = p; return 1;(3)入栈入栈x phead head-nextp-next32(4)出栈出栈int StackPop(LSNode *head, DataType *d) head-next = p-next; *d = p-data; free(p); return 1; pheadP-nexthead-next33（5）取栈顶数据元素StackTop(*head, *d) int StackTop(LSNode *head, DataType *d) LSNode *p = head-next; if(p = NULL) printf(堆栈已空出错！); retu

13、rn 0; *d = p-data; return 1; 3.2 3.2 堆栈应用堆栈应用1、括号匹配问题例：假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的函数，并设计一个测试主函数。解题：这是一个输入元素序列到特定输出元素序列转换问题。算法思想： 算术表达式中右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。括号匹配共有四种情况：（1）左右括号配对次序不正确；（2）右括号多于左括号；（3）左括号多于右括号； （4）左右括号匹配正确。 具体方法：顺序扫描算术表达式（表现为一个字

14、符串），当遇到三种类型的左括号时让该括号进栈；当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左右括号配对次序不正确；若字符串当前为某种类型左括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空（即堆栈中尚有某种类型左括号），则说明左括号多于右括号；否则，左右括号匹配正确。括号匹配共有四种情况：（1）左右括号配对次序不正确：()abc()（2）右括号多于左括号： ()abc（3）左括号多于右括号： ()()abc（4）左右括号匹配正确： ()abcvoid ExpIsCorrect(char exp,

15、 int n) SeqStack myStack; int i; char c; StackInitiate(&myStack); for(i = 0; i 0)/m=0则循环结束x=m%n;StackPush(&mystack,x);/将转换后的数字压入栈 m=m/n; while(StackNotEmpty(myStack)StackPush(&myStack,&x);/出栈 printf(%d,x); 3.3 3.3 队队 列列1、队列的基本概念(1)定义:只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。一个队列的示意图如下：队尾插入队头删除

16、a0a1a2an-1队头队尾数据集合:a0,a1,an-1，ai的数据类型为DataType。操作集合：（1）初始化QueueInitiate(Q) （2）非空否QueueNotEmpty(Q) （3）入队列QueueAppend(Q, x) （4）出队列QueueDelete(Q, d) （5）取队头数据元素QueueGet(Q, d) 3、顺序队列(1)顺序队列： 顺序存储结构的队列。2、队列抽象数据类型 (2) (2)顺序队列的存储结构顺序队列的存储结构 有有6 6个存储空间的顺序队列动态示意图个存储空间的顺序队列动态示意图(a)空队列front rear=012345CBA(b)入队列

17、A、B、C后front =012345C(c)出队列A、B后front=012345rear =EDC(d)入队列D、E后front=012345rear =rear = (3) (3)顺序队列的顺序队列的“假溢出假溢出”问题问题假溢出假溢出顺序队列因多次入队列和出队列操作后出现的虽有存储顺序队列因多次入队列和出队列操作后出现的虽有存储空间但不能进行入队列操作的情况。空间但不能进行入队列操作的情况。可采取3种方法：1)采用顺序循环队列；（教材中的方法） 2)按最大可能的进队操作次数设置顺序队列的最大 元素个数；（最差的方法） 3)修改出队算法，使每次出队列后都把队列中剩余 数据元素向队头方向移

18、动一个位置；如何解决顺序队列的假溢出问题？(4)(4)顺序循环队列的基本原理顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当的循环队列。当rearrear和和frontfront达到达到MaxQueueSize-1MaxQueueSize-1后，再前进后，再前进一个位置就自动到。一个位置就自动到。a3a2a1frontrear 0 1 2 3 . .N-1a3a2a10123N-1rearfront (5)顺序循环队列的队空和队满判断问题 新问题：在顺序循环队列中，队空特征是front=rear；队满时也

19、会是 front=rear；判决条件将出现二义性！解决方案有三： 使用一个计数器记录队列中元素个数（即队列长度）； （教材中的方法）判队满：count0 & rear=front 判队空：count=0 设标志位，出队时置,入队时置,则可识别当前front=rear 属于何种情况判队满：tag=1 & rear=front 判队空：tag=0 & rear=front 少用一个存储单元判队满： front=(rear+1)%MaxQueueSize 判队空： rear=front问题1n若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当

20、从队列中删除1个元素，再加入2个元素后，rear和front的值分别为多少？nrear=2，front=451问题2n设栈S和队列Q的初始状态为空，元素1,2,3,4,5,6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队列的序列是3,5,4,6,2,1，则栈s的容量至少应该是多少？n4524、顺序循环队列顺序循环队列的结构体定义如下：typedef struct DataType queueMaxQueueSize; int rear; int front; int count; SeqCQueue; （1）初始化QueueInitiate(Q)void QueueInitiate(S

21、eqCQueue *Q) Q-rear = 0; Q-front = 0; Q-count = 0;（2）非空否QueueNotEmpty(Q)int QueueNotEmpty(SeqCQueue Q) if(Q.count != 0)return 1; else return 0;（3）入队列QueueAppend(Q, x)int QueueAppend(SeqCQueue *Q, DataType x) if(Q-count 0 & Q-rear = Q-front) printf(队列已满无法插入! n); return 0; else Q-queueQ-rear = x;

22、Q-rear = (Q-rear + 1) % MaxQueueSize; Q-count+; return 1; （4）出队列QueueDelete(Q, d)int QueueDelete(SeqCQueue *Q, DataType *d) if(Q-count = 0) printf(队列已空无数据元素出队列! n); return 0; else *d = Q-queueQ-front; Q-front = (Q-front + 1) % MaxQueueSize; Q-count-; return 1; （5 5）取队头数据元素）取队头数据元素QueueGet(Q, d)int Q

23、ueueGet(SeqCQueue Q, DataType *d) if(Q.count = 0) printf(队列已空无数据元素可取队列已空无数据元素可取! n); return 0; else *d = Q.queueQ.front; return 1; 5、链式队列1)1)链式队列链式队列 链式存储结构的队列。链式存储结构的队列。2)2)链式队列的存储结构链式队列的存储结构 链式队列的队头指针指向队列的当前队头结点链式队列的队头指针指向队列的当前队头结点; ;队尾队尾指针指在队列的当前队尾结点指针指在队列的当前队尾结点. . 一个不带头结点的链式队列的结构：一个不带头结点的链式队列的结

24、构：a0a1an-2an-1frontrear结点的结构体可定义如下：typedef struct qnode/*结点结构结点结构*/ DataType data; struct qnode *next; LQNode; 队头指针front和队尾指针rear的结构体类型：typedef struct/*指针结构指针结构*/ LQNode *front; /*队头指针队头指针*/ LQNode *rear; /*队尾指针队尾指针*/ LQueue;3) 链式队列操作的实现 （1）初始化QueueInitiate(Q) void QueueInitiate(LQueue *Q) Q-rear =

25、NULL; Q-front = NULL; （2）非空否QueueNotEmpty(Q) int QueueNotEmpty(LQueue Q) if(Q.front = NULL) return 0; else return 1; Q-frontQ-rear （3）入队列QueueAppend(Q, x) int QueueAppend(LQueue *Q, DataType x) LSNode *p; p = (LQNode *)malloc(sizeof(LQNode) ; p-data = x; p-next = NULL; if(Q-rear != NULL) Q-rear-next

26、 = p; Q-rear = p; if(Q-front = NULL) Q-front = p; return 1; pxabQ-frontQ-rearQ-rear-next （4）出队列QueueDelete(Q, d) int QueueDelete(LQueue *Q, DataType *d) LQNode *p;*d = Q-front-data; p = Q-front; Q-front = Q-front-next; if(Q-front = NULL) Q-rear = NULL; /*此时队列中已无数此时队列中已无数据元素据元素*/ free(p); return 1; p

27、cabQ-frontQ-rearQ-front-next（5）取队头数据元素QueueGet(Q, d) int QueueGet(LQueue Q, DataType *d) if(Q.front = NULL) printf(队列已空无数据元素出队列! n); return 0; else *d = Q.front-data;return 1; 6、队列的应用任务描述：一个计算机局域网系统中有若干台计算机，为了节约资源，只安装了一台打印机，要求设计一个对打印机的打印任务进行管理的打印任务管理器，打印机的打印任务按照先来先打印的方式进行管理。任务分析：打印任务管理器可设计成一个链式队列。打印

28、任务管理器应包含的操作有：（1）初始化。（2）入队列。把新的打印任务加入到队尾。（3）出队列。（4）输出。（5）清空。任务说明：每一个打印任务应包含打印任务标识号和要打印的内容。数据结构设计：链式队列的结点结构体定义如下：typedef struct node int id;/打印任务标识号 char *text; /要打印的内容 struct node *next; /指向下一个结点的指针Task; /结点结构体Task链式队列的头指针、尾指针结构体定义如下：typedef struct Task *front; /头指针 Task *rear; /尾指针Queue; /链式队列结构体Que

29、ue（2）入队列。把新的打印任务加入到队尾。void AppendPrintTask(Queue *taskmanager, int tid, char *text)/打印任务包括打印任务标识号tid和要打印的内容text Task *p; p = (Task *) malloc(sizeof(Task); p-text = (char *) malloc(strlen(text) * sizeof(Task) +1); strcpy(p-text, text); p-id = tid; p-next = NULL; if(taskmanager-rear != NULL) taskmanag

30、er-rear-next = p; taskmanager-rear = p; if(taskmanager-front = NULL) taskmanager-front = p; （3）出队列。int PrintFirstTask(Queue *taskmanager)/取出队列taskmanager中的第一个打印任务进行打印，并把该打印任务从队头删除 Task *p = taskmanager-front; if(p = NULL) return 0; else printf(Task id: %dn, p-id); printf(Task context: %sn, p-text);

31、taskmanager-front = taskmanager-front-next; if(taskmanager-front = NULL) taskmanager-rear = NULL; free(p-text);free(p); return 1;练习void main()QueueInitiate(Q);char x=e,y=c;QueueAppend(Q,h);QueueAppend(Q,r);QueueAppend(Q,y);QueueDelete(Q,x);QueueAppend(Q,x);QueueDelete(Q,x);QueueAppend(Q,a);while(!Qu

32、eueNotEmpty(Q)QueueDelete(Q,y);printf(y);printf(x);68void algo(Queue &Q)int d;StackInitiate(S);while(!QueueNotEmpty(Q)QueueDelete(Q,d);StackPush(S,d); while(!StackNotEmpty(S)StackPop(S,d);QueueAppend(Q,d);693.3.6 队列的应用n回文处理问题n回文是指一个字符序列以中间字符为基准，两边字符完全相同，如字符“ABCDEDCBA”是回文； “ABCDEDBAC”不是回文70编程思想：设

33、字符数组str中存放了要判断的字符串。把字符数组中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的字符和退栈的字符是否相等，若全部相等则该字符序列是回文，否则就不是回文。71#include #include #include #include #define MaxQueueSize 100#define MaxQueueSize 100#define MaxStackSize 100#define MaxStackSize 100typedef char DataType;typedef char DataType;#include SeqCQueue.h#include

34、SeqCQueue.h#include SeqStack.h#include SeqStack.h“void void HuiWenHuiWen(char str)(char str) SeqCQueue myQueue;SeqCQueue myQueue;SeqStack myStack;SeqStack myStack;char x, y;char x, y;int i, length;int i, length;73length = strlen(str);/length = strlen(str);/取字符长度取字符长度QueueInitiate(&myQueue);/Queu

35、eInitiate(&myQueue);/初始化队列初始化队列StackInitiate(&myStack);/StackInitiate(&myStack);/初始化栈初始化栈for(i = 0; i length; i+)for(i = 0; i length; i+) QueueAppend(&myQueue, stri);/QueueAppend(&myQueue, stri);/入队列入队列StackPush(&myStack, stri);StackPush(&myStack, stri); /入栈入栈while(QueueNotEmpty(myQueue)=1 & while(QueueNotEmpty(myQueue)=1 & StackNotEmpty(myS