第02章 线性数据结构2-栈和队列

1、第2章,线性数据结构及其运算,2,2.1 线性表 2.2 栈和队列 2.3 数组,3,栈的定义,栈（stack）是限定在一端进行插入与删除的线性表 栈顶（top）是允许插入与删除的一端 栈底（bottom）是表中固定的一端，是栈顶的另一端 FILO（First In Last Out） 进栈 出栈,4,栈操作示例,有三个元素的进栈序列是1，2，3，举出此三个元素可能的出栈序列，并写出相应的进栈和出栈操作序列 (假设以I和O表示进栈和出栈操作)。,5,栈的顺序存储顺序栈,用一维数组作为栈的存储空间S（1:m） top指针始终指向栈顶元素的当前位置 top-1表示栈空 topm1表示栈满,(a)空

2、栈 (b)元素A入栈 (c)栈满 (d)元素Y出栈,6,建立顺序栈的C语言描述,#define MAXSIZE m /* m为栈中数据元素个数的最大可能值*/ int stackMAXSIZE; int top=-1;,7,进栈运算算法,#define MAXSIZE m int stackMAXSIZE; int top=-1; void push(int x) if(top=MAXSIZE-1) printf(栈满溢出 n); exit(1); else top+; stacktop=x; ,判断栈是否已满，若满则输出栈溢出信息，并停止执行；否则，继续执行； 栈顶指针top后移； 在栈顶指

3、针所指当前位置插入元素x。,8,退栈运算算法,#define MAXSIZE m int stackMAXSIZE; int top; int pop( ) int x; if(top=-1) printf(栈空溢出 n); exit(1); else x=stacktop; top-; return x; ,判断栈是否为空栈，若为空则输出栈下溢信息，并停止执行；否则，继续执行； 弹出(删除)栈顶元素； 栈顶指针top下移。,9,读栈顶元素算法,#define MAXSIZE m int stackMAXSIZE; int top; int pop( ) int x; if(top=-1) p

4、rintf(栈空溢出 n); exit(1); else x=stacktop; return x; ,判断栈是否为空栈，若为空则输出栈下溢信息，并停止执行；否则，继续执行； 读出栈顶元素。,10,栈的链式存储链栈,链栈的C语言描述如下： struct snode int data; struct snode *link; ; typedef struct snode SNODE; 栈顶指针仍是top，其类型为SNODE *，相当于单链表的头指针，可惟一确定一个链栈； 当top=NULL，表示一个空链栈。,11,链栈的插入运算（入栈）,申请一链栈结点，若无可用内存空间，则表示栈满，否则继续执行

5、； 在top所指结点之前插入新结点，并将top指向新申请的结点。,#include “stdlib.h” void push(SNODE *top, int x) SNODE *p; p=(SNODE *)malloc(sizeof(SNODE); if(p=NULL) printf( 内存中无可用空间，栈溢出! n); exit(1); else p-data=x; p-link=top; top=p; ,12,链栈的删除运算（退栈）,若链栈为空，则输出栈溢出信息；否则继续执行； 删除top所指结点，并使top指向被删结点的后继结点。,#include “stdlib.h” void pop

6、(SNODE *top) int x; SNODE *p; if(top=NULL) printf(栈空溢出(下溢)n); exit(1); else p=top; top=top-link; x=p-data; free(p); ,13,队列的定义,队列（Queue）是指允许在一端进行插入，而在另一端进行删除的线性表 队尾：允许插入的一端；用尾指针rear指向队尾元素，即最后被插入的元素 队头：允许删除的一端；用头指针front指向队头元素的位置 FIFO结构的线性表,具有n个元素的队列示意图,14,队列的顺序存储结构,用一维数组作为队列的存储空间Q（1:m） 队头指针front指向队列中队

7、头元素的前一个位置 队尾指针rear指向队尾元素在队列中的当前位置,(a)空队列 (b)A,B,C,D相继入队 (c)A,B,C,D相继出队 (d)E,F入队,15,入队和出队运算,入队时的相关操作： rear+；/* 修改尾指针*/ queuerear=x；/* x入队列*/ 出队时需修改头指针： front+；,16,循环队列,循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。,17,循环队列运算,队列为空：rear=front 入队：rear+1，如果rear=m，则rear=0或rear=(rear+1)%m 出队：front+1，如果fr

8、ont=m，则front=0 或front=(front+1)%m 队满判定1：front=(rear+1)%m 队满判定2：front=rear？不能确定 单独设立一个标志：,18,循环队列运算,例1 设循环队列容量为70（序号为170），经过若干入队和出队后有： front=14,rear=21。 front=23,rear=12。 求这两种情况下，循环队列中各有多少个元素？,7,59,例2 设栈S和队列Q的初始状态为空，元素e1,e2,e3, e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈S的容量至少应为多少？,3,19,

9、循环队列入队算法,判定循环队列是否已满，若满，则给出队列溢出出错信息； 队尾指针后移，将入队元素放入队尾指针所指的存储位置。,算法的C语言描述:,#define MAXSIZE m int queueMAXSIZE； int front=-1, rear=-1； void addqueue(int x) if(front=(rear+1)% MAXSIZE) printf(循环队列已满，上溢!n); exit(1); else rear=(rear+1)% MAXSIZE; queuerear=x; ,20,循环队列出队算法,判定循环队列是否为空，若空，则给出队列溢出（下溢）信息； 队头指针后

10、移一个位置。,算法的C语言描述:,#define MAXSIZE m int queueMAXSIZE； int front=-1, rear=-1 int delqueue( ) int x; if(front=rear) printf(循环队列已空，下溢！n); x=-1; else front=(front+1)% MAXSIZE; x=queuefront; return x; ,21,队列的链式存储结构,链队列满的条件是仅当内存中无可利用内存； 链队列空的条件是：front=rear,(a)空链队列 (b)非空链队列,22,链队列的运算,(a)空链队列 (b)元素x入队列 (c)元素

11、y入列 (d)元素x出列,23,链队列的入队算法,#include “stdlib.h” struct qnode int data; struct qnode *next; ; typedef struct qnode QNODE; QNODE *front, *rear; void addqueue(int x) QNODE *p; p=(QNODE *)malloc(sizeof(QNODE);,if(p=NULL) printf(内存中无可用空间。链队列已满，即上溢。 n); exit(1); else p-data=x; p-next=NULL; rear-next=p; rear=p; ,24,链队列的出队算法,if(front=rear) printf (链队列已空，即下溢。n); exit(1); else p=front-next; front-next=p-next; x=p-data; if(p-next=NULL) rear=front; free(p