《《数据结构——用C语言描述》-蔡明志-电子教案 第三章 堆栈与队列》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述》-蔡明志-电子教案 第三章 堆栈与队列（48页珍藏版）》请在金锄头文库上搜索。
1、3.1 2006,第3章 堆栈与队列,21世纪高等院校规划教材,返回总目录,3.2 2006,堆栈与队列,堆栈与队列的基本概念 堆栈的插入与删除 队列的插入与删除 循环队列 堆栈与队列的应用 如何计算后序表达式,3.3 2006,堆栈与队列的基本概念,堆栈与队列是数据结构最基本的两个主题，它们的功能却是相 当强，用途相当广。 在计算机算法（algorithms）中，堆栈（stack）与队列 （queue）是常用到的数据结构。 堆栈：是一有序表（order list），其插入（insert）和删除（delete）操 作都在同一端，此端通常称之为栈顶（top）。插入一元素于堆栈， 此操作称为入栈（
2、push），与之相反的是从堆栈删除一元素；此操作 称为出栈（pop）。由于堆栈具有后进先出的特性，所以又称堆栈是 一种后进先出（Last In First Out，LIFO）列表。 队列：也是属于线性表，与堆栈不同的是插入和删除不在同一端，删除的那 一端为队头（front），而插入的一端称为队尾（rear）。由于队列 具有先进先出（First In First Out，FIFO）的特性，因此也称队列 为先进先出列表。假若队列两端皆可做插入或删除的操作，则称之为 双端队列（double-ended queue,deque）。,3.4 2006,堆栈与队列的示意图,(a) 堆栈,（b） 队列,图3
3、-1 堆栈与队列示意图,3.5 2006,堆栈的插入与删除,堆栈的插入：插入一个元素（push an item）到堆栈，主要考虑会不会因为插入此元素而溢出（overflow），亦即插入要考虑不可超出栈的最大容量。若没有超出，则先将top插入，再将元素填入atop中。 堆栈的删除：从堆栈删除一个元素等于出栈（pop）一个元素，此时必须注意堆栈是否为空，亦即top的值是否为-1，若不为空，表示堆栈有元素存在，此时，先将atop的元素移除，然后将top减1。,3.6 2006,堆栈的插入示意图,插入元素10于堆栈如图3-2所示：,（1）top 的起始值,（2）top加1,（3）再将元素（假设10）填
4、入,图3-2 插入10于堆栈的示意图,3.7 2006,插入元素10于堆栈的程序段,void push(void) if(top = MAX-1) /*当堆栈已满时，显示出错误信息*/ printf(“The Stack is full n“); else top+; printf(“please enter an item to stack:“); scanf(“%d“, ,3.8 2006,从堆栈中删除元素40的示意图,如图3-3所示，从堆栈中删除元素40,（1）堆栈初始状况top值为3 （2）将a3，即40删除 （3）将top减1,图3-3 删除堆栈中的40,3.9 2006,从堆栈中删
5、除元素40的程序段,void pop(void) if (top 0) printf(“The stack is empty n“); else printf(“pop %d from stack n“, atop); top -; ,3.10 2006,堆栈的插入和删除 程序实例,/* file name : stack.c */ /* 使用堆栈处理数据新增、删除、输出 */ #include #include #include #define MAX 100 void push_f(void); /* 入栈函数 */ void pop_f(void); /* 出栈函数 */ void li
6、st_f(void); /* 输出函数 */ char itemMAX20; int top = -1;,3.11 2006,堆栈的插入和删除 程序实例（续1）,void main(void) char option; while(1) printf(“n *n“); printf(“ insert (push)n“); printf(“ delete (pop)n“); printf(“ listn“); printf(“ quitn“); printf(“ *n“); printf(“ Please enter your choice.“); option = getche(); swit
7、ch(option) ,3.12 2006,堆栈的插入和删除 程序实例（续2）,case 1: push_f(); break; case 2: pop_f(); break; case 3: list_f(); break; case 4: exit(0); ,3.13 2006,堆栈的插入和删除 程序实例（续3）,void push_f(void) if(top = MAX-1) /* 当堆栈已满时，显示错误 */ printf(“nnStack is full !n“); else top+; printf(“nn Please enter item to insert: “); get
8、s(itemtop); ,3.14 2006,堆栈的插入和删除 程序实例（续4）,void pop_f(void) if(top 0) /* 当堆栈没有数据存在时，则显示错误 */ printf(“nn No item, stack is empty !n“); else printf(“nn Item %s deletedn“, itemtop); top-; ,3.15 2006,堆栈的插入和删除 程序实例（续5）,void list_f(void) int count = 0, i; if(top 0) printf(“nn No item, stack is emptyn“); els
9、e printf(“nn ITEMn“); printf(“ -n“); for(i = 0; i = top; i+),3.16 2006,堆栈的插入和删除 程序实例（续6）, printf(“ %-20sn“, itemi); count+; if(count % 20 = 0) getch(); printf(“ -n“); printf(“ Total item: %dn“, count); getch(); ,3.17 2006,队列的插入与删除,队列的操作行为是先进先出，此种方式类似排队，排在前面的会先被服务，因此，可以设想数组的两端分别为front和rear端，每次插入都加在re
10、ar端，而删除（即将被服务）在front端。 当rear为MAX-1时，表示数组已到达最大容量了，此时不能再加任何元素进来，反之则数组未达最大容量，因此可以插入任何元素（如图3-4所示 ）。 删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front = rear时，表示队列是空的。 上述队列是线性队列（linear queue），表示方式为Q(0MAX-1)，但此线性队列当rear到达MAX-1时，任何插入都是不允许的，因为上述插入片段程序打印出队列是满的信息，因此它没考虑队列的前面是否还有空的位子，（如图3-5所示）。,3.18 2006,队列的
11、插入与删除示意图,图3-4 队列示意图,图3-5 rear到达MAX-1时，进行插入元素所对应的队列图,3.19 2006,队列的插入程序段,void enqueue(void) if (rear = MAX-1) printf(“The Queue is full n“); else rear+; printf(“please enter an item to queue: “); scanf(“%d“, ,3.20 2006,队列的删除程序段,删除队列的元素则需考虑队列是空的情况，因为队列为空时，表示没有元素在队列中，怎么能删除呢？当front = rear时，表示队列是空的，实现该功能的程序段如下： void dequeue(void) if (front = rear) printf(“The queue is Empty n“); else front +; printf(“pop %d from queue n“); ,3.21 2006,循环队列,队列常常以循环队列（circle queue）来表示，即 CQ(0MAX-1)，如图3-6所示。,图3-6 循环队列示意图,循环队列的初始值为front=rear=MAX-1，当有元素要插入时，利用rear=(rear+
