《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第三章 栈和队列》由会员分享，可在线阅读，更多相关《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第三章 栈和队列（38页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,知识教学目标,栈的定义和基本运算 栈的顺序存储和链式存储 队列的定义和基本运算 队列的顺序存储和链式存储,能力培养目标,顺序栈和链栈的进栈、退栈运算 共享栈的概念和运算 顺序队列和链队的进队、出队运算 循环队列的概念和运算 栈和队列的应用,3.1.1 栈的定义与基本运算,栈（stack）是一种只能在一端进行插入或删除操作的线性表。通常称允许进行插入和删除运算的这一端为栈顶（Top），而表的另一端为栈底（Bottom）。当栈中没有结点时，称之为空栈。,栈的基本运算有以下六种： 1) 初始化栈InitStack（S） 2) 判栈空StackEmpty（S） 3) 判栈满Stack
2、Full（S） 4) 进栈Push（S，x） 5) 出栈Pop（S） 6) 取栈顶结点GetTop（S）,3.1.2 顺序栈,栈的顺序存储结构简称为顺序栈，它实际上是利用一组地址连续的存储单元依次存放从栈底到栈顶的结点，同时附设一变量top来指示栈顶结点在栈中的位置。 顺序栈的类型定义如下： #define Max 100 /假设预分配的栈空间最多为100个结点 typedef int DataType; /假设栈结点的数据类型为整型 typedef struct DataType dataMax; int top; SeqStack；,【算法3.1】 初始化栈。 void InitStack
3、(SeqStack *S) S-top=-1; 【算法3.2】 判栈空。 int StackEmpty（SeqStack *S） /判断S所指向的栈是否为空栈，当S所指的栈为空栈时，返回1，否则返回0。 return S-top = -1; ,【算法3.3】 判栈满。 int StackFull（SeqStack *S） /判断S所指向的栈是否为满栈，当S所指的栈为满栈时，返回1，否则返回0。 return S-top = Max-1; ,【算法3.4】 进栈。 void Push（SeqStack *S，DataType x） if (StackFull(S) /若顺序栈S已满，则上溢 pr
4、intf(“Stack Overflow”); else S-top+; /栈顶指针加1 S-dataS-top=x; /元素x进栈 ,【算法3.5】 出栈。 DataType Pop（SeqStack *S） if (StackEmpty（S）) printf(“Stack Underflow”); /若顺序栈S为空，则下溢 return NULL; /退出运行 else return S-dataS-top-; /返回原来的栈顶元素 ,【算法3.6】 取栈顶结点。 DataType GetTop（SeqStack *S） if (StackEmpty（S）) printf(“Stack i
5、s empty”); /若顺序栈S为空，则取栈顶元素运算非法 return NULL; else return S-dataS-top; /返回栈顶元素 ,共享栈,#define MaxSize 200 /假设两个栈的共享空间最多容纳200个元素 typedef int DataType; /假设栈结点的数据类型为整型 typedef struct DataType dataMaxSize; int top1; /栈1的栈顶元素指针 int top2; /栈2的栈顶元素指针 DSeqStack；,【算法3.7】 置空栈。 void InitDStack(SeqStack *S，int i) /
6、将共享栈置为空栈，i表示栈号 if(i = 1) S-top1=-1; /栈S1置为空栈 else S-top2= MaxSize; /栈S2置为空栈 【算法3.8】 判栈满。 int DStackFull（DSeqStack *S） /判断共享栈是否为满栈，若为满栈时，返回1，否则返回0。 if (S-top1 + 1 = S-top2) return 1; return 0; /判共享栈满的条件为S-top1 + 1 = S-top2 ,【算法3.9】 元素x进栈。 void DPush（DSeqStack *S，DataType x，int i） if (DStackFull(S) /若
7、共享栈S已满，则上溢 printf(“Stack Overflow”); if ( i = 1 ) /元素x进栈1 S-top1 +; S-dataS-top1=x; else /元素x进栈2 S-top2 -; S-dataS-top2=x; ,【算法3.10】 共享栈出栈。 DataType DPop（DSeqStack *S,int i） if (DStackEmpty（S）) printf(“Stack Underflow”); /若共享栈S为空，则下溢 return NULL; /退出运行 if ( i = 1 ) return S-dataS-top1-; /栈1元素出栈 else
8、 return S-dataS-top2+; /栈2元素出栈 ,3.1.3 链栈,链栈的类型说明如下： typedef struct node DataType data; Struct node *next; StackNode; typedef struct StackNode *top /栈顶指针 LinkStack;,【算法3.11】 初始化栈。 void InitStack(LinkStack *S) S-top=NULL; 【算法3.12】 判栈空。 int StackEmpty（LinkStack *S） return S-top = NULL; ,【算法3.13】 进栈。 vo
9、id Push（LinkStack *S，DataType x） /进栈运算，表示往S所指的栈中插入一个结点x，首先申请结点空间。然后，通过指针修改将结点插入到栈顶指针后。 StackNode *p=(StackNode *) malloc(sizeof(StackNode); p-data=x; p-next=S-top; /将新结点*p插入链栈头部 S-top=p; ,【算法3.14】 出栈。 DataType Pop（SeqStack *S） /出栈运算，表示从S所指的栈中删除一个结点。当栈非空时，直接修改栈顶指针，删除结点。 DataType x; StackNode *p=S-top
10、; /保存栈顶指针 if (StackEmpty（S）) printf(“Stack Underflow”); /下溢 return NULL; else x=p-data; /保存栈顶结点数据 S-top=p-next; /栈顶指针指向下一结点 free(p); return x; ,【算法3.15】 取栈顶结点。 DataType GetTop（SeqStack *S） /当S所指的栈非空时，取出栈顶结点，栈保存不变。 if (StackEmpty（S）) printf(“Stack is empty”); return NULL; else return S-top-data; ,3.2
11、 队列,3.2.1 队列的定义及基本运算 队列（Queue）也是一种运算受限的线性表，只允许在线性表的一端进行结点的插入运算，而在另一端进行结点的删除运算。其中允许删除的一端称为队头（front），允许删除的一端称为队尾（rear）。当队列中没有任何结点时，称为空队列。,队列的基本运算有以下六种： 1) 初始化队列InitQueue（Q） 2) 判队空QueueEmpty（Q） 3) 判队满QueueFull（Q） 4) 进队EnQueue（Q，x） 5) 出队DeQueue（Q） 6) 取队头结点GetFront（Q）,3.2.2 顺序队列,#define MaxSize 100 /假设预分
12、配的队列空间最多为100个结点 typedef int DataType; /假设队列结点的数据类型为整型 typedef struct DataType dataMaxSize; int front,rear; SeqQueue;,【算法3.16】 初始化队列。 void InitQueue(SeqQueue *Q) Q-front = Q-rear = 0; 【算法3.17】 判队空。 int QueueEmpty（SeqQueue *Q） return Q-front = Q-rear; 【算法3.18】 判队满。 int QueueFull（SeqQueue *Q） return Q-
13、rear = MaxSize-1; ,【算法3.19】 进队。 void EnQueue（SeqQueue *Q，DataType x） /进队列运算，当队列不满时，将结点x插入到Q所指的队列中。 if ( QueueFull（Q）) printf（“Quere overflow”）; /顺序队列满，则上溢 else Q-dataQ-rear=x; /元素x进队列 Q-rear+; ,【算法3.20】 出队。 DataType DeQueue（SeqQueue *Q） /出队列运算，当队列非空时，从Q所指的队列中删除一个结点。 DataType temp; if (QueueEmpty（Q）)
14、 return NULL; else temp=Q-dataQ-front; /取原来的队首元素 Q-front+; /队首元素指针加1 return temp; /返回原来的队首元素 ,【算法3.21】 取队头结点。 DataType GetFront（SeqQueue *Q） /当Q所指队列非空时，取出队列头部的结点，队列本身保持不变。 if (QueueEmpty（Q）) return NULL; else return (Q-dataQ-front); ,循环队列,循环队列所需要的具体数据类型描述如下： #define MaxSize 100 /最大队列长度 typedef struc
15、t DataType dataMaxSize; int front; /头指针，若队列不空，指向队首元素 int rear; /尾指针，若队列不空，指向队尾元素的下一个位置 SqQueue;,【算法3.22】 新元素x进循环队列。 void EnQueue（SeqQueue *Q，DataType x） if (QueueFull（Q）) printf（“Quere overflow”）; else Q-rear(Q-rear+1)MaxSize; Q-dataQ-rear=x; ,【算法3.23】 循环队列队首元素出队。 DataType DeQueue（SeqQueue *Q） DataType temp; if (QueueEmpty（Q）) return NULL; else Q-front(Q-front+1)MaxSize; temp=Q-dataQ-front; return temp; ,3.2.
