第三章-堆栈与队列课件

第3章

堆栈与队列

21世纪高等院校规划教材返回总目录3.1

©2006堆栈与队列

堆栈与队列的基本概念

堆栈的插入与删除

队列的插入与删除

循环队列

堆栈与队列的应用

如何计算后序表达式

3.2

©2006堆栈与队列的基本概念

堆栈与队列是数据结构最基本的两个主题，它们的功能却是相当强，用途相当广。在计算机算法（algorithms）中，堆栈（stack）与队列（queue）是常用到的数据结构。堆栈：是一有序表（orderlist），其插入（insert）和删除（delete）操作都在同一端，此端通常称之为栈顶（top）。插入一元素于堆栈，此操作称为入栈（push），与之相反的是从堆栈删除一元素；此操作称为出栈（pop）。由于堆栈具有后进先出的特性，所以又称堆栈是一种后进先出（LastInFirstOut，LIFO）列表。队列：也是属于线性表，与堆栈不同的是插入和删除不在同一端，删除的那一端为队头（front），而插入的一端称为队尾（rear）。由于队列具有先进先出（FirstInFirstOut，FIFO）的特性，因此也称队列为先进先出列表。假若队列两端皆可做插入或删除的操作，则称之为双端队列（double-endedqueue,deque）。

3.3

©2006堆栈与队列的示意图(a)堆栈（b）队列图3-1堆栈与队列示意图

3.4

©2006堆栈的插入与删除堆栈的插入：插入一个元素（pushanitem）到堆栈，主要考虑会不会因为插入此元素而溢出（overflow），亦即插入要考虑不可超出栈的最大容量。若没有超出，则先将top插入，再将元素填入a[top]中。 堆栈的删除：从堆栈删除一个元素等于出栈（pop）一个元素，此时必须注意堆栈是否为空，亦即top的值是否为-1，若不为空，表示堆栈有元素存在，此时，先将a[top]的元素移除，然后将top减1。3.5

©2006堆栈的插入示意图插入元素10于堆栈如图3-2所示：

（1）top的起始值

（2）top加1

（3）再将元素（假设10）填入

图3-2插入10于堆栈的示意图

3.6

©2006插入元素10于堆栈的程序段voidpush(void){if(top>=MAX-1)/*当堆栈已满时，显示出错误信息*/

printf("TheStackisfull\n");else{top++;

printf("pleaseenteranitemtostack:");

scanf("%d",&a[top]);}}3.7

©2006从堆栈中删除元素40的示意图如图3-3所示，从堆栈中删除元素40

（1）堆栈初始状况top值为3（2）将a[3]，即40删除

（3）将top减1图3-3删除堆栈中的403.8

©2006从堆栈中删除元素40的程序段voidpop(void){if(top<0)

printf("Thestackisempty\n");else{

printf("pop%dfromstack\n",a[top]);top--;}}3.9

©2006堆栈的插入和删除——

程序实例/*filename:stack.c*//*使用堆栈处理数据—新增、删除、输出*/#include<stdio.h>#include<stdlib.h>#include<conio.h>#defineMAX100voidpush_f(void);/*入栈函数*/voidpop_f(void);/*出栈函数*/voidlist_f(void);/*输出函数*/

charitem[MAX][20];

inttop=-1;

3.10

©2006堆栈的插入和删除——

程序实例（续1）voidmain(void){

charoption;

while(1)

{

printf("\n*****************************\n");

printf("<1>insert(push)\n");

printf("<2>delete(pop)\n");

printf("<3>list\n");

printf("<4>quit\n");

printf("*****************************\n");

printf("Pleaseenteryourchoice...");

option=getche();

switch(option)

{3.11

©2006堆栈的插入和删除——

程序实例（续2）case'1':

push_f();

break;

case'2':

pop_f();

break;

case'3':

list_f();

break;

case'4':

exit(0);

}

}}3.12

©2006堆栈的插入和删除——

程序实例（续3）voidpush_f(void){

if(top>=MAX-1)/*当堆栈已满时，显示错误*/

printf("\n\nStackisfull!\n");

else

{

top++;

printf("\n\nPleaseenteritemtoinsert:");

gets(item[top]);

}}3.13

©2006堆栈的插入和删除——

程序实例（续4）voidpop_f(void){

if(top<0)/*当堆栈没有数据存在时，则显示错误*/

printf("\n\nNoitem,stackisempty!\n");

else

{

printf("\n\nItem%sdeleted\n",item[top]);

top--;

}}3.14

©2006堆栈的插入和删除——

程序实例（续5）voidlist_f(void){

intcount=0,i;

if(top<0)

printf("\n\nNoitem,stackisempty\n");

else

{

printf("\n\nITEM\n");

printf("------------------\n");

for(i=0;i<=top;i++)

3.15

©2006堆栈的插入和删除——

程序实例（续6）{

printf("%-20s\n",item[i]);

count++;

if(count%20==0)getch();

}

printf("------------------\n");

printf("Totalitem:%d\n",count);

getch();

}}3.16

©2006队列的插入与删除队列的操作行为是先进先出，此种方式类似排队，排在前面的会先被服务，因此，可以设想数组的两端分别为front和rear端，每次插入都加在rear端，而删除（即将被服务）在front端。当rear为MAX-1时，表示数组已到达最大容量了，此时不能再加任何元素进来，反之则数组未达最大容量，因此可以插入任何元素（如图3-4所示）。

删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front>=rear时，表示队列是空的。

上述队列是线性队列（linearqueue），表示方式为Q(0…MAX-1)，但此线性队列当rear到达MAX-1时，任何插入都是不允许的，因为上述插入片段程序打印出队列是满的信息，因此它没考虑队列的前面是否还有空的位子，（如图3-5所示）。

3.17

©2006队列的插入与删除示意图图3-4队列示意图图3-5rear到达MAX-1时，进行插入元素所对应的队列图3.18

©2006队列的插入程序段voidenqueue(void){if(rear>=MAX-1)

printf("TheQueueisfull\n");else{rear++;printf("pleaseenteranitemtoqueue:");

scanf("%d",&a[rear]);}}3.19

©2006队列的删除程序段删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front>=rear时，表示队列是空的，实现该功能的程序段如下：

voiddequeue(void){if(front==rear)printf("ThequeueisEmpty\n");else{front++;printf("pop%dfromqueue\n");}}3.20

©2006循环队列队列常常以循环队列（circlequeue）来表示，即CQ(0…MAX-1)，如图3-6所示。图3-6循环队列示意图

循环队列的初始值为front=rear=MAX-1，当有元素要插入时，利用rear=(rear+1)%MAX语句求出rear，以便能够使rear回到前面，看看是否还有空的位置可放。

循环队列的删除，是判断front是否和rear在同一个位置，若是则打印出循环队列是满的信息，否则，将front往前移，并插入元素。3.21

©2006循环队列——程序实例/*filename:cqueue.c*//*使用环形队列处理数据—新增、删除、输出*/#include<stdio.h>#include<stdlib.h>#include<conio.h>#defineMAX20voidenqueue_f(void);/*新增函数*/voiddequeue_f(void);/*删除函数*/voidlist_f(void);/*输出函数*/3.22

©2006循环队列——程序实例（1）charitem[MAX][20];intfront=MAX-1,rear=MAX-1,tag=0;/*tag为记忆front所在是否已储存数据，0时为没有存放数据，1时为存放数据*/voidmain(void){

charoption;

while(1) {

3.23

©2006循环队列——程序实例（2）

printf("\n*****************************\n"); printf("<1>insert(enqueue)\n"); printf("<2>delete(dequeue)\n"); printf("<3>list\n");

printf("<4>quit\n"); printf("*****************************\n"); printf("Pleaseenteryourchoice..."); option=getche(); switch(option) {3.24

©2006循环队列——程序实例（3）case'1': enqueue_f(); break; case'2': dequeue_f(); break; case'3': list_f(); break; case'4': exit(0); } }}3.25

©2006循环队列——程序实例（4）voiddequeue_f(void){ If(front==rear&&tag==0)/*当队列中没有数据存在时，显示错误*/

printf("\n\nNoitem,queueisempty!\n"); else { front=(front+1)%MAX; printf("\n\nItem%sdeleted\n",item[front]); if(front==rear)tag=0; }}3.26

©2006循环队列——程序实例（5）voidenqueue_f(void){ if(front==rear&&tag==1)/*当队列已满时，显示错误*/

printf("\n\nQueueisfull!\n"); else { rear=(rear+1)%MAX; printf("\n\nPleaseenteritemtoinsert:"); gets(item[rear]); if(front==rear)tag=1; }}3.27

©2006循环队列——程序实例（6）voidlist_f(void){ intcount=0,i; if(front==rear&&tag==0) printf("\n\nNoitem,queueisempty\n"); else {

printf("\n\nITEM\n"); printf("------------------\n"); for(i=(front+1)%MAX;i!=rear;i=++i%MAX) {

printf("%-20s\n",item[i]); count++; if(count%20==0)getch();3.28

©2006循环队列——程序实例（7）}

printf("%-20s\n",item[i]); printf("------------------\n"); printf("Totalitem:%d\n",++count); getch(); }}3.29

©2006堆栈与队列的应用由于堆栈具有先进后出的特性，因此凡是具有后来先处理特性的，都可以使用堆栈来解决。

堆栈还有一些很好的用途，就是如何将算术表达式由中序表达式变为后序表达式。运算符有优先顺序与结合性，以及又有括号先处理的问题，为了避免上述的问题，编译程序将一般的中序表达式先转化为后序表达式。假如所要解决的问题是有先进先出特性的，则宜用队列来解决，例如操作系统的工作调度（jobscheduling）。3.30

©2006堆栈应用示例——子程序调用假设主程序X调用子程序Y，子程序Y调用子程序Z，此时可以用堆栈来存储返回（return）的地址，当子程序Z执行完后，从堆栈弹出返回子程序Y的地址，子程序Y执行完再从堆栈弹出返回主程序X的地址，如图3-8所示。这里所指的返回地址是调用子程序的下一条指令。图3-8使用堆栈来解决子程序调用的示意图

3.31

©2006堆栈与队列的应用——

程序实例/*filename:intopost.c*//*将数学式子由中序表示法转为后序表示法*/#include<stdio.h>#defineMAX20voidinfix_to_postfix(char[],int);/*由中序转后序函数*/intcompare(char,char);/*比较两个运算子函数*//*在中序表示法队列及暂存堆栈中，运算符的优先级表，其优先值为INDEX/2*/3.32

©2006堆栈与队列的应用——

程序实例（续1）charinfix_priority[9]={'#',')','+','-','*','/','^','','('};charstack_priority[8]={'#','(','+','-','*','/','^',''};voidmain(void){

intrear=-1;

charinfix_q[MAX];/*储存使用者输入中序式的队列*/

printf("*********************************\n");

printf("--Usableoperator--\n");

printf("^:Exponentiation\n");

printf("*:Multiply/:Divide\n");3.33

©2006堆栈与队列的应用——

程序实例（续2）printf("+:Add-:Subtraction\n");

printf("(:LeftBrace):RightBrace\n");

printf("*********************************\n");

printf("Pleaseenterinfixexpression:");

while(infix_q[rear]!='\n')

infix_q[++rear]=getchar();

infix_q[rear]='#';/*队列结束时插入#为结束符号*/

printf("Postfixexpression:");

infix_to_postfix(infix_q,rear);

printf("\n");}3.34

©2006堆栈与队列的应用——

程序实例（续3）voidinfix_to_postfix(charinfix_q[],intrear){

inttop=0,ctr,tag=1;

charstack_t[MAX];/*用以储存还不必输出的运算符*/

stack_t[top]='#';/*于堆栈最底下插入#为结束符号*/

for(ctr=0;ctr<=rear;ctr++)

{

switch(infix_q[ctr])

{3.35

©2006堆栈与队列的应用——

程序实例（续4）/*输入为)，则应输出堆栈内运算符，直到堆栈内为(*/

case')':

while(stack_t[top]!='(')

printf("%c",stack_t[top--]);

top--;

break;

/*输入为#，则将堆栈内还未输出的运算符输出*/

case'#':

while(stack_t[top]!='#')

3.36

©2006堆栈与队列的应用——

程序实例（续5）

printf("%c",stack_t[top--]);

break;

/*输入为运算符，若小于TOP在堆栈中所指运算符，则将堆栈所指运算符输出，若大于等于TOP在堆栈中所指运算符，则将输入之运算符放入堆栈*/case'(':

case'^':

case'*':

case'/':3.37

©2006堆栈与队列的应用——

程序实例（续6）while(compare(stack_t[top],infix_q[ctr]))

printf("%c",stack_t[top--]);

stack_t[++top]=infix_q[ctr];

tag=1;

break;

case'+':

case'-':

if(tag==1)

{

stack_t[++top]=infix_q[ctr];3.38

©2006堆栈与队列的应用——

程序实例（续7）tag=2;

}

else

{

while(compare(stack_t[top],infix_q[ctr]))

printf("%c",stack_t[top--]);

stack_t[++top]=infix_q[ctr];

tag=1;

}break;3.39

©2006堆栈与队列的应用——

程序实例（续8）/*输入为操作数，则直接输出*/

default:

printf("%c",infix_q[ctr]);

if(tag==2)

printf("%c",stack_t[top--]);

tag=0;

break;

}

}}3.40

©2006堆栈与队列的应用——

程序实例（续9）/*输入为操作数，则直接输出*/

default:

printf("%c",infix_q[ctr]);

if(tag==2)

printf("%c",stack_t[top--]);

tag=0;

break;

}

}}3.41

©2006堆栈与队列的应用——

程序实例（续10）/*比较两运算符优先权，若输入运算符小于堆栈中运算符，则传回值为1，否则为0*/intcompare(charstack_o,charinfix_o){

intindex_s=0,index_i=0;

while(stack_priority[index_s]!=stack_o)

index_s++;

while(infix_priority[index_i]!=infix_o)

index_i++;

returnindex_s/2>=index_i/2?1:0;}3.42

©2006程序实例——输出结果（1）*********************************--Usableoperator--^:Exponentiation*:Multiply/:Divide+:Add-:Subtraction(:LeftBrace):RightBrace*********************************Pleaseenterinfixexpression:a+b*(c-d)/e^f-g*hPostfixexpression:abcd-*ef^/+gh*-*********************************3.43

©2006程序实例——输出结果（2）--Usableoperator--^:Exponentiation*:Multiply/:Divide+:Add-:Subtraction(:LeftBrace):RightBrace*********************************Pleaseenterinfixexpression:a*b-c^d*e/(f+g)Postfixexpression:ab*cd^e*fg+/-Pressanykeytoc