严蔚敏、吴伟民编著 清华大学出版社 学习网站：

Presentation on theme: "严蔚敏、吴伟民编著 清华大学出版社 学习网站："— Presentation transcript:

1 严蔚敏、吴伟民编著 清华大学出版社 学习网站：http://www.xin126.cn/list.asp?id=301
数 据 结 构 （C语言版） 严蔚敏、吴伟民编著 清华大学出版社 学习网站：

2 第3章 栈和队列 主要内容： 一、栈 二、队列 1、抽象数据类型栈的定义 2、栈的表示和实现 3、栈的应用举例 1、抽象数据类型队列的定义
第3章 栈和队列 主要内容： 一、栈 1、抽象数据类型栈的定义 2、栈的表示和实现 3、栈的应用举例 二、队列 1、抽象数据类型队列的定义 2、链队列 3、循环队列

3 第3章 栈和队列 栈与队列是两种特殊的线性结构。从数据结构角度看它们是线性表，从操作的角度看它们是操作受限的线性表。在日常生活中我们会经常遇到栈与队列的实例。例如铁路调度中用到栈，铁路购票中用到了队列。 一、栈（Stack） 1、抽象数据类型栈的定义 栈是限定只能在表的一端进行插入和删除操作的线性表。 在表中，允许插入和删除的一端称作“栈顶（top）”； 不允许插入和删除的一端称为“栈底（bottom）”。

4 栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom)：是固定端，又称为表头。 空栈：当表中没有元素时称为空栈。 设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素。

5 第3章 栈和队列 ADT Stack{ top an ai ⋯⋯ a2 bottom a1 栈的类型定义：
第3章 栈和队列 a1 a2 ai an ⋯⋯ bottom top 进栈（push） 出栈(pop) 栈的类型定义： ADT Stack{ 数据对象：D={ai | ai∈ ElemSet, i=1,2,…,n,n>=0} 数据关系：R1={<ai-1,ai>|ai-1,ai ∈D,i=2,…,n} 基本操作：初始化、进栈、出栈、取栈顶元素等 }

6 第3章 栈和队列 2、栈的表示和实现 和线性表相比，栈也有两种存储方法： （1）顺序栈 栈的顺序存储结构是利用一批地址连续的存储单元依
第3章 栈和队列 2、栈的表示和实现 和线性表相比，栈也有两种存储方法： （1）顺序栈 栈的顺序存储结构是利用一批地址连续的存储单元依 次存放自栈底到栈顶的数据元素，同时设一个栈顶指针top 指向栈顶元素的下一个位置。 通常用一维数组来实现栈的顺序 存储。习惯上以数组的小下标一端 做为栈底，top=0时为空栈；每进 栈一个元素，指针top加1，每出栈 一个元素，指针top减1。

7 栈的类型定义 #define STACK_SIZE 100 /* 栈初始向量大小 */
#define STACKINCREMENT 10 /* 存储空间分配增量 */ #typedef int ElemType ; typedef struct sqstack { ElemType *bottom; /* 栈不存在时值为NULL */ ElemType *top; /* 栈顶指针 */ int stacksize ; //当前已分配空间，以元素为单位 }SqStack ;

8 栈的初始化 Status Init_Stack(SqStack &S ) {
S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType)); if (! S.bottom) return ERROR; S.top=S.bottom ; // 栈空时栈顶和栈底指针相同 S. stacksize=STACK_SIZE; return OK ; }

9 获取栈顶元素的值 Status GetTop( SqStack &S, ElemType &e )

10 获取栈顶元素的值 /*弹出栈顶元素*/ { if ( S.top== S.bottom )
Status GetTop( SqStack &S, ElemType &e ) /*弹出栈顶元素*/ { if ( S.top== S.bottom ) return ERROR ; // 栈空，返回失败标志 e=*(S.top-1) ; return OK ; }

11 第3章 栈和队列 进栈和出栈的例子(S是SqStack类型变量) s.top (c)栈满 s.top (d)”90”出栈 s.top
第3章 栈和队列 进栈和出栈的例子(S是SqStack类型变量) s.top 85 60 74 55 90 1 2 3 4 (c)栈满 s.top 85 60 74 55 1 2 3 4 (d)”90”出栈 s.top 1 2 3 4 (a)空栈 s.top 85 1 2 3 4 (b)”85”进栈

12 压栈(元素进栈) S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ;
Status push(SqStack &S , ElemType e){ if (S.top-S.bottom>=S.stacksize) { S.bottom=(ElemType *)realloc (S.bottom,(S.stacksize+STACKINCREMENT)*sizeof(ElemType)); /* 栈满，追加存储空间 */ if (!S.bottom) exit(OVERFLOW);; S.top=S.bottom+S. stacksize ; S. stacksize+=STACKINCREMENT ; } *S.top=e; S.top++ ; //栈顶指针加1，e成为新的栈顶 return OK;

13 弹栈(元素出栈) Status pop( SqStack &S, ElemType &e )
/*弹出栈顶元素*/ { if ( S.top== S.bottom ) return ERROR ; // 栈空，返回失败标志 S.top-- ; e=*S. top ; return OK ; }

14 第3章 栈和队列 （2）链栈 栈的主要基本操作的实现 （参见教材P47） 例题分析：
第3章 栈和队列 栈的主要基本操作的实现 （参见教材P47） 例题分析： 假设有3个元素a，b，c，入栈顺序是a，b，c，则 它们的出栈顺序有几种可能？ （2）链栈 栈也可以用单链表作为存储结构。一个链栈由它的栈顶指针唯一确定 。假设 top 是SNode* 类型的变量，则 top 指向栈顶结点，top=NULL时，链栈为空。 示意思图如下：

15 第3章 栈和队列

16 第3章 栈和队列 2、栈的应用实现 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是栈应用的例子 (1) 数制转换
第3章 栈和队列 2、栈的应用实现 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是栈应用的例子 (1) 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本 问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例1 13=(13 div 8 )*8+13 mod 8

17 第3章 栈和队列 n n div 8 n mod 8 运算结果为： (1348)10=(2504)8
第3章 栈和队列 例如 (1348)10=(2504)8，其运算过程如下 其计算过程是从低位到高位顺序产生，但在输出或打印时，应从高位到底位进行，顺序相反，因此在运算过程中，将得到的八进制数各位数顺序进栈，再按出栈顺序输出即可。 n n div n mod 8 计算顺序 输出顺序 运算结果为： (1348)10=(2504)8

18 第3章 栈和队列 n n div 8 n mod 8 计算顺序 输出顺序 void conversion( ) { 1348 168 4
第3章 栈和队列 数制转换的程序 n n div 8 n mod 8 void conversion( ) { initstack(s); scanf (“%”,n); while(n){ push(s, n % 8); n=n / 8; } while(! Stackempty(s)) { pop(s,e); printf(“%d”,e); } } 计算顺序 输出顺序

19 void conversion( ) { SqStack S; int e,n;
Init_Stack(S); printf("请输入一个10进制整数："); scanf("%d", &n); while(n){ push(S, n % 8); n=n / 8; } printf("转成8进制后的数为："); while(S.top!=S.bottom) { pop(S,e); printf("%d",e); } } int main() { conversion();}

20 向量、栈都是_____结构，可以在向量的____位置插入和删除元素, 对于栈只能在 ____ 插入和删除元素。
栈是一种特殊的线性表，允许插入和删除运算的一端称为____,不允许插入和删除运算的一端称为____。

21 1. 〖00年统考题〗栈中元素的进出原则是 Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出
Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出 2.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ） Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

22 从栈中弹出（POP）一个元素时，变量T的值 C 。
设用一维数组A[1,…,n]来表示一个栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈中推入（PUSH）一个新元素时，变量T的值 B ； 从栈中弹出（POP）一个元素时，变量T的值 C 。 设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是 D 供选择的答案： B，C： ① 加1②减1 ③不变 ④清0 ⑤ 加2 ⑥减2 D：① a,b ②b,c ③c,a ④b,a ⑤ c,b ⑥ a,c

23 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
B C D

24 第3章 栈和队列 二、队列 1、抽象数据类型队列的定义
第3章 栈和队列 二、队列 1、抽象数据类型队列的定义 队列是一种先进先出（first in first out简写FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。 队列示意图如下： 如果按a1，a2，…，an的顺序入队，则出队的顺序仍然是a1，a2，…，an

25 第3章 栈和队列 队列的抽象类型定义： ADT Queue{
第3章 栈和队列 队列的抽象类型定义： ADT Queue{ 数据对象：D={ai | ai∈Elemset，i=1，2，…，n，n>=0} 数据关系：R1={<ai-1，ai>|ai-1，ai ∈D,i=1，2，…，n} 约定其中a1端为队列头，an端为队尾。 基本操作：[参见教材P59] } 关于双端队列：也是一种限定性的数据结构，是限定插入和 删除操作在表的两端进行的线性表。这两端分别端点1和端 点2。[见参教材P60图3.9]

26 第3章 栈和队列 2、链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。
第3章 栈和队列 2、链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。 在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。 typedef struct QNode{ QElemType data; struct QNode *next; } QNode,*QueuePtr;

27 第3章 栈和队列 typedef struct{ QueuePtr *front; QueuePtr *rear; }LinkQueue
第3章 栈和队列 typedef struct{ QueuePtr *front; QueuePtr *rear; }LinkQueue 链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。 队列空：Q.front==Q.rear。

28 链队列的基本运算的实现[参见教材P62] Status InitQueue(LinkQueue &Q)//初始化队列 {
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); Q.front->next=NULL; return OK; }

29 插入元素e为Q的队尾元素

30 插入元素e为Q的队尾元素 Status EnQueue(LinkQueue &Q,QElemType e) { QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

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

32 销毁队列 Status DestoryQueue(LinkQueue &Q) { while(Q.front)
Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK;

33 第3章 栈和队列 3、循环队列---队列的顺序表示和实现 （1）队列的顺序存储结构
第3章 栈和队列 3、循环队列---队列的顺序表示和实现 （1）队列的顺序存储结构 用一组地址连续的存储单元依次存放从队头到队尾的元素，同时需要附设两个指针front和rear分别指示队列头元素及队尾元素的位置。（注意：尾指针始终指向队列尾元素的下一个位置。） 采用以下的存储结构： typedef struct { ElemType elem[MAXSIZE]； int rear,front; }SeQueue;

34 第3章 栈和队列 设sq是SeQueue类型变量，则队列的数据区为：sq.elem[0]—sq.elem[MAXSIZE-1]，队头指针：sq.front；队尾指针为：sq.rear,初始化时: sq.front=sq.rear=0;

35 第3章 栈和队列 动画演示

36 第3章 栈和队列

37 第3章 栈和队列 判断队列是空还是满有两种方法：
第3章 栈和队列 判断队列是空还是满有两种方法： 1）另设一个标志位，以区分是队空还是队满； 2）约定队空条件仍是Sq.front=Sq.rear，而队满的条件为（即牺牲一个存储单元）: (rear+1)%MAX_QUEUE_SIZE =front。

38 循环队列类型定义 #define MAXQSIZE 100 //最大队列长度
  typedef struct {     QElemType  *base;  // 动态分配存储空间     int  front;     // 头指针，若队列不空，                         //  指示队列头元素的位置     int  rear;      // 尾指针  } SqQueue;

39 循环队列初始化 Status InitQueue (SqQueue &Q) {    // 构造一个空队列Q    Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType));     if (!Q.base) exit (OVERFLOW);                                             // 存储分配失败     Q.front = Q.rear = 0;      return OK;  }

40 求队列长度 int QueueLength (SqQueue Q)  { }

41 求队列长度 int QueueLength (SqQueue Q)
{   return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; }

42 Status EnQueue (SqQueue &Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q
Status EnQueue (SqQueue &Q, ElemType e) {   // 插入元素e为Q的新的队尾元素     if ((Q.rear+1) % MAXQSIZE == Q.front)         return ERROR; //队列满     Q.base[Q.rear] = e;     Q.rear = (Q.rear+1) % MAXQSIZE;     return OK; }

43 删除队头元素 Status DeQueue (SqQueue &Q, ElemType &e) {  // 若队列不空，则删除Q的队头元素，        if (Q.front == Q.rear)     return ERROR;     e = Q.base[Q.front];     Q.front = (Q.front+1) % MAXQSIZE;     return OK; }

44 1. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。【北京理工大学 2001 六、3（2分）】
A．仅修改队头指针 B. 仅修改队尾指针 C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

45 2. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。【北京工商大学 2001 一、2（3分）】
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

46 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
3. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( )。【南京理工大学 2001 一、5（1.5分）】 A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front

47 4. 循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。【中山大学 1999 一、6（1分）】
rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)

48 更多学习内容参考： 中国网页设计-数据结构
5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )【浙江大学1999 四、1(4分)】 1和 5 B. 2和4 C. 4和2 D. 5和1 更多学习内容参考： 中国网页设计-数据结构