《数据结构第3章 栈和队列ppt.ppt》由会员分享，可在线阅读，更多相关《数据结构第3章 栈和队列ppt.ppt（65页珍藏版）》请在金锄头文库上搜索。
1、第3章 栈和队列,3.1 栈 3.2 队列 3.3 应用,本章学习目标,理解栈的定义及其基本运算 掌握顺序栈和链栈的各种操作实现 理解队列的定义及其基本运算 掌握循环队列和链队列的各种操作实现 学会利用栈和队列解决一些问题,栈和队列是两种重要的线性结构,栈和队列是操作受限的线性表,3.1 栈,3.1.1 栈的基本概念 栈：限制仅在表的一端进行插入和删除操作的线性表 栈的操作特性：按先进后出(F I L O )或后进先出(I)的原则 栈顶(top)：允许插入和删除的一端。 约定top始终指向栈顶位置。 栈底(bottom): 不允许插入和删除的一端。 入栈顺序： e0 e1 e2 en-2 en
2、-1 出栈顺序： en-1 en-2 e2 e1 e0 栈可以对序列实现求逆,栈的基本运算 ： InitStack(s) 初始化操作，初始化为空栈s 。 IsEmpty(s) 判断栈空函数。如果s是空栈，返回“true”，否则返回“false”。 IsFull(s) 判断栈满函数。主要应用在顺序存储结构中，如果s栈满，返回“true”，否则返回“false”。 Push(s，x) 压栈操作。将元素x插入到栈s中，并使x成为新的栈顶元素。 Pop(s) 出栈函数。如果栈s非空，那么返回栈顶元素，并删除该栈顶元素，否则返回空值NULL。 GetTop(s) 获取栈顶元素。如果栈s非空，那么返回值为
3、栈顶元素，否则返回空值NULL。 EmptyStack(s) 清空栈操作。将栈s中的所有元素清除掉，使之成为一个空栈。 DestroyStack ()销毁栈。释放栈占用的存储空间。,栈有两种存储结构：顺序存储结构和链式存储结构。 3.1.2 栈的顺序存储结构 顺序栈：顺序存储结构的栈。 顺序栈：用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示 栈顶指针：指示栈顶位置,A,B A,C B A,(a)空栈 （b）元素A进栈 （c）元素B、C进栈 （ d）出栈一次 （ e）出栈二次,top,-1,top,top,top,top,-1,4 3 2 1 0,4 3 2 1 0,4 3
4、2 1 0,4 3 2 1 0,4 3 2 1 0,顺序栈类型定义： #define StackSize 100 /*顺序栈的初始分配空间*/ typedef struct DataType dataStackSize; /*保存栈中元素*/ int top; /*栈指针*/ SeqStack; top为int型，取值范围为0-StackSize-1。 top=-l表示栈空；top=StackSize-1表示栈满。 栈的长度：栈顶指针top+1,顺序栈的基本运算：,(1) 初始化栈运算 功能：创建一个空栈，并将初始化栈顶下标top=-1。 int InitStack(SeqStack * re
5、turn 1； ,(2)进栈运算 功能：栈顶指针加1，将进栈元素放进栈顶指针所指的位置上。 int Push(SeqStack *sq, DataType x) if(sq-top= StackSize-1)/*栈满*/ return 0; else sq-top+; sq-datasq-top=x ; return 1; ,(3)出栈运算 功能：先将栈顶元素取出，然后将栈顶指针减1。 int Pop(SeqStack *sq, DataType ,(4)取栈顶元素运算 功能：将栈中top处的元素取出赋给变量x。 int GetTop(SeqStack *sq, DataType ,(5)判断
6、栈空运算算法 功能：若栈为空(top=-1)则返回值l，否则返回值 0。 int StackEmpty(SeqStack *sq) if(sq-top=-1) return 1; else return 0; ,3.1.3 栈的链式存储结构,链栈：栈的链式存储结构。第一个结点为栈顶结点 优点：链式栈无栈满问题，空间可扩充 特点：插入与删除仅在栈顶处执行,链栈的类型定义： typedef struct stnod DataType data; /*存储结点数据*/ struct stnode *next ; /*指针域*/ LinkStack;,栈的基本运算算法：,(1)初始化栈运算 功能：创建
7、一个带头结点的链栈，头结点指针ls； 用ls-next=NULL标识栈为空栈。 void InitStack(LinkStack * ,(2) 判断栈空运算 功能：若栈为空则返回值1，否则返 回值0。 int StackEmpty(LinkStack *ls) if(ls-next=NULL) return 1; else return 0; ,(3) 进栈运算 void Push(LinkStack *ls, DataType x) LinkStack *p; p=(LinkStack*)malloc(Sizeof(LinkStack); p-data=x; p-next=ls-next;
8、ls-next=p; ,(4)出栈运算 功能: 将栈顶结点的data域值赋给x, 然后删除该栈顶结点。 int Pop(LinkStack *ls，DataType ,(5)取栈顶元素运算算法 功能：将栈顶结点的data域值赋给x。 int GetTop(LinkStack *ls, DataType ,3.2 队列,3.2.1 队列的基本概念 队列：限制插入操作只能在一端进行，而删除操作只能在另一端进行的线性表 操作特性：按先进先出(FIFO)或后进后出(LILO)的原则。 队首（front）：能进行删除的一端 队尾（rear） ：能进行插入操作的一端。,出队,入队,队首（front）,队尾
9、（rear）,队列的基本操作主要： 1) InitQueue(Q)：构造一个空队列Q。 2) QueueEmpty(Q)：判断队列是否为空。 3) QueueLength(Q)：求队列的长度。 4) GetHead(Q)：返回Q的队头元素，不改变队列状态。 5) EnQueue(Q，x)：插入元素x为Q的新的队尾元素。 6) DeQueue(Q)：删除Q的队头元素。 7) C1earQueue(Q)：清除队列Q中的所有元素。,队列有两种存储表示：顺序队列和链队列 。 3.2.2 队列的链式存储结构,链队：链式存储结构的队列；为一个同时带有首指针和尾指针的单链表 队头在链头，队尾在链尾。 链式队
10、列在进队时无队满问题，但有队空问题。,链队的类型定义： typedef struct QNode DataType data; struct QNode *next; QType; /*链队中结点的类型*/ typedef struct qptr QType *front,*rear; LinkQueue; /*链队类型*/ 队空的条件:lq-front=lq-next=NULL。,链队基本运算算法：,(1) 初始化队列运算 功能：置队列lq的rear和front均为NULL。 void InitQueue(LinkQueue * /*初始情况*/ ,(2) 入队运算 功能：创建一个新结点，将
11、其链接到链队列的末尾， 并由rear指向它。 Void EnQueue(LinkQueue *lq, DataType x) QType *s; /*创建新结点，插入到链队的末尾*/ s=(QType *)malloc(sizeof(QType); /*创建新结点，插入到链队的末尾*/ s-data=x; s-next=NULL; if(lq-front=NULL ,(3)出队运算 功能：将front结点的data域值赋给x，并删除该结点。 DataType DeQueue(LinkQueue *lq) QType *p; DataType x; if(lq-front=NULL ,(4) 取
12、队头元素运算 功能：将front指向结点的data域值赋给x DataType GetHead(LinkQueue *lq) DataType x; if(lq-front=NULL ,(5)判断队空运算算法 功能：若链队为空，则返回1；否则返回0 int QueueEmpty(LinkQueue *lq) if(lq-front=NULL ,3.2.3 循环队列,顺序队列：顺序存储结构的队列，即用一组地址连续的存储单元依次存放队头到队尾的元素； 顺序队列：实质是运算受限的顺序表；,3.2.3 循环队列,由于队列的队头和队尾的位置是变化的，设立两个指针 front 和 rear ，指针 fro
13、nt队头， rear指示队尾下一个元素； 每插入一新元素，rear 增 1，每删除一元素，front 增 1。 front = rear = 0 表示空队列，rear=MAXSIZE 表示队满。,避免假溢出有两种办法： 1) 每次一个元素出队，将整个队列向前移动一个位置。 2) 采用循环队列：将顺序队列的数据区data0MAXSIZE-1 看成一个首尾相接的圆环，头尾指针的关系不变,循环队列的类型定义： #define MAXSIZE 100 /*最大队列长度 */ typedef struct datatype dataMAXSIZE; /*存储队列的数据空间*/ int front; /*
14、队头指针，若队列不空，则指向队头元素*/ int rear; /*队尾指针，若队列不空，则指向队尾元素的下一个位置*/ SeqQueue;,rear,front,0,1,2,3,e4,e3,循环队列特点,rear,front,(3) 队空,将头尾连接成一个环，形成循环队列。,rear,(1)一般情况,front,0,1,2,3,e4,e3,(2) 队满,e3,e4,0,1,2,3,rear,e5,rear=front,e6,rear=front,front,在入队时， rear=（rear+1）%MAXSIZE。存储队列的数组就变为首尾相接的一个环，即为循环队列。 在出队时，front=(fr
15、ont+1)%MAXSIZE，实现存储空间的首尾相接。 判断队列“空”还是“满”的处理方法： 一是另设一个标志位以区别队列的“空”和“满”； 二是少用一个元素的空间，约定以“队头指针在队尾指针的下一位置(指环状的下一位置)上”作为队列“满”的标志。,5 4 3 2 1 0,5 4 3 2 1 0,5 4 3 2 1 0,d c,f e d c,g,front,rear,rear,front,rear,front,(a)正常情况 （b） 队满 （c） 队空,在循环队列中： 若front=rear，则称为队空； 若(rear+1)%maxsize=front, 则称为队满。循环队列中能装入的元素个数为maxsize-1，即浪费一个存储单元，但是这样可以给操作带来较大方便。,3循环队列的基本操作,(1)构造空队列 int InitQueue(SeqQueue *,(2) 判断队空 int QueueEmpty(SeqQueue *q) return(q-front=q-rear); /*如果队列为空，则返回1，否则返回0*/ ,(3) 入队 int EnQueue(SeqQueue*q，DataType x)
