数据结构 第三章 栈和队列

1、第三章 栈和队列学时：4学时本章主要介绍以下内容： 1、栈的概念、存储结构及其基本操作 2、队列的概念、存储结构及其基本操作 3、栈与队列的应用举例 本章主要介绍以下内容： 本章重点难点： 1、栈的存储结构、特点、基本操作算法实现、 以及栈在递归算法实现中的应用。2、队列存储结构、特点、基本操作、 算法实现、循环队列及其应用。 本章重点难点：3.1 栈栈的定义栈的表示与实现栈的应用栈 是仅在表尾进行插入、删除操作的线性表。表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base3.1.1 栈的定义例如： 栈 S= (a1 , a2 , a3 , .,an-1 , an

2、 )插入元素到栈顶的操作，称为入栈。从栈顶删除最后一个元素的操作，称为出栈。an称为栈顶元素a1称为栈底元素想一想：要从栈中取出a1，应当如何操作？强调：插入和删除都只能在表的一端（栈顶）进行！问题1：堆栈是什么？它与一般线性表有什么不同？ 堆栈是一种特殊的线性表，它只能在表的一端（即栈顶）进行插入和删除运算。一般线性表 堆栈逻辑结构：1:1 逻辑结构： 1:1 存储结构：顺序表、链表 存储结构：顺序栈、链栈运算规则：任意插入删除 运算规则：后进先出(LIFO)“进”插入=压入=PUSH（an+1)“出”删除=弹出=POP(an)问题2： 为什么要设计堆栈？ 它有什么独特用途？调用函数或子程序

3、非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题。例1.一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即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种可能性。例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？答：43512不可能实现，主要是其中的12顺

4、序不能实现；12345的输出可以实现，每压入一数便立即弹出即。 思考：有无通用的判别原则？例3：设依次进入一个栈的元素序列为c，a，b，d， 则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、D）可以， B）、C）不行。讨论：有无通用的判别原则？有！若输入序列 ,PjPkPi (PjPkPi)，一定不存在这样的输出序列 ,PiPjPk 答：即对于输入序列1，2，3，不存在输出序列3，1，2栈的抽象数据类型定义关系：栈中数据元素之间是线性关系数据元素：可以是任意类型的数据，但必须属于同一个数据对象。 ADT Stack 数据对象： D ai

5、| ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁StackEm

6、pty(S)初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。StackLength(S)初始条件：栈 S 已存在。操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, &e)初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。a1a2an ClearStack(&S)初始条件：栈 S 已存在。操作结果：将 S 清为空栈。 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。a1a2ane Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并

7、用 e 返回其值。a1a2anan-1 3.1.2 栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。用C语言定义栈的顺序存储结构#define TRUE 1#define FALSE 0#define Stack_Size 50typedef structStackElementType elemStack_Size;

8、 /*用来存放栈中元素的一维数组*/int top; /*用来存放栈顶元素的下标*/SeqStack;顺序栈中的进栈和出栈图例AEDCBABAtop top top top顺序栈基本操作的实现1）初始化void InitStack(SeqStack *S)/*构造一个空栈S*/ S-top= -1;2）判栈空int IsEmpty(SeqStack *S) /*判栈S为空栈时返回值为真，反之为假*/return(S-top=-1?TRUE:FALSE);3） 判栈满int IsFull(SeqStack *S)/*判栈S为满时返回真，否则返回假*/return(S-top= Stack_Siz

9、e-1?TRUE:FALSE);4）进栈int Push(SeqStack * S, StackElementType x)if(S-top= Stack_Size-1) return(FALSE); /*栈已满*/S-top+;S-elemS-top=x;return(TRUE);5）出栈int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*栈为空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针 */ return(TRUE); 6） 取栈顶元素int GetTop

10、（SeqStack S, StackElementType *x） /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */if(S-top=-1) /*栈为空*/ return(FALSE);else *x = S-elemS-top; return(TRUE); 栈为空 的条件 ： S.top=-1;栈满的条件 ： S.top=Stack_Size-1; a1 a2 an顺序栈S ai低地址高地址 栈顶top顺序栈栈空栈满的条件2.链栈链栈是采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指

11、针就作为栈顶指针。 栈顶指针a1an注意: 链栈中指针的方向an-1用C语言定义的链栈结构typedef struct nodeStackElementType data;struct node *next;LinkStackNode,*LinkStack;链栈的进栈操作int Push(LinkStack top, StackElementType x)/* 将数据元素x压入栈top中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE

12、); /* 申请空间失败 */temp-data=x; temp-next=top-next;top-next=temp; /* 修改当前栈顶指针 */ return(TRUE);链栈的出栈操作int Pop(LinkStack top, StackElementType *x) /* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*栈为空*/return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 释放存储空间

13、 */ return(TRUE);例1、 数制转换例2、 括号匹配的检验例3、 表达式求值3.2栈的应用举例 例1、 数制转换 算法基于原理： N = (N div d)d + N mod d 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2计算顺序输出顺序void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e);

14、 printf ( %d, e ); / conversion 例2、 括号匹配的检验假设在表达式中（）或（ ）等为正确的格式，（ ）或（ ）或 （）)均为不正确的格式。分析可能出现的不匹配的情况:到来的右括弧并非是所“期待”的；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表

15、明“左括弧”有余。Status matching(string& exp) int state = 1; while (i0时 递推规则 为保证递归调用正确执行，系统设立一个“递归工作栈”，作为整个递归调用过程期间使用的数据存储区。 每一层递归包含的信息如：参数、局部变量、上一层的返回地址构成一个“工作记录” 。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记录。 从被调函数返回调用函数的一般步骤：(1) 若栈为空，则执行正常返回。 从栈顶弹出一个工作记录。 将“工作记录”中的参数值、局部变量值赋给相应的变量；读取返回地址。 将函数值赋给相应的变量。(5)

16、 转移到返回地址。例 3-2 n 阶 Hanoi 问题。 假设有三个分别命名为 X 、 Y 和 Z 的塔座，在塔座X 上插有 n 个直径大小各不相同、依小到大编号为 1 ， 2 ， ,n 的圆盘。现要求将 X 轴上的 n 个圆盘移至塔座 Z上，并仍按同样顺序叠排，圆盘移动时必须遵循下列规则： 1) 每次只能移动一个圆盘； 2) 圆盘可以插在 X 、 Y 和Z 中的任一塔座上； 3) 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。 如何实现圆盘的移动操作？ 当 n=1 时，从塔座 X - Z; 当 n1 时，利用塔座 Y 作辅助塔座，若能设法将 压在编号为 n 的圆盘之上的 n-1 个圆盘从

17、塔座 X -Y 上，则可先将编号为 n 的圆盘从塔座 X -Z ，然后再 将塔座 Y 上的 n-1 个圆盘移至塔座 Z 上。 而如何将 n-1 个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小 1 ，因此可以用同样的方法求解。 void hanoi ( int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n = 1) 2 move(x, 1, z); / 将编号为的圆盘从x移到z 3 else 4 hanoi(n-1, x,

18、z, y); / 将x上编号为至n-1的 / 圆盘移到y, z作辅助塔 5 move(x, n, z); / 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 / 圆盘移到z, x作辅助塔 7 8 3.4队列队列的定义队列的表示与实现队列的应用 队列是只允许在一端插入元素,而在另一端删除的线性表。 允许插入的一端叫队尾,允许删除的一端称为队头3.4.1 队列的定义例如： 队列 q= (a1 , a2 , a3 , .,an-1 , an )插入元素到队尾的操作，称为入队列。删除第一个元素的操作，称为出队列。an称为队尾元素a1称为队头元素队列

19、特点:先进先出 队列的抽象数据类型定义关系：队列中数据元素之间是线性关系数据元素：可以是任意类型的数据，但必须属于同一个数据对象。 ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾基本操作： ADT Queue队列的抽象数据类型定义队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)

20、EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：队列Q已存在。 操作结果：队列Q被销毁，不再存在。 QueueEmpty(Q)初始条件：队列Q已存在。操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。a1a2an ClearQueue(&Q)初始条件：队列Q已存在。操作结果：

21、将Q清为空队列。 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。a1a2an 链队列链式映象循环队列顺序映象3.4.2队列的表示与实现 队列的链式存储结构称为链队列（或链队），实际上它是一个带有头指针（front）和尾指针（rear）的单链表。为了处理方便，也可以给链队列附加一个头结点。链队列为空的条件是front=rear，即队列的头指针和尾指针均指向表头结点。1.链队列 typedef struct QNode / 结点类型

22、 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链式映象typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存

23、储分配失败 Q.front-next = NULL; return OK;链队列基本操作的实现 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;链队列基本操作的实现 Status DeQueue (LinkQueue &Q, QElemType &e)

24、 / 若队列不空，则删除Q的队头元素， /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;链队列基本操作的实现 将队列的数据区Q0 .MAXLEN-1看成是首尾相连的环，即将表示队首的元素Q0与表示队尾的元素QMAXLEN1连接起来，形成一个环形表，这就成了循环队列。2、循环队列#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;循环队列顺序映象 q.rear q.front q