第3章 栈和队列.

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

1 第3章 栈和队列

2 2 3.1 栈 栈的逻辑结构 栈的顺序存储结构 栈的链式存储结构

3 3 栈的逻辑结构 1. 栈的定义 栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表，因此，对于栈来说，表尾端有其特殊的含义。 在栈中，插入元素叫作入栈，删除元素叫作出栈。通常将允许进行插入或删除操作的一端称为栈顶 (top)，栈顶将随着栈中的数据元素的增减而浮动，通过栈顶指针指明当前元素的位置；另一端称为栈底 (bottom)，栈底指针并不随着栈中的元素的增减而移动，栈底是固定的。不含元素的空表称为空栈。

4

5 5 出栈 进栈 an a2 a1 栈顶 栈底 (a) 非空栈 (b) 空栈

6 2. 栈的基本操作  InitStack (S ) 操作结果：构造一个空栈 S。  Push (S, x) 初始条件：栈 S 已经存在。
6 2. 栈的基本操作  InitStack (S ) 操作结果：构造一个空栈 S。  Push (S, x) 初始条件：栈 S 已经存在。 操作结果：插入元素 x为新的栈顶元素。  Pop (S,x) 初始条件：栈 S 已经存在且非空。 操作结果：删除栈 S 栈顶元素，并用 x返回其值。

7 7 栈的顺序存储结构 栈的顺序存储结构（简称顺序栈）是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。

8 1. 栈的顺序存储表示 # define STACK_SIZE 50; /* 存储空间初始分配量*/
8 1. 栈的顺序存储表示 # define STACK_SIZE 50; /* 存储空间初始分配量*/ typedef struct /* 顺序栈存储结构定义*/ { StackElementType elem[Stack_Size]; /* 用来存放栈中元素的 一维数组*/ int top; /* 栈顶指针,top为-1表示空栈*/ } SeqStack ; /* 顺序栈的类型名*/

9 9 2. 栈的初始化操作 S->top 称为栈顶指针，初值为-1, 可作为栈空的标记。假定 1 个元素占 1 个存储单元：当插入新元素时，先使指针 S->top 增 1再插入；当删除元素时，先删除元素再使指针 S->top 减 1 ，因此，非空栈中的栈顶指针top始终指向栈顶元素。 栈顶指针的初值也可以为0。此时：当插入新元素时，先插入再使指针S->top增1；删除元素时，先使指针S->top减1，再删除。此时，栈中的栈顶指针始终指向当前栈顶元素的下一个位置。

10 3. 基本操作在顺序栈上的实现 (1) 初始化 void InitStack ( SeqStack *S ) /* 构造一个空栈 S*/
10 3. 基本操作在顺序栈上的实现 (1) 初始化 void InitStack ( SeqStack *S ) /* 构造一个空栈 S*/ { S.top = -1； return OK; } /* InitStack*/ InitStack 算法的时间复杂性为 O(1)。

11 11 (2) 取栈顶元素 Status GetTop ( SeqStack *S, StackElementType *x) /* 如果栈空，则返回 FALSE*//* 如果栈不空，则用 x返回 S 的栈顶元素，并返回 TRUE。*/ { if ( S->top = = -1) return FALSE; /* 如果栈 S 为空，则返回FALSE*/ else { *x= S->elem[ S->top]; /*栈顶指针所指向的单元内的值赋给x指向的单元中*/ return (TRUE); } } /* GetTop*/ GetTop 算法的时间复杂性为 O(1)

12 12 (3) 将元素弹出栈 int Pop ( SeqStack *S, StackElementType *x ) /*若栈空，则返回 FASLE*/；/* 若栈不空，将栈S的栈顶元素弹出，放到x所指的存储空间中*/ { if ( S－＞top ==-1） return FALSE; /* 如果栈 S 为空，则返回FALSE*/ else { *x=S->elem[S->top]; /*将栈顶指针所指单元内的值赋给 e*/ S->top--; /* 栈顶指针减 1*/ } return OK; }/* Pop*/ Pop算法的时间复杂性为 O(1)

13 Int Push ( SeqStack *S; StackElementType x)
13 Int Push ( SeqStack *S; StackElementType x) /* 插入元素 x为新的栈顶元素*/ { if ( S->top ==Stack_Size-1) return(FALSE); /* 栈满*/ S->top++; /*栈顶指针加 1*/ S->elem[S->top]=x; /* x送入栈顶指针指向的单元*/ return(TRUE); }/* Push*/ Push 算法的时间复杂性为 O(1)

14 栈的应用（一）表达式求值问题 int ExpEvaluation( ) InitStack(&OVS); InitStack(&OPTR);
Push(&OPTR,’#’); printf(“\n\n请输入一个表达式串（以#结尾）:”); ch=getchar( ); while(ch!=‘ #’||GetTop(OPTR)!=‘#’) { if(!In(ch,OPSet)) { n=GetNumber(&ch); /*读入的数ch拼接后转化为十进制*／ push(&OVS,n); } else { switch (Compare(GetTop(OPTR),ch))

15 { case ‘<‘: /*栈顶运算符的优先级低于刚读入运算符的优先级*/ Push(&OPTR,ch);
ch=getchar( ); break; 15 case’>=‘: Pop(&OPTR,&op); Pop(&OVS,&b); Pop(&OVS,&a); v=Execute(a,op,b); Push(&OVS, v); break; } } /*end of while*/ V=GetTop(OVS); return(v); } /* ExpEvaluation*/

16 16 栈的链式存储结构 栈的链式存储结构（简称链式栈）是指栈中各数据元素独立存储，依靠指针链接建立相邻的逻辑关系。这里和线性表的单链表一样，为了操作方便起见，我们也给链式栈添加一个头结点，并令头指针指向头结点。 栈顶指针 top 惟一地确定一个链式栈，top->next 指向栈顶元素。当 top->next = NULL 时，该链式栈为空栈。链式栈没有栈满的问题。 在应用中，如果同时需要两个以上的栈，则最好采用链式栈。

17 由于栈操作是线性表操作的特例（入栈相当于线性表的插入，出栈相当于线性表的删除），则链式栈的操作易于实现，
17 1. 栈的链式存储结构 typedef struct node { StackElementType data; /* 数据域*/ struct node *next; /* 指针域*/ } LinkStackNode ,*LinkStack; // 链式栈的类型名 由于栈操作是线性表操作的特例（入栈相当于线性表的插入，出栈相当于线性表的删除），则链式栈的操作易于实现，

18 18 2. 基本操作在链式栈上的实现 (1) 取栈顶元素 int GetTop1 ( LinkStack top, StackElementType *e ) /* 如果栈 S 空，则返回 FALSE；*//*如果栈 S 不空，则用 e 返回 S 的栈顶元素，并返回 TRUE。*/ { if ( ! top->next ) /* 如果栈 S 为空，则返回FALSE*/ return(FALSE); else { /* 如果栈 S 不空，则返回栈顶元素*/ e = top->next->data; return(FALSE); } /* else */ } // GetTop1 GetTop1算法的时间复杂性为 O(1)

19 19 (2) 将元素压入栈 int Push1 ( LinkStack &top; SElemType e ) /* 将元素 e 插入到栈 S 中，成为新的栈顶元素*/ { q = ( LinkStack ) malloc ( sizeof ( SNode ) ); if ( ! q ) return (FALSE); // 存储分配失败 q->data = e; // 将数据 e 写入新结点 q->next = top->next; // 将新结点插入栈顶 top->next = q; // 修改栈顶指针 return OK; } /* Push1*/ Push1 算法的时间复杂性为 O(1)

20 (3) 将元素弹出栈 Status Pop1 ( LinkStack &top, SElemType &e )
20 (3) 将元素弹出栈 Status Pop1 ( LinkStack &top, SElemType &e ) /*若栈 S 空，则返回 ERROR ； 若栈 S 不空，则删除 S 栈顶元素，用 e 返回其值，并返回 OK */ { if ( ! top->next ) return ERROR; // 如果栈 S 为空，则返回 ERROR e = top->next->data; // 取出栈顶元素的值 q = top->next; // q 指向栈顶元素 top->next = q->next; // 删除栈顶元素 free (q); // 释放栈顶元素所占的空间 return OK; } /*Pop1*/ Pop1 算法的时间复杂性为 O(1)

21 21 3.2 队 列 队列的逻辑结构 队列的顺序存储结构 队列的链式存储结构

22 3.2.1 队列的逻辑结构 1. 队列的定义 队列 (queue) 是限定只能在表的一端进行插入，而在表的另一端进行删除操作的线性表。
22 队列的逻辑结构 1. 队列的定义 队列 (queue) 是限定只能在表的一端进行插入，而在表的另一端进行删除操作的线性表。 在队列中，我们把允许插入的一端称为队尾 (rear)，通过队尾指针指明队尾的位置；把允许删除的一端称为队头 (front)，通过队头指针指明队头的位置。队头和队尾指针将随着队列的动态变化而移动。

23 23 假设有队列 Q = ( a1, a2, a3, …, an-2, an-1, an )，则 a1 就是队头元素，an 就是队尾元素。队列中的元素是按照 a1, a2, a3, …, an-2, an-1, an 的顺序进队的，而第一个出队的元素是 a1，第二个出队的元素是 a2，只有在 ai-1 出队后 ai 才可以出队（1≤i≤n）。 当队列中没有元素时称为空队列。

24 操作结果：插入元素 e 为队列 Q 的新队尾元素。  DeleteQueue ( &Q, &x ) 初始条件：队列 S 已经存在且非空。
24 (2) 队列的抽象数据类型定义  InitQueue ( &Q ) 操作结果：构造一个空队列 Q。  EnterQueue ( &Q, x) 初始条件：队列 Q 已经存在。 操作结果：插入元素 e 为队列 Q 的新队尾元素。  DeleteQueue ( &Q, &x ) 初始条件：队列 S 已经存在且非空。 操作结果：删除队列 Q 队头元素，用 x返回其值。

25 25 队列的顺序存储结构 和顺序栈相类似，在队列的顺序存储结构中，除了利用一组连续的存储单元依次存放从队列头到队列尾的数据元素之外，还需要附设两个指针：队头指针 front 和队尾指针 rear，分别指示队列头元素和队列尾元素的位置。

26 1. 队列的顺序存储表示 # define MAXSIZE 50; //最大队列长度 typedef struct {
26 1. 队列的顺序存储表示 # define MAXSIZE 50; //最大队列长度 typedef struct { QueueElementType element[MAXSIZE]; //队列的元素空间 int front; // 队头指针 int rear; //队尾指针 } SeqQueue ; //顺序队列的类型名

27 27 2. 队列的初始化操作 初始化构建空队列时，令 Q->front = Q->rear = 0。每当插入新的队列尾元素的时候，先将新元素插入队尾指针所指位置，再使队尾指针 Q->rear 加 1；每当删除旧的队列头元素的时候，先使队头指针所指位置的元素取出，再使队头指针 Q->front 加 1。因此，在非空队列中，队头指针始终指向队列头元素，而队尾指针始终指向队列尾元素的下一个位置。

28 对下面给出的队列进行插入和删除操作的示意过程：
28 3. 循环队列 对下面给出的队列进行插入和删除操作的示意过程： 从队列头删除旧元素 从队列尾插入新元素 J1 J2 J3 J4 Q->front Q->rear J5 J6 J7 J8 Q->front Q->front Q->front Q->front Q->rear Q->rear Q->rear Q->rear 在队列中，由于不断插入新元素，队尾很快会超出数组 Q[ ] 的边界；由于不断删除旧元素，数组 Q[ ] 的开始处又会出现很多空位。

29 ① 当发生这样的情况时，把队列中的数据元素移到数组 Q[ ] 的前端，并且修改头指针和尾指针。
29 为了调剂余缺，解决办法有下面两种： ① 当发生这样的情况时，把队列中的数据元素移到数组 Q[ ] 的前端，并且修改头指针和尾指针。 ② 将数组 Q[ ] 的 “尾” 与 Q[ ] 的 “头” 逻辑上接起来，形成循环队列，这是一种较巧妙的解决办法，也是通常采用的解决办法。

30 4. 基本操作在循环队列上的实现 (1) 构造空队列
30 4. 基本操作在循环队列上的实现 (1) 构造空队列 void InitQueue ( SeqQueue *Q ) //构造一个空循环队列 Q { Q->front = Q->rear = 0; } /* InitQueue*/ InitQueue 算法的时间复杂性为 O(1)

31 31 (2) 在队列尾插入新元素 int EnterQueue ( SeqQueue *Q, QueueElemmentType x) /* 如果队列满，则返回 FALSE,如果队列不满，则插入元素x 为 Q 新的队尾元素。*/ { if ( ( Q->rear + 1 ) % MAXSIZE = = Q->front ) return (FALSE) // 如果队列满，则无法插入，报错 Q->element [Q->rear] =x; //插入 Q->rear = ( Q->rear + 1 ) % MAXSIZE; //移动队尾指针 return (TRUE); } /*EnterQueue*/ EnterQueue算法的时间复杂性为 O(1)

32 (4)删除队列头元素 int DeleteQueue ( SeqQueue *Q, QueueElemmentType*x) {
32 (4)删除队列头元素 int DeleteQueue ( SeqQueue *Q, QueueElemmentType*x) /*如果队列空，则返回 FALSE， 如果队列不空，则删除 Q 的队列头元素，用 x返回其值， 并返回 TRUE。*/ { if ( Q->front = = Q->rear ) return (FALSE); // 若队列空，则无法删除，报错 *x= Q->element [Q->front]; //带回被删除元素 Q->front = ( Q->front + 1 ) % MAXQSIZE; //移动队头指针 return (TRUE); } /* DeleteQueue*/ DeleteQueue 算法的时间复杂性为 O(1)

33 队列的应用：打印杨辉三角形前n行算法 void YangHuiTrianble( )
{ SeqQueue Q; InitQueue(&Q); //初始化队列 EnterQueue(&Q,1) //第一行元素入队列 for( n=2;n<=N; n++) //产生第n行元素并入队，同时打印第n-1行的元素 { EnterQueue(&Q,1); //杨辉三角的每行的第一个元素是1 　　for( i=1;i<=n-2;i++) { DeleteQueue (&Q, &temp); printf (“%d”, temp); GetHead (Q, &x); temp=temp+x; EnterQueue (&Q, temp); }　　　

34 3.2.3 队列的链式存储结构 当用户无法予估计所用队列的最大长度时，宜采用链式存储结构。
34 队列的链式存储结构 当用户无法予估计所用队列的最大长度时，宜采用链式存储结构。 队列的链式存储结构（简称链队列）是利用单链表表示的队列。一个链队列显然需要两个分别指向队列头和队列尾的指针（分别称为头指针和尾指针）才能唯一确定。这里，和线性表的单链表结构一样，为了操作方便起见，我们也给链式队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件为头指针和尾指针均指向头结点。

35 1. 队列的链式存储结构 typedef struct Node // 结点定义
35 1. 队列的链式存储结构 typedef struct Node // 结点定义 { QueueElementType data ; // 数据域 struct Node *next ; // 指针域 }LinkQueueNode; typedef struct // 队列定义 { LinkQueueNode; *front; // 队列头指针 LinkQueueNode; *rear; // 队列尾指针 } LinkQueue ; // 链式队列的类型名

36 3. 基本操作在链式队列上的实现 (1) 构造空队列
36 3. 基本操作在链式队列上的实现 (1) 构造空队列 int InitQueue ( LinkQueue *Q ) // 构造一个空链式队列 Q { Q->front = (LinkQueueNode*) malloc ( sizeof (LinkQueueNode ) ); if (Q->front!=NULL ) { Q->rear= Q->front; Q->front->next=NULL; return (TRUE); } else return (FALSE) // 存储分配失败 InitQueue 算法的时间复杂性为 O(1)

37 (2) 销毁队列 int DestroyQueue ( LinkQueue *Q ) // 销毁队列 Q
37 (2) 销毁队列 int DestroyQueue ( LinkQueue *Q ) // 销毁队列 Q { while ( Q->front ) { Q->rear = Q->front->next; free ( Q->front ); Q->front = Q->rear; } // while return OK; } // DestroyQueue DestroyQueue算法的时间复杂性为 O(n) Q->front x y ∧ z Q->rear

38 38 (3) 在队列尾插入新元素 int EnterQueue ( LinkQueue *Q; QueueElementType x) // 插入元素 x为 Q 的新的队列尾元素 {LinkQueueNode *NewNode; NewNode= (LinkQueueNode *) malloc ( sizeof (LinkQueueNode)); if (NewNode!=NULL) { NewNode->data =x; NewNode->next = NULL; Q->rear -> next =NewNode; Q->rear =NewNode; return(TRUE); } else return (FALSE) // 存储分配失败 } /* EnterQueue*/ EnterQueue 算法的时间复杂性为 O(1)

39 {if ( Q->front = = Q>rear ) return(FALSE);
39 int DeleteQueue ( LinkQueue *Q, QueueElemmentType *x ) /* 如果队列空，则返回 FALSE；如果队列不空，则删除 Q 的 队列头元素，用 x返回其值，并返回 TRUE。*/ {if ( Q->front = = Q>rear ) return(FALSE); p = Q->front->next; // p 指向队列的头元素结点 Q->front->next = p->next; // 删除 p 指向的结点 if ( Q->rear = = p ) Q->rear = Q->front; // 若删除的是队列最后一个元素，则令队尾指针等于队头指针 *x= p->data; // 取出队列头元素结点的数据 free ( p ); return (TRUE); } // DeleteQueue DeQueue 算法的时间复杂性为 O(1)

40 队列应用─模拟患者医院看病过程 void SeeDoctor( ) { InitQueue(Q); flag=1; while(flag){
40 while(flag){ printf(“\n请输入命令：”）； 　ch=getchar( ); switch(ch){ case ‘a’: printf(“\n病历号：”); scanf(“%d”,&n); EnterQueue(&Q, n); break;

41 case ‘n’: if (! IsEmpty(Q))
{ DeleteQueue (&Q, &n); printf(“\n病历号为％d的病人就诊”，n); } else printf(“\n无病人等候就诊”）； 　　　 break; case ‘q’: printf(“\n今天停止挂号，下列病人依次就诊：”）； 　　　　　while (!IsEmpty(Q)) { DeleteQueue(&Q,&n); printf(“%d”,n); } Flag=0; break; default: printf(“\n非法命令！”）；｝｝｝