数据结构DS03栈和队列

1、 第三章第三章 栈和队列栈和队列定定 义义与线性表相同，数据元素之间仍为一对一的关与线性表相同，数据元素之间仍为一对一的关系。系。用用或或存储均可。存储均可。只能在只能在运算，且访问结点时依照运算，且访问结点时依照（lifolifo）或）或（filofilo）的原则。）的原则。关键是编写关键是编写、等函数，具体实现按顺序等函数，具体实现按顺序栈或链栈的存储结构的不同而不同。栈或链栈的存储结构的不同而不同。存储结构存储结构运算规则运算规则实现方式实现方式 逻辑结构逻辑结构限定只能在表的限定只能在表的进行插入和删除运算的线进行插入和删除运算的线性表。性表。基本操作基本操作 建栈、判断栈满或栈空、入

2、栈、出栈、读栈顶建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。元素值，等等。 是仅在表尾进行插入、删除操作的线性表。是仅在表尾进行插入、删除操作的线性表。表尾表尾( (即即 a an n 端端) )称为栈顶称为栈顶 (top) ; (top) ; 表头表头( (即即 a a1 1 端端) )称为栈底称为栈底( (bottom)bottom)。例如：例如： 栈栈 = (a1 , a2 , a3 , .,an-1 , an )插入元素到栈顶的操作，称为插入元素到栈顶的操作，称为入入。从栈顶删除元素的操作，称为从栈顶删除元素的操作，称为出栈出栈。a an n称为栈顶元素称为栈顶元素a a1

3、1称为栈底元素称为栈底元素插入和删除都只能在表插入和删除都只能在表的一端（栈顶）进行！的一端（栈顶）进行！栈的基本操作栈的基本操作 initstackinitstack(s)(s)： 构造一个空栈构造一个空栈s s clearstackclearstack(s)(s)： 清除栈清除栈s s中的所有元素中的所有元素 stackemptystackempty(s)(s)：判断栈：判断栈s s是否为空，若为空，则返回是否为空，若为空，则返回 truetrue；否则返回；否则返回falsefalse gettopgettop(s) (s) ： 返回返回s s的栈顶元素，但不移动栈顶指针的栈顶元素，但不

4、移动栈顶指针 push(s, x) push(s, x) ：插入元素：插入元素x x为新的栈顶元素（入栈操作为新的栈顶元素（入栈操作) ) pop(s) pop(s) ： 删除删除s s的栈顶元素并返回其值（出栈操作）的栈顶元素并返回其值（出栈操作）顺序栈的存储结构和操作的实现顺序栈的存储结构和操作的实现 顺序栈顺序栈: :是利用一组地址连续的存储单元依次存放从栈底到是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈顶的数据元素。 a1 a2 an顺序栈顺序栈s ai0n栈底栈底栈顶栈顶压入压入( (ss+=a an+1n+1弹出弹出( ( 顺序栈存储结构的描述：顺序栈存储结构的描

5、述：/*设顺序栈的最大长度为100，可依实现情况而修改*/*栈顶指针*/*顺序栈类型定义*/*s为顺序栈类型变量的指针*/顺序栈的几种状态以及在这些状态下栈顶指针顺序栈的几种状态以及在这些状态下栈顶指针toptop和栈和栈中结点的关系中结点的关系 栈为空的条件栈为空的条件 ： top=-1;top=-1;栈满的条件栈满的条件 ： top=top=maxsizemaxsize-1-1若入栈动作使地址向高端增长，称为若入栈动作使地址向高端增长，称为“向上生成向上生成”的栈；的栈；若入栈动作使地址向低端增长，称为若入栈动作使地址向低端增长，称为“向下生成向下生成”的栈；的栈； 对于向上生成的堆栈对于

6、向上生成的堆栈: :入栈入栈：栈指针：栈指针top “top “先加后压先加后压” ” : : ss+top+top=a=an+1n+1出栈出栈：栈指针：栈指针top “top “先弹后减先弹后减” ” : : e=se=stop-top- 顺序栈的基本操作顺序栈的基本操作构造一个空顺序栈构造一个空顺序栈 seqstack *initstack() seqstack *s ;s=(seqstack *)malloc(sizeof(seqstack);if(!s) printf(“空间不足空间不足”)； return null;else s-top=- -1; return s; 取顺序栈栈顶元

7、素取顺序栈栈顶元素 datatype gettop(seqstack *s) if (s-top= - -1) printf(n栈是空的栈是空的!); return false; else return s-stacks-top; 判别空栈判别空栈int stackempty(seqstack *s) if(s-top= - -1) return true; else return false; 顺序栈的入栈操作顺序栈的入栈操作例如用堆栈存放（例如用堆栈存放（a a，b b，c c，d d）aacbabatop核心语句：核心语句：顺序栈入栈函数顺序栈入栈函数pushpush（）（）seqsta

8、ck*push(seqstack*s，datatype x) if(s-top=maxsize-1) return null;/*栈满栈满*/ else s-top+; s-stacks-top=x; return s; push (b);push (c);push (d);toptoptoptop低地址低地址lpush (a);高地址高地址mbcd顺序栈出栈操作顺序栈出栈操作例如从栈中取出例如从栈中取出 dcbatoptopdcabdcbatopdcbatop低地址低地址l高地址高地址md核心语句：核心语句：pop ( );顺序栈出栈函数顺序栈出栈函数pop()pop()datatype p

9、op( seqstack *s) if(s-top=- -1) /*栈空栈空*/ printf(nthe sequence stack is empty!); return false; else s-top- -; return s-stacks-top+1; pop ( );printf( pop () );链链 栈栈链栈的构造方式链栈的构造方式用用top指向栈顶，只能在栈顶插入或删除。指向栈顶，只能在栈顶插入或删除。栈顶栈顶栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈。链栈。 a1 a2an-1 annextdata链栈

10、中每个结点由两个域构成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedef struct node datatype data; /*数据域数据域*/ struct node *next; /*指针域指针域*/ linkstack; linkstack *top; /* top为栈顶指针为栈顶指针*/ 将将x x入栈，修改栈顶入栈，修改栈顶指针指针: :top=ptop=pa an n出栈，修改栈顶指出栈，修改栈顶指针针: :top=top-nexttop=top-next链栈的入栈操作和出栈操作链栈的入栈操作和出栈操作linksta

11、ck *push(linkstack *top，datatype x) linkstack *p; p=( linkstack *)malloc(sizeof(linkstack); p-data=x; p-next=top; top=p; return top;链栈入栈操作链栈入栈操作 linkstack *pop( linkstack *top) linkstack *q; if(!top) printf(n链栈是空的链栈是空的!);return null; else q=top; /*q指向要删除的栈顶结点*/ top=top-next; /*栈顶指针下移*/ free(q); /*释放

12、q指向结点空间*/ return top; 链栈出栈操作链栈出栈操作1、数制转换（十进制数数制转换（十进制数n n转换为转换为r r进制数进制数） 设计思路：用栈暂存余数（低位值）设计思路：用栈暂存余数（低位值）2、括号匹配问题括号匹配问题 设计思路：用栈暂存左括号设计思路：用栈暂存左括号3、子程序的调用子程序的调用 设计思路：用栈暂存指令地址设计思路：用栈暂存指令地址4、逆置一个单链表逆置一个单链表 设计思路：用栈暂存每一结点的数据设计思路：用栈暂存每一结点的数据例例3.2 将十进制整数转换成二至九之间的任一进将十进制整数转换成二至九之间的任一进制数输出制数输出 将一个十进制数将一个十进制数

13、43274327转换成八进制数转换成八进制数(10347)(10347)8 8： 当当n0n0，将，将n%rn%r压压入栈入栈s s中；中；n/r n/r n n；若若n n0 0，则重复，则重复、两步；若两步；若n=0n=0，则将栈则将栈s s的内容依次出的内容依次出栈。栈。解题思路如下：解题思路如下：void conversion(int n, int r) int x=n,y=r;seqstack *s; s=initstack(); while(n!=0) push(s, n %r ); n=n/r ; printf(“n十进制数十进制数%d所对应的所对应的%d进制进制数是数是:”，x

14、,y);w h i l e ( ! s t a c k e m p t y ( s ) ) printf(“%d”,pop(s);printf(“n”); 例例3.5 3.5 利用一个顺序栈将一个带头结点的单链表利用一个顺序栈将一个带头结点的单链表（a1, ,a2, , ,an）（其中）（其中n=0n=0）逆置为（）逆置为（an, ,an-1, ,，a1）。）。1 1、建立一个、建立一个带头结点的带头结点的单链表单链表headhead；2 2、输出该单链表；、输出该单链表；3 3、建立一个空栈、建立一个空栈s s（顺序栈）（顺序栈）；4 4、依次将单链表的数据入栈；、依次将单链表的数据入栈；5

15、 5、依次将单链表的数据出栈，、依次将单链表的数据出栈，并逐个将出栈的数据存入单链并逐个将出栈的数据存入单链表的数据域（自前向后）表的数据域（自前向后）; ;6 6、再输出单链表。、再输出单链表。 解题思路如下：解题思路如下：linklist*backlinklist(linklist *head) linklist *p; p=head-next; initstack(); while(p) push(&s, p-data); p=p-next ; p=head-next; while(!stackempty(s) p-data=pop(&s); p=p-next; retu

16、rn (head);； 与线性表相同，仍为一对一关系与线性表相同，仍为一对一关系。顺序存储方式：顺序队列顺序存储方式：顺序队列( (循环队列循环队列) )和链式和链式存储方式：存储方式：链队列链队列。只能在队尾入队、队头出队，并遵循只能在队尾入队、队头出队，并遵循先进先先进先出出（fifofifo）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现按存操作，具体实现按存储方式的不同储方式的不同( (顺序队列或链队列顺序队列或链队列) )而不同。而不同。只能在表的一端进行插入运算，在表的另一只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。端进行删除运算的线性表。

17、入队、出队、建空队列、判队空或队满等。入队、出队、建空队列、判队空或队满等。尾部插尾部插入入头部删头部删除除队列队列 （queuequeue）是仅在是仅在表尾表尾进行插入操作、在进行插入操作、在表头表头进行删除操进行删除操作的线性表。它是一种先进先出作的线性表。它是一种先进先出（）（）的线性表。的线性表。例如：队列例如：队列 q= (a1 , a2 , a3 , .,an-1 , an )在队尾插入元素称为在队尾插入元素称为；在队首删除元素称为；在队首删除元素称为。队首队首队尾队尾关键是掌握关键是掌握入队入队和和出队出队操作。操作。 具体实现按具体实现按存储结构存储结构的不同（的不同（顺序队列

18、顺序队列或或链队列链队列）而）而不同。不同。（1 1）initqueueinitqueue(q)(q)： 构造一个空队列构造一个空队列q q（2 2）queueemptyqueueempty(q)(q)： 判断队列是否为空判断队列是否为空 （3 3）queuelengthqueuelength(q)(q)：求队列的长度：求队列的长度 （4 4）getheadgethead(q)(q)： 返回返回q q的队头元素，不改变队列状态的队头元素，不改变队列状态 （5 5）enqueueenqueue(q,x)(q,x)： 入队列：插入元素入队列：插入元素x x为为q q的新的队尾元素的新的队尾元素 （

19、6 6）dequeuedequeue(q)(q)： 出队列：删除出队列：删除q q的队头元素的队头元素（7 7）clearqueueclearqueue(q)(q)： 清除队列清除队列q q中的所有元素中的所有元素 链队列类型定义：链队列类型定义： typedef struct qnode *front ; /*队头指针*/ qnode *rear ; /*队尾指针*/ linkqueue; linkqueue *q; /*q是链队列指针,其中封装了队头指针和队尾指针*/结点类型定义：结点类型定义： typedef struct qnode datatype data; /*数据域*/ str

20、uct qnode *next; /*指针域*/ qnode; 链队列的几种状态示意图：链队列的几种状态示意图：此时，front=rear修改rear指针修改头结点的指针域链队列为空的特征：链队列为空的特征：front=rearfront=rear 链队列会满吗？链队列会满吗？一般不会，因为删除时有一般不会，因为删除时有freefree动作，除非内存不足！动作，除非内存不足！修改rear指针入队（尾部插入）：入队（尾部插入）：rear-next=s; rear-next=s; rear=s; rear=s;出队（头部删除）：出队（头部删除）：front-next=front-next-next

21、;front-next=front-next-next; 怎样实现链队列的怎样实现链队列的入队入队操作操作和出队和出队操作？操作？ 假设假设s s所指结点为入队结点，则有所指结点为入队结点，则有linkqueue *initqueue() linkqueue *q; /*q为链队列指针,q中封装了队头指针和队尾指针*/ qnode *p; /*p为指向链队列结点的指针*/ q=(linkqueue*)malloc(sizeof(linkqueue); p=(qnode*)malloc(sizeof(qnode); p-next=null; q-front =q-rear=p; return q

22、; datatype gethead(linkqueue *q) if(q-front=q-rear) printf(“n链队列为空!”); return false; else return q-front-next-data； /*返回队头元素的值*/ void enqueue(linkqueue *q，datatype x) qnode *p; /*p为指向链队列结点的指针*/ p = (qnode *)malloc(sizeof(qnode)； p-data = x； p-next = null； q-rear-next = p； q-rear=p； datatype dequeue(

23、linkqueue *q) qnode *p; /*p为指向链队列结点的指针*/ datatype x; if (q-front = q-rear) printf(队列为空，无法删除！队列为空，无法删除！); return false; else p = q-front-next； /*p指向链队列的队头结点*/ x = p-data； /*将队头元素的值赋给变量x*/ q-front-next = p-next； /*出队列，修改队头指针*/ if(q-rear = p) q-rear=q-front； /*若出队列后队列为空， 则还应当修改队尾指针，使队尾指针指向头结点*/ free(p)

24、； /*释放空间*/ return x; /*返回已出队元素（即原队头元素）的值*/ 循环（顺序）队列的类型定义：循环（顺序）队列的类型定义：#define maxsize 100 /* 最大队列长度 */typedef structtypedef struct datatype datamaxsize； /* 存储队列的数据空间 */ int front； /* 队头指针，若队列不空，则指向队头元素 */ int rear； /* 队尾指针，若队列不空，则指向队尾元素的下一个位置 */seqqueue; 头、尾指针与队列中元素之间的关系示意图：头、尾指针与队列中元素之间的关系示意图：入队操作

25、时的尾指针运算入队操作时的尾指针运算: rear=(rear+1)%maxsize出队操作时的头指针运算出队操作时的头指针运算: front=(front+1)%maxaize问题：问题：在循环队列中，由于队空时有在循环队列中，由于队空时有front=rear；队满时也有队满时也有front=rear；因因此我们无法通过此我们无法通过front=rear来判断队列是来判断队列是“空空”还是还是“满满”。循环队列示意图循环队列示意图循环队列的几种状态循环队列的几种状态循环队列空的条件循环队列空的条件 : : front = =rear循环队列满的条件循环队列满的条件： front = (rear

26、+1) % maxsize循环循环队列长度为：队列长度为：l=（rearfront +maxsize）% maxsize j2 j3j1 j4 j5frontrear解决办法：解决办法：少用一个元素空间，约定以少用一个元素空间，约定以“队头指针在队尾指针的下队头指针在队尾指针的下一位置一位置(指环状的下一位置指环状的下一位置)”作为队列作为队列“满满”的标志。也就是说，若的标志。也就是说，若数组的大小是数组的大小是maxsize，则该数组所表示的循环队列最多允许存储则该数组所表示的循环队列最多允许存储maxsize-1个结点。注意：个结点。注意： rear所指的结点始终为空。所指的结点始终为空

27、。循环队列满的示意图：循环队列满的示意图： 经过约定后的循环队列操作示意图 （p.70，图3.13改）循环队列的基本操作实现循环队列的基本操作实现以创建队列、入队和出队三种基本操作为例以创建队列、入队和出队三种基本操作为例1 1、构造（初始化）一个空队列、构造（初始化）一个空队列算法要求：生成一空队列算法要求：生成一空队列算法步骤：算法步骤： 为队列分配存储空间；为队列分配存储空间； 设置队列为设置队列为空队列空队列，其特征为：，其特征为： front=rear=0front=rear=0构造一个空队列构造一个空队列qseqqueue *initqueue() seqqueue *q； q=(

28、seqqueue *)malloc(sizeof(seqqueue)； /* 开辟一个足够大的存储队列空间 */ q-front = q-rear = 0； /* 将队列头尾指针置为零 */ return q； /* 返回队列的首地址 */ 算法说明：向循环队列的队尾插入一个元素。算法说明：向循环队列的队尾插入一个元素。分分 析析：(1)(1)入队入队前应当先判断队列是否已满？前应当先判断队列是否已满？ if(q-rear+1)% maxsizeif(q-rear+1)% maxsize) )=q-front)q-front) return false; return false;(2)(2)

29、入队入队动作如下动作如下: : q-dataq-rear = x; q-dataq-rear = x; q-rear=(q-rear+1)% maxsize q-rear=(q-rear+1)% maxsize; ;2 2、入队操作、入队操作int enqueue(seqqueue *q, datatype x) if(q-rear+1)maxsize=q-front) printf(“n循环队列满循环队列满!”); return false; q-dataq-rear = x； q-rear = (q-rear+1)%maxsize; return true;循环队列入队操作循环队列入队操作

30、3 3、出队操作出队操作算法说明：删除循环队列的队头元素，返回其值算法说明：删除循环队列的队头元素，返回其值 x x。 分分 析：析： （1 1）在）在出队出队前应当判断队列是否为空？前应当判断队列是否为空？ if (q-frontif (q-front=q-rear) return false;q-rear) return false; （2 2）出队出队动作动作如下如下: : x= q-dataq-front; x= q-dataq-front; q-front=(q-front+1)% maxsize q-front=(q-front+1)% maxsize; ; datatype de

31、queue(seqqueue *q) datatype x; if (q-front = = q-rear) printf(“n循环队列空！不能做删除操作！循环队列空！不能做删除操作！”); return false; x = q-data q-front ； q-front = (q-front+1)maxsize； return x；循环队列出队操作循环队列出队操作3.4 队列的应用队列的应用2 2、迷宫问题：寻找一条从迷宫入口到出口、迷宫问题：寻找一条从迷宫入口到出口的最短路径的最短路径 例例3.7 打印杨辉三角形。打印杨辉三角形。 此问题是一个初等数学问题。系数表中的第此问题是一个初等

32、数学问题。系数表中的第i i行有行有i+1i+1个个数，除了第数，除了第1 1个和最后一个数为个和最后一个数为1 1外，其余的数则为上一行中外，其余的数则为上一行中位于其左、右的两数之和。位于其左、右的两数之和。 如果要计算并输出二项式系数表（即杨辉三角形）如果要计算并输出二项式系数表（即杨辉三角形）的前的前n n行的值，则所设循环队列的最大空间应为行的值，则所设循环队列的最大空间应为n+2n+2。假设队列中已存有第假设队列中已存有第i i行的值，为计算方便，在两行之行的值，为计算方便，在两行之间均加一个间均加一个“0”0”作为行间的分隔符，则在计算第作为行间的分隔符，则在计算第i+1i+1行

33、之前，头指针正指向第行之前，头指针正指向第i i行的行的“0”0”，而尾元素为第，而尾元素为第i+1i+1行的行的“0”0”。由此，从左至右输出第。由此，从左至右输出第i i行的值，并将行的值，并将计算所得的第计算所得的第i+1i+1行的值插入队列。行的值插入队列。分析第分析第 i i 行元素与第行元素与第 i+1i+1行元素的关系如图所示行元素的关系如图所示 ： 假设假设n=4n=4，i=3i=3，则输出第，则输出第3 3行元素并求解第行元素并求解第4 4行行元素值的循环执行过程中队列的变化状态如图所元素值的循环执行过程中队列的变化状态如图所示示 ：程序如下: (n7)#define max

34、size 10 /*定义队列的最大长度*/#include #include typedef int datatype;typedef structint datamaxsize; int front; int rear;seqqueue;seqqueue *initqueue() /*队列初始化*/ seqqueue *q;q=(seqqueue*)malloc(sizeof(seqqueue);q-front = q-rear = 0;return q;void enqueue(seqqueue *q, datatype x) /*入队列*/ if(q-rear+1)%maxsize=q-front) printf(n顺序循环队列是满的!); else