第三章 栈和队列.

Presentation on theme: "第三章 栈和队列."— Presentation transcript:

1 第三章 栈和队列

2 从数据结构上看，栈和队列也是线性表，与线性表一样，数据元素的集合是数据对象，数据元素之间存在有序对的关系。
从类型的角度来说是不一样的，是两种特殊的线性表，是操作受限的线性表。 栈允许在表的一端进行插入或删除操作。 队列允许在表的一端进行插入操作，在另一端进行删除操作。

3 线性表 栈 队列 栈和队列是两种常用的数据类型 基本操作主要是两个操作：插入和删除
线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 栈和队列是两种常用的数据类型

4 3.1 栈 3.2 栈的应用举例 3.3 队列 3.4 队列的应用举例

5 3.1 栈 1、定义：限定仅在一端进行插入或删除操作的线性表。 在表中只允许进行插入和删除的一端，称为栈顶(top)，相应地，表头端称为栈底(base)。假设栈 S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。 栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。 a1 a2 a3 a4 an · · · 退栈（删） 进栈（插） 2、栈的结构示意图 3、栈的特性——先进后出（FILO）或后进先出（LIFO）栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素an。

6 栈的示意图 an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an)

7 栈的类型定义 ADT Stack { 基本操作： } ADT Stack 数据对象：
D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ <ai-1, ai >| ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack

8 InitStack(&S) DestroyStack(&S) StackLength(S) StackEmpty(S) GetTop(S, &e) ClearStack(&S) Push(&S, e) Pop(&S, &e) StackTravers(S, visit())

9 InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。

10 StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。

11 StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。

12 GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。
a1 a2 … … an

13 ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。

14 Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。
a1 a2 … … an e

15 Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
a1 a2 … … an-1 an

16 3.3 栈类型的实现 顺序栈 链栈

17 3.1.2 栈的顺序存储结构的表示及实现 1．顺序栈的表示
栈的顺序存储结构的表示及实现 1．顺序栈的表示 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，这种形式的栈也称为顺序栈。 设指针top指向栈顶元素在顺序栈中的位置，为栈顶指针。 指针base始终指向顺序栈中栈底的位置，为栈底指针。 base=NULL,表明栈结构不存在， top=base,表明栈空 top base A B C D E 顺序栈中数据元素与栈顶指针的变化：每当插入新的栈顶元素时，指针top增1；删除栈顶元素时，指针top减1，因此，非空栈中的栈顶指针top始终在的 下一个位置。 栈顶元素

18 栈的存储结构 顺序栈 s.top s.top s.top s.top s.top s.top
实现：一维数组s[M] 栈空 栈满 top s.top s.top 1 2 3 4 5 A B C D E F s.top=0 1 2 3 4 5 栈空 1 2 3 4 5 s.top F s.top s.top E s.top s.top D s.top s.top C s.top s.top B s.top A 出栈 进栈 设数组维数为M s.top=0,栈空，此时出栈，则下溢（underflow) s.top=M,栈满，此时入栈，则上溢（overflow) 栈顶指针s.top,指向实际栈顶 的空位置，初值为0

19 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct {
SElemType *base; SElemType *top; int stacksize; } SqStack; 定义一个顺序栈类型的变量： SqStack S； 在初始化空栈时一般不限定栈的最大容量，因为，栈在使用过程中所需最大空间的大小很难估计。 一般做法：先为栈分配一个基本容量即设一个存储空间初始分配量STACK_INIT_SIZE，然后在应用过程中，当栈的空间不够使用时，逐段扩大存储空间分配增量即使用常量STACKINCREMENT。

20 } {// 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE*
Status InitStack (SqStack &S) {// 构造一个空栈S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType)); if (!S.base) exit (OVERFLOW); //存储分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; }

21 入栈 Status push(SqStack &s,SElemType e) {
if(S.top-S.base>=S.stacksize) { s.base=(SElemType*)realloc(s.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; //先将e赋给S.top所指向的元素，S.top再自增 return OK;

22 栈的链式存储结构的表示及实现 1. 栈的链式存储结构的表示 链栈用线性表的链式存储结构实现的栈称为链栈。 链栈的操作易于实现，通常用单链表表示。链栈的结点结构与单链表的结点结构相同，由数据域和指针域组成，如图所示(S表示链栈)。

23 栈的链式存储结构的C语言表示： typedef struct StackNode { SElemType data; strut StackNode *next; }StackNode，*StackPtr; typedef struct { //链栈类型 StackPtr top; //栈顶指针 Stackptr base; //栈底指针 }LinkStack; 定义一个链栈类型的变量： LinkStack S；

24 an an-1 a1 栈顶指针 ∧ 栈底元素 注意: 链栈中指针的方向 链栈主要的运算，如插入、删除是在栈顶执行的。
链表的头部作栈顶是最方便的，没有必要像单链表那样为了运算方便附加一个头结点，如果加了头结点，就要在头结点之后的结点进行操作，会使算法复杂，所以一般多使用链表的头指针指向栈顶。 栈顶指针 an an-1 a1 ∧ 栈底元素 注意: 链栈中指针的方向

25 入栈 出栈 链式栈无栈满问题，空间可动态扩充 插入与删除仅在栈顶处执行 p top 栈底 top top 栈底 top x …... ^ q

26 入栈算法实现。 算法3.5 Status Push_LinkStack(LinkStack &S, SElemType e) { StackNode *p.; p=malloc(sizeof(StackNode)); p->data=e; p->next=S.top; S.top=p; return OK; }

27 出栈算法实现。 算法3.6 Status Pop_LinkStack (LinkStack &S, SElemType & e) { StackNode *p; if (S.top= =S.base) return NULL; else { e = S.top->data; p = S.top; S.top = S.top->next; free (p); return OK; } }

28 3.2栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。

29 十进制N与其它进制d的转换 算法基于原理： N = (N div d)×d + N mod d 以N = 3467，d = 8为例，则(3467)10 = (6613)8
数制转换问题

30 1．分析 按照十进制数向八进制数的转换原理，得到按低位到高位顺序产生的八进制数，产生的数字序列依次为3、1、6、6，如图3
1．分析 按照十进制数向八进制数的转换原理，得到按低位到高位顺序产生的八进制数，产生的数字序列依次为3、1、6、6，如图3.6(a)所示。按此顺序将产生的数字入栈，如图3.6(b)所示，根据数制转化原理，输出是从高位到低位的，恰好与计算过程相反，因此输出时将入栈的数字依次出栈，6、6、1、3正好是转换结果。

31

32 void conversion() { // 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 SqStack s; unsigned n; // 非负整数 SElemType e; InitStack(&s); // 初始化栈 printf("n(>=0)="); scanf("%u",&n); // 输入非负十进制整数n while(n) // 当n不等于0 {Push(&s,n%8); // 入栈n除以8的余数(8进制的低位) n=n/8; } while(!StackEmpty(s)) // 当栈不空 { Pop(&s,&e); // 弹出栈顶元素且赋值给e printf("%d",e); // 输出e printf("\n");

33 初学者往往将栈视为一个很复杂的东西，不知道如何使用，通过这个例子可以消除栈的“神秘”，当应用程序中需要一个与数据保存时顺序相反的数据时，就要想到栈。通常用顺序栈较多，因为很便利。 栈的操作调用了栈的相关基本操作，此程序是用C语言编写的。

34 3.2.2 利用栈实现迷宫求解 (i,j,l) 北4 西3 东1 × 南2 假定迷宫只能横走、
利用栈实现迷宫求解 j 假定迷宫只能横走、 坚走。下一位置是当前位置东、南、西、北四个方向上的方块。 (i,j,l) i 东1 当前 位置 × 北4 西3 南2

35 为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构—栈来保存从入口到当前位置的路径。
根据入口和出口的位置，我们规定按顺时针进行探索。 从入口到出口所走的路叫路径，当前位置都在路径上，若当前位置不通，将其从路径上删掉，走过但走不通的路，使用符号标记，防止重走。 为了保证在任何位置上都能沿原路退回，需要一个后进先出的结构—栈来保存从入口到当前位置的路径。

36 求迷宫路径算法的基本思想是： 1、若当前位置“可通”，则纳入路径，继续前进; 保留当前位置和继续走的方向
1、若当前位置“可通”，则纳入路径，继续前进; 保留当前位置和继续走的方向 2、若当前位置“不可通”，则沿原路后退，换方向继续探索; 3、若四周“均无通路”，则将当前位置从路径中删除出去。 当前位置总是在栈顶，后退指当前位置出栈，退到了前一步，换向探索，若有别的方向可以走，则继续前进；若前面位置仍不可通，则继续后退。若退到第一个位置，仍不可通，则说明迷宫无路径，否则一定可以找到路径。

37              1 4 4 1 5 3 $ $ $ 1 6 3 $ $ $ 2 6 4 $ $
i j  $     $ $    $ $ $    $ $   3

38 求迷宫中一条从入口到出口的路径的算法： 设定当前位置的初值为入口位置； do｛ 若当前位置可通， 则｛将当前位置插入栈顶；
若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为 新的当前位置； ｝ 否则 { ｝while (栈不空）； … …

39 若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则｛删去栈顶位置；// 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； ｝ 若栈空，则表明迷宫没有通路。

40 3.3 队列 定义 特性 队列是只允许在一端删除，在另一端插入的顺序表
队列 a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 定义 队列是只允许在一端删除，在另一端插入的顺序表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out)

41 队列的类型定义： ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系：
R1＝{ <a i-1,ai > | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾 基本操作： } ADT Queue

42 队列的基本操作： InitQueue(&Q) DestroyQueue(&Q) QueueEmpty(Q) QueueLength(Q)
GetHead(Q, &e) ClearQueue(&Q) DeQueue(&Q, &e) EnQueue(&Q, e) QueueTravers(Q, visit())

43 InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在。 操作结果：队列Q被销毁， 不再存在。

44 QueueEmpty(Q) 初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。

45 QueueLength(Q) 初始条件：队列Q已存在。 操作结果：返回Q的元素个数，即队列的长度。

46 GetHead(Q, &e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。
an … …

47 ClearQueue(&Q) 初始条件：队列Q已存在。 操作结果：将Q清为空队列。

48 EnQueue(&Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。
a1 a2 … … an e

49 DeQueue(&Q, &e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。
a1 a2 … … an

50 双端队列 输出受限的双端队列:一个端点允许插入和删除,另一个端点只允许插入的双端队列.
a1 a2 a3…………………….an 端1 端2 入队 出队 输出受限的双端队列:一个端点允许插入和删除,另一个端点只允许插入的双端队列. 输入受限的双端队列:一个端点允许插入和删除,另一个端点只允许删除的双端队列. 如果进一步对双端队列两端进行限定,从某个端点插入的元素只能从该端点删除,则该双端队列就转变为两个栈底相邻接的栈.

51 3.3.2 队列的顺序存储结构 1．队列顺序存储结构 以顺序结构存储的队称为顺序队。
队列的顺序存储结构 1．队列顺序存储结构 以顺序结构存储的队称为顺序队。 除了队列中的数据外，队头和队尾都是可操作的，在编程时要使用两个指针：队头指针、队尾指针。 #define MAXQSIZE //最大队列长度 //与栈不同，队列不能进行再分配。 typedef struct { QElemType *base; // 动态分配存储空间 int front， rear; // 队头队尾指针，若队列不空，指向队列 //头元素；若队列不空，指向队列尾元素 的下一个位置 } SqQueue; 定义一个顺序队类型的变量，即 SqQueue Sq；

52 队列的顺序存储结构 实现：用一维数组实现 设两个指针Sq.front,Sq.rear,约定： 存在问题:
1 2 3 4 5 队空 1 2 3 4 5 Sq.front J1,J2,J3入队 Sq.rear 1 2 3 4 5 1 2 3 4 5 J6 J5 Sq.rear Sq.rear Sq.front J4 Sq.rear Sq.front J3 J3 Sq.front Sq.rear J2 J2 Sq.front J1 J1 Sq.front J1,J2,J3出队 J4,J5,J6入队 设两个指针Sq.front,Sq.rear,约定： Sq.rear指示队尾元素的下一位置； Sq.front指示队头元素 初值Sq.front=Sq.rear=0 存在问题: 再有元素入队发生溢出

53 解决方案:循环队列 基本思想：把队列设想成环形 M-1 1 Sq.front Sq.rear …...

54 队空条件: 队满条件: 队空：Sq.front==Sq.rear 队满：Sq.front==Sq.rear
1 2 3 4 5 Sq.rear Sq.front J4 J5 J6 1 2 3 4 5 Sq.front J4,J5,J6出队 Sq.rear J7,J8,J9入队 J4 J5 J6 1 2 3 4 5 J9 J8 J7 Sq.rear Sq.front 初始状态 队空条件: Sq.front =Sq.Rear 队满条件: (Sq.rear+1)%maxsize = Sq.front

55 队列的链式存储结构 1. 概念 使用链式存储的队称为链队。 和链栈类似，用单链表来实现链队。根据队的先入先出(FIFO)原则，为了操作上的方便，使用一个头指针和尾指针，如图所示。

56 a1 an … Q.front Q.rear Q.front Q.rear 空队列
头指针front和尾指针rear是两个独立的指针变量，通常将二者封装在一个结构中。 a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列

57 链队列的表示: typedef struct QNode {// 结点类型 QElemType data;
struct QNode *next; } QNode, *QueuePtr; typedef struct { // 链队列类型 QueuePtr front; // 队头指针 QueuePtr rear; // 队尾指针 } LinkQueue; 定义一个链队列类型的变量： LinkQueue Q;

58 if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front->next = NULL;
单链队列基本操作的算法描述(部分): Status InitQueue (LinkQueue &Q) { // 构造一个空队列Q Q.rear = (QueuePtr) malloc (sizeof(Qnode)); Q.front = Q.rear; if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front->next = NULL; return OK; } Q.front Q.rear ∧

59 e a1 an Status EnQueue (LinkQueue &Q, QElemType e) { // 插入元素e为Q的新的队尾元素
p = (QueuePtr) malloc (sizeof(Qnode)); if (!p) exit (OVERFLOW); //存储分配失败 p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } p Q.front e a1 ∧ an …… ∧ Q.rear

60 a1 an a2 QElemType &e) { p if (Q.front == Q.rear) return ERROR;
Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; free (p); return OK; } p Q.front a1 ∧ an Q.rear a2 Q.rear ∧ Q.rear Q.front

61 an p Q.front Q.rear Q.front Q.rear
∧ an Q.rear Q.front p ∧ Q.rear Q.front p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front;//删除的特殊情况 free (p); return OK;

62 if (Q.front == Q.rear) return ERROR;
Status DeQueue (LinkQueue &Q, QElemType &e) { // 若队列不空，则删除Q的队头元素， //用 e 返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; free (p); return OK; } if (Q.rear == p) Q.rear = Q.front;

63 3.4 队列的应用举例 例3.2 求迷宫的最短路径。 设计一个算法找一条从迷宫入口到出口的最短路径。 1．算法的基本思想 从迷宫入口点(1, 1)出发，向四周搜索，记下所有一步能到达的坐标点；然后依次从这些点出发，再记下所有一步能到达的坐标点，……以此类推，直到到达迷宫的出口点(m,n)为止，然后从出口点沿搜索路径回溯直至入口，就找到了一条迷宫的最短路径，否则迷宫无路径。

64 2. 数据结构的选用 有关迷宫的数据结构、试探方向、如何防止重复到达某点以避免发生死循环的问题与利用栈实现迷宫求解的处理方法相同，不同的是在搜索路径过程中必须记下每一个可到达的坐标点，并从这些点出发继续向四周搜索。先到达的点先向下搜索，具有先进先出的特点，从而使用数据结构——队列来保存已到达的坐标点。 到达迷宫的出口点(m, n)后，为了能够从出口点沿搜索路径回溯直至入口，对于每一点，记下其坐标点的同时，还要记下到达该点的前驱点，因此，用一个结构数组sq[num]作为队列的存储空间，因为迷宫中每个点至多被访问一次，所以num至多等于m*n。sq的每一个结构有三个域：x，y和pre，其中x，y为所到达的点的坐标，pre为前驱点在sq中的坐标，是一个静态链域。除sq外，还有队头、队尾指针：front和rear用来指向队头和队尾元素。 3、参考程序（略）