第3章 栈和队列,本章主要介绍以下内容： 栈的概念、存储结构及其基本操作 队列的概念、存储结构及其基本操作 栈与队列的应用举例,退出,诚昊工作室,3.1 栈 3.2 栈的应用举例 3.3 队列 3.4 队列的应用举例,,3.1 栈,3.1.1 栈的定义 栈是一种特殊的线性表其特殊性在于限定插入和删除数据元素的操作只能性表的一端进行如下所示： 进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底我们经常将栈用下图3-1的形式描述：,,,a1, a2, a3, ..., an 插入和删除端,,图 3-1,,,结论：后进先出（Last In First Out），简称为LIFO线性表 举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗 举例2：死胡同 举例3：对一栈，给定的输入项目A,B,C,若输入的顺序是A,B,C，试给出全部的可能的输出序列 下面我们先给出栈结构的基本操作： （1）初始化栈 Init_Stack(S) （2）入栈 Push_Stack(S,x) （3）出栈 Pop_Stack(S) （4）获取栈顶元素内容 Top_Stack(S) （5）判断栈是否为空 Empty_Stack (S),,,3.1.2 栈的顺序存储 栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
类型定义如下所示： #define MAXSIZE 100 typedef struct datatype dataMAXSIZE; int top; SeqStack 定义一个指向顺序栈的指针： SeqStack *s;,,,基本操作算法： 置空栈：首先建立栈空间，然后初始化栈顶指针 SeqStack *Init_SeqStack() SeqStack *s; s=malloc(sizeof(SeqStack)); s-top= -1; return s; 判空栈 int Empty_SeqStack(SeqStack *s) if (s-top= = -1) return 1; else return 0; ,,,图 3-2,,, 入栈 int Push_SeqStack (SeqStack *s, datatype x) if (s-top= =MAXSIZE-1) return 0; /*栈满不能入栈*/ else s-top++; s-datas-top=x; return 1; 出栈 int Pop_SeqStack(SeqStack *s, datatype *x) if (Empty_SeqStack ( s ) ) return 0; /*栈空不能出栈 */ else *x=s-datas-top; s-top--; return 1; /*栈顶元素存入*x，返回*/ ,,, 取栈顶元素 datatype Top_SeqStack(SeqStack *s) if ( Empty_SeqStack ( s ) ) return 0; /*栈空*/ else return (s-datas-top ); 以下几点说明： 1. 对于顺序栈，入栈时，首先判断栈是否满了，栈满的条件为：s-top= =MAXSIZE-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
2. 出栈和读栈顶元素操作，先判断栈是否为空，为空时不能操作，否则产生错误通常栈空时常作为一种控制转移的条件3.1.3 栈的链式存储 若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构人们将用链式存储结构表示的栈称作“链栈”链栈通常用一个无头结点的单链表表示如图3-3所示 由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针链式栈:栈的链接表示,链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,top,,,,,,,,,,,,,,,,,,,如图3-3,栈的链式存储结构在C语言中可用下列类型定义实现： typedef struct node datatype data; struct node *next; StackNode，* LinkStack; 说明top为栈顶指针： LinkStack top ;,,,下面我们将给出链栈各项基本操作的算法 置空栈 Init_LinkStack（ LinkStack top） top NULL; 判栈空 int Empty_LinkStack（LinkStack top ） if（top==NULL ） return 1; else return 0; ,,, 入栈 LinkStack Push_LinkStack（LinkStack top, datatype x） StackNode *s; s=malloc（sizeof（StackNode））; s-data=x; s-next=top; top=s; return top; ,,, 出栈 LinkStack Pop_LinkStack (LinkStack top, datatype *x) StackNode *p; if （top= =NULL） return NULL; else *x = top-data; p = top; top = top-next; free (p); return top; ,,,例 3.1 简单应用：数制转换问题 将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3467，r=8为例转换方法如下： N N / 8 （整除） N % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高 所以：（3467）10 =（6613）8,,,,3.2 栈的应用举例,我们看到所转换的8进制数按低位到高位的顺序产生的，而通常的输出是从高位到低位的，恰好与计算过程相反，因此转换过程中每得到一位8进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。
算法思想如下：当N0时重复1，2 1若 N0，则将N % r 压入栈s中 ，执行2;若N=0，将栈s的内容依次出栈，算法结束 2用N / r 代替 N,,,#define L 10 void conversion(int N，int r) int sL,top; /*定义一个顺序栈*/ int x; top =-1; /*初始化栈*/ while ( N ) s++top=N%r; /*余数入栈 */ N=N / r ; /* 商作为被除数继续 */ while (top!=-1) x=stop--; printf(“%d”,x); ,,,课堂练习： I表示入栈，O表示出栈，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的I和O的操作串是什么？ I1O1I2I3O3I4O4O2,main() int i,e,a=1,2,3,4,5,6,7,8,9; SeqStack s; Initstack(s); for(i=0;i<9;i++) push(s,ai);//入栈 while(!Stackempty(s)) pop(s,e);//出栈 printf(“%2d”,e) ,课堂练习：,作业： 3.3 3.4 3.5,。