数据结构第三部分栈和队列

《数据结构第三部分栈和队列》由会员分享，可在线阅读，更多相关《数据结构第三部分栈和队列（31页珍藏版）》请在装配图网上搜索。

1、 数据结构课程本章内容3.1 栈3.2 栈的应用举例3.3 队列中国科大数据结构3.1 栈3.1.1 3.1.1 栈的定义栈的定义p栈（栈（stackstack）：是限定仅在表尾进行插入和删除操作的线性表。又：是限定仅在表尾进行插入和删除操作的线性表。又称为称为后进先出后进先出（last in first outlast in first out）的线性表（简称）的线性表（简称LIFOLIFO结构）。结构）。p栈顶（栈顶（toptop）：栈表尾端。）：栈表尾端。p栈底（栈底（bottombottom）：栈表头端。）：栈表头端。例：假设栈例：假设栈 S=(aS=(a1 1,a,a2 2,a,an

2、 n)，则，则 a a1 1 称称为栈底元素，为栈底元素，a an n 为栈顶元素。栈中元素按为栈顶元素。栈中元素按a a1 1,a,a2 2,a,an n 的次序进栈，退栈的第一个元的次序进栈，退栈的第一个元素应为栈顶元素。如右图所示。素应为栈顶元素。如右图所示。出栈出栈 进栈进栈 栈顶栈顶 an .a2 栈底栈底 a1 栈的示意图栈的示意图中国科大数据结构3.1 栈3.1.2 3.1.2 栈的顺序存储结构栈的顺序存储结构p定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存定义：顺序栈（即栈的顺序存储结构）：是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针储单

3、元依次存放自栈底到栈顶的数据元素，同时附设指针toptop指示指示栈顶元素在顺序栈中的位置。栈顶元素在顺序栈中的位置。pC C语言描述语言描述typedef struct stack_tag typedef struct stack_tag elemtype elemtype*elem;elem;/指向存放数据元素的内存块指向存放数据元素的内存块 int top;int top;/栈顶标识，栈顶标识，elemtopelemtop是栈顶元素是栈顶元素 int size;int size;/栈的容量栈的容量 SQSTACK;SQSTACK;p图形表示图形表示topbottomtopbottomto

4、pbottomAABCDE栈的顺序存储结构示意图栈的顺序存储结构示意图 中国科大数据结构3.1 栈p初始化栈初始化栈int InitSqstack(SQSTACK int InitSqstack(SQSTACK*S,int n)S,int n)/初始化顺序栈，栈的容量是初始化顺序栈，栈的容量是n n。成功则返回。成功则返回1 1，否则返回，否则返回0 0 S-elem=(elemtype S-elem=(elemtype*)malloc(n)malloc(n*sizeof(elemtype);sizeof(elemtype);/为数据元素分配内存为数据元素分配内存 if(S-elem=NULL

5、)return 0;if(S-elem=NULL)return 0;/初始化失败初始化失败 S-size=n;S-size=n;/设置栈的容量设置栈的容量 S-top=-1;S-top=-1;/设置栈为空栈设置栈为空栈 return 1;return 1;p销毁栈销毁栈void DestroySqstack(SQSTACK void DestroySqstack(SQSTACK*S)S)/释放栈所占有的内存释放栈所占有的内存 free(S-elem);free(S-elem);/释放内存，并设置为释放内存，并设置为NULLNULL S-elem=NULL;S-elem=NULL;S-top=-

6、1;S-top=-1;/将其他成员设置成安全值将其他成员设置成安全值 S-size=0;S-size=0;中国科大数据结构3.1 栈p入栈入栈int Push(SQSTACK*S,elemtype e)/在栈顶一端插入数据元素在栈顶一端插入数据元素e，操作成功，则返回，操作成功，则返回1，否则返回，否则返回0 if(IsSqstackFull(*S)return 0;/栈满，操作失败栈满，操作失败 S-top+;/top增增1 S-elemS-top=e;/将将e赋值成新的栈顶赋值成新的栈顶 return 1;p出栈出栈int Pop(SQSTACK*S,elemtype*e)/获取栈顶数据元

7、素，并删除栈顶。操作成功，则返回获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回，否则返回0 if(IsSqstackEmpty(*S)return 0;/如果栈空，操作失败如果栈空，操作失败 *e=S-elemS-top;/获取栈顶元素获取栈顶元素 S-top-;/删除栈顶删除栈顶 return 1;中国科大数据结构3.1 栈p判断栈空、栈满判断栈空、栈满int IsSqstackEmpty(SQSTACK S)/如果栈空，则返回如果栈空，则返回1，否则返回，否则返回0 return=-1;/top是栈顶标识，是是栈顶标识，是-1时表示空栈时表示空栈int IsSqstackFul

8、l(SQSTACK S)/如果栈满，则返回如果栈满，则返回1，否则返回，否则返回0 return=S.size-1;/top作为作为elem的下标，其最大值是的下标，其最大值是size-1 中国科大数据结构3.1 栈3.1.3 栈的链式存储结构栈的链式存储结构 data next S 栈顶栈顶 栈底栈底 链栈示意图链栈示意图 中国科大数据结构3.2 栈的应用举例3.2.1 数制转换数制转换十进制数十进制数N和其他和其他d进制数的转换是计算机实现计算的基本问进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个是辗转相除法：题，其解决方法很多，其中一个是辗转相除法：N=(N div d

9、)d+N mod d（其中：（其中：div为整除运算，为整除运算，mod为求余运算）为求余运算）由于计算过程是从低位到高位顺序产生八进制数的各个数由于计算过程是从低位到高位顺序产生八进制数的各个数位，而输出应从高位到低位进行，恰好和计算过程相反。因此，若位，而输出应从高位到低位进行，恰好和计算过程相反。因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。的即为与输入对应的八进制数。例如：例如：(1348)10(2504)8，其运算过程如下：，其运算过程如下：NN div 8 N mod 8 13

10、48 /168 余余 4 168 /21 余余 0 21 /2 余余 5 2 /0 余余 2中国科大数据结构3.2 栈的应用举例p算法如下：算法如下：void conversion()/输入一个非负十进制整数，转换成八进制数。输入一个非负十进制整数，转换成八进制数。InitStack(S);/构造空栈构造空栈scanf(“%d”,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(s)Pop(S,e);printf(“%d”,e);/conversion中国科大数据结构3.2 栈的应用举例3.2.2 迷宫路径求解迷宫路径求解【任务描述】给定某个迷宫的布

11、局及其入口和出口的坐标（如图【任务描述】给定某个迷宫的布局及其入口和出口的坐标（如图3_9所示，注所示，注意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方意横坐标是从左向右的，但是纵坐标是从上向下的），迷宫中空白的地方可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所可以走，阴影的部分表示墙壁，走不通。设计算法找出从入口到出口的所有路径。需要解决有路径。需要解决2个问题：个问题：迷宫在计算机中如何表示。迷宫在计算机中如何表示。int maze 12=1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,0,0,1,1,1,1,0,1,0,1,

12、0,1,0,1,1,1,1,1,0,1,0,0,0,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1 ;如何探索从入口到达出口的所有路径。如何探索从入口到达出口的所有路径。深度优先探索深度优先探索+回溯：从当前位置出发，向四个方向探索，如果发现某方回溯：从当前位置出发，向四个方向探索，如果发现某方向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时向的相邻位置可走，则走过去，将那个位置当作当前位置继续探索。这时需要将原当前位置保存在栈中。如果四个方向都走不通，则退回

13、到出发点需要将原当前位置保存在栈中。如果四个方向都走不通，则退回到出发点（栈顶中的位置）。走过的地方要打上（栈顶中的位置）。走过的地方要打上“已走标记已走标记”，回退时要将，回退时要将“已走已走”标记清除。标记清除。0 1 2 3 4 5 6 7 8 901234入口(1,5)(8,1)出口10 1165中国科大数据结构3.2 栈的应用举例typedef struct int x,y;/位置坐标位置坐标 int v;/探索方向探索方向 elemtype;int movex5=0,0,1,0,-1;int movey5=0,-1,0,1,0;#define M 27#define N 25#de

14、fine MAXSIZE 200算法：算法：void go(int mazeMN,int x0,int y0,int xx,int yy)/找出找出maze中从入口中从入口(x,y)到出口到出口(xx,yy)的所有路的所有路径径 int x,y,x1,y1,v;SQSTACK s;/存放探索路径的栈存放探索路径的栈 elemtype e;InitSqstack(&s,MAXSIZE);/初始化栈初始化栈初始化栈将入口位置信息(x,y,0)入栈v0)/这次出栈是回退操作，清除原探索位置的这次出栈是回退操作，清除原探索位置的已走已走标记标记 =0;while(v=4)/*按照顺时针顺序探索按照顺时

15、针顺序探索4个方向个方向*/x1=x+movexv;y1=y+moveyv;/获取当前位置获取当前位置(x,y)v方向的相邻位置坐标方向的相邻位置坐标(x1,y1)if(x1=xx&y1=yy)/遇到出口遇到出口 输出存放在输出存放在s中的路径中的路径/*这条指令不是这条指令不是C语句语句*/V+;/换一个方向继续探索换一个方向继续探索 while(v0&x10&y1elem=(elemtype*)malloc(n+1)*sizeof(elemtype);if(q-elem=NULL)return 0;/操作失败操作失败 q-front=q-rear=0;/队首指针、队尾指针都归零队首指针、队

16、尾指针都归零 q-size=n+1;/设置容量设置容量 return 1;中国科大数据结构 队列p销毁队列销毁队列void DestroySqqueue(SQQUEUE*q)/销毁队列销毁队列 free(q-elem);/释放队列所占内存释放队列所占内存 q-elem=NULL;/将其他成员设置成安全值将其他成员设置成安全值 q-front=q-rear=0;q-size=0;p判断队空判断队空int IsSqqueueEmpty(SQQUEUE q)/如果队空，则返回如果队空，则返回1，否则返回，否则返回0 return=;中国科大数据结构 队列p入队入队int EnSqqueue(SQQU

17、EUE*q,elemtype e)/将数据元素将数据元素e入队，操作成功返回入队，操作成功返回1，否则返回，否则返回0 if(IsSqqueueFull(*q)return 0;q-elemq-rear=e;/将将e放置在队列中放置在队列中 q-rear=(q-rear+1)%q-size;/队尾指针向后移动队尾指针向后移动 return 1;p判断队满判断队满int IsSqqueueFull(SQQUEUE q)/如果队满，则返回如果队满，则返回1，否则返回，否则返回0 return=(q.rear+1)%q.size;中国科大数据结构 队列p出队出队int DeSqqueue(SQQUE

18、UE*q,elemtype*e)/将队首元素复制给将队首元素复制给*e,操作成功返回操作成功返回1，否则返回，否则返回0 if(IsSqqueueEmpty(*q)return 0;/如果队空，操作失败如果队空，操作失败 *e=q-elemq-front;/复制队首元素复制队首元素 q-front=(q-front+1)%q-size;/队首指针向后移动队首指针向后移动 return 1;p获得队列长度获得队列长度int SqqueueLen(SQQUEUE q)/返回队列长度返回队列长度 return(;中国科大数据结构 队列3.3.3 链式队列链式队列p数据类型定义：数据类型定义：type

19、def struct node_tag elemtype data;struct node_tag*next;NODE,*NODEPTR;/*定义单链表结点和指针类型定义单链表结点和指针类型*/typedef struct NODEPTR front,rear;/*队首队尾指针队首队尾指针*/LKQUEUE;p基本操作：基本操作：1初始化空队初始化空队void InitLkqueue(LKQUEUE*Q)Q-front=Q-rear=NULL;中国科大数据结构 队列p销毁队列销毁队列void DestroyLkqueue(LKQUEUE*Q)NODEPTR p;while(Q-front!=N

20、ULL)p=Q-front;Q-front=p-next;/*摘除队首结点摘除队首结点*/free(p);Q-rear=NULL;中国科大数据结构 队列p入队入队int EnLkqueue(LKQUEUE*Q,elemtype e)NODEPTR p;p=(NODEPTR)malloc(sizeof(NODE);if(p=NULL)return 0;p-data=e;p-next=NULL;if(Q-front=NULL)/如果队空，则将队首队尾指针都指向结点如果队空，则将队首队尾指针都指向结点p Q-front=Q-rear=p;else /否则将结点否则将结点p插入到队尾结点后面插入到队尾

21、结点后面 Q-rear-next=p;Q-rear=p;return 1;中国科大数据结构 队列p出队出队int DeLkqueue(LKQUEUE*Q,elemtype*e)NODEPTR p;if(Q-front=NULL)return 0;p=Q-front;Q-front=p-next;if(Q-front=NULL)Q-rear=NULL;/如果队空，则将队尾指针置如果队空，则将队尾指针置NULL *e=p-data;free(p);return 1;中国科大数据结构 队列p队列的应用举例队列的应用举例n【举例举例1 1】汽车加油站。汽车加油站。随着城市里汽车数量的急速增长，汽车加油

22、站也渐渐多了起来。随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加用算法模拟这个过程，

23、就需要设置加油车道数加2个队列。个队列。中国科大数据结构 队列n【举例举例2 2】模拟打印机缓冲区。模拟打印机缓冲区。在主机将数据输出到打印机时，会出现主机速度与打印机的打在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。为此人们设想了一种办法：为打印机设样会降低主机的使用效率。为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转

24、去做其他的事情，而打印机就从缓冲入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。冲区实际上就是一个队列结构。中国科大数据结构 队列n【举例举例3 3】CPU分时系统分时系统 在一个带有多个终端的计算机系统中，同时有多个用户需要使在一个带有多个终端的计算机系统中，同时有多个用户需要使用用CPU运行各自的应用程序，它们分别通过各自的

25、终端向操作系统运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使即可以满足每个用户的请求，又可以使CPU正常工作。正常工作。中国科大数据结构习题p本章习题参见教师网页：本章习题参见教师网页：http:/