QueueEmpty(Q) 初始条件：队列Q已存在 操作结果：若队列Q为空队列，则返回TRUE；否则，返回 FALSE。 QueueLength(Q) 返回S的元素个数，即栈的长度。 GetHead(Q，&e) 初始条件：队列Q已存在且非空 操作结果： 用e返回队头元素 EnQueue(&Q，e) 初始条件：队列Q已存在 操作结果：插入元素e为Q的新的队尾元素 DeQueue(&Q，&e) 初始条件：队列Q已存在且非空 操作结果： 删除Q的队头元素，并用e返回其值
3.1、链栈的C语言定义为： typedef struct StackNode { ElemType data; Struct StackNode *next; }StackNode,*LinkStack;
top top
C B
p
B A ^
（a）
top
A
（b）
^
A
（c）
^
图3-6 链栈的存储结构图
（a）含有两个元素A、B的栈；（b）插入元素C后的栈；（c） 删除元素C、B后的栈
．． ．
2．栈的抽象数据类型定义
ADT Stack{ 数据对象: D={ai|ai∈ElemSet,i=1,2,„,n,n>=0} 数 据 关 系 ： R1={<ai-1,ai>|ai-1,ai ∈D,i=2,„,n} 约定an为栈顶，a1为栈底 基本操作： InitStack(S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在 操作结果：栈S被销毁 ClearStack(&S) 初始条件：栈S已存在 操作结果：将S清为空栈
删除
插入 删除
a1 a2
a3…………………….an
插入
端1 队列Q=(a1,a2,……,an)
端2
3.2.2
1、存储结构定义： typedef struct QNode { QElemType data; struct QNode * next; } QNode,*QueuePtr
Q->front
p
e=‘a’
^
练习
四个元素入栈的顺序是A,B,C,D.不可能的出 栈顺序是： (a)ABCD (b)DCBA (c)BADC (d)ADCB (e)DACB
3.3
队 列
3.2.1 队列的抽象数据类型定义 3.2.2 链队列 3.2.3 顺序队列(循环队列)
3.2.2 队列的抽象数据类型定义
在日常生活中队列很常见，如，我们 经常排队购物或购票. 队列在计算机系统中的应用也非常广 泛。例如：操作系统中的作业排队。
top
data next
…...
栈底 ^
– 入栈过程 top p top …... 栈底 ^
x
– 出栈过程 top
q
top
…... 栈底 ^
3.2、链栈入栈、出栈的算法实现 1）入栈操作 Status Push (LinkStack &top, ElemType e) { /*将元素e压入链栈top中*/ p=(LinkStack)malloc(sizeof(StackNode)); if(!p) exit(OVERFLOW); p->data =e; p->next=top; top=p; }
top
e p
2）出栈操作 Status pop(LinkStack &top,ElemType &e) { /*从链栈top中删除栈顶元素*/
if (top= =NULL) return ERROR; /*空栈*/ else{ p=top; top top=top->next; a e=p->data; b free(p); return OK;} c d
（2）入栈操作【算法3.2
栈的入栈操作】
Status Push(SqStack &S, Elemtype e)
{ /*将元素e插入到栈S中，作为S的新栈顶*/
elem top
if (S->top>= Stack_Size -1) return ERROR; else { S->top++;
you 2 1 0
free(p); return OK Q.front
Q.rear
}
x
p
y z
3.2.3
3.1.2
栈的表示和算法实现
1.顺序栈 2.链栈
1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即 利用一组地址连续的存储单元依次存放 自栈底到栈顶的数据元素，同时由于栈 的操作的特殊性，还必须附设一个位置 指针top（栈顶指针）来动态地指示栈 顶元素在顺序栈中的位置。通常以 top=-1表示空栈。
S->top=4 E
S->top=2
S->top=-1 S->p=0
A （b）
（a）
C B A
C B A
（c）
（d）
（a）空栈；（b）插入元素A后；（c）插入元素B、C、D、E 后；（d）删除元素E、D后
1.2、顺序栈基本运算的算法： （1）初始化栈 【算法3.1 栈的初始化】 Status InitStack(SqStack s) {/*创建一个空栈由指针S指出*/ if ((s=(SqStack*)malloc(sizeof(SqStack)))= =NULL) exit(OVERFLOW); s->top= -1; return OK; }
return TRUE;
else
Q->front
return FALSE;
}
Q->rear
算法2：入队列：
Status EnQueue(LinkQueue &Q, QElemType e) {p= (QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW); p->data = e; p->next=null; Q->rear->next =p;
0
e -1
自由区
lefttop
rightto
图3-3 两个栈共享邻接 空间
3.2
链 栈
栈也可以采用链式存储结构表示，这种结构的栈简 称为链栈。在一个链栈中，栈底就是链表的最后一个结 点，而栈顶总是链表的第一个结点。因此，新入栈的元 素即为链表新的第一个结点，只要系统还有存储空间， 就不会有栈满的情况发生。一个链栈(不带头结点)可由 栈顶指针top唯一确定，当top为NULL时，是一个空栈。
链队列
typedef struct { QueuePtr front; QueuePtr rear; }*LinkQueue ;
x Q->rear
y
z
LinkQueue Q;
2、链队列的算法：
算法1：判队列是否为空：
Status QueueEmpty( LinkQueue Q) { if Q.front = = Q.rear
S->elem[S->top]=e;
min
return OK;}
Push(S,‟you‟)
xx
（3）出栈操作 Status Pop(SqStack &S,ElemType &e) {/*若栈s不为空，则删除栈顶元素 */
elem
top
{
if(s->top<0) return ERROR; /*栈空*/ else { e=S->elem[S->top]; S->top- -;
min e=‘min’ you xx 2 1 0
return OK; }
}
（4）取栈顶元素操作
ElemType GetTop(SqStack s,ElemType &e) {/*若栈s不为空，则返回栈顶元素*/ if(s->top==-1) return ERROR; /*栈空*/
else
{e= s->elem[s->top]; return e;} } 取栈顶元素与出栈不同之处在于出栈操作改变
StackEmpty(S) 初始条件：栈S已存在 操作结果：若栈S为空栈，则返回TRUE；否则，返回FALSE。 StackLength(S) 返回S的元素个数，即栈的长度。 GetTop(S，&e) 初始条件：栈S已存在且非空 操作结果： 用e返回S的栈顶元素 Push(&S，e) 初始条件：栈S已存在 操作结果：插入元素e为新的栈顶元素
rear
2.队列的抽象数据类型定义
ADT Stack{ 数据对象: D={ai|ai∈ElemSet,i=1,2,„,n,n>=0} 数据关系：R1={<ai-1,ai>|ai-1,ai ∈D,i=2,„,n} 约定a1为队列头，an为队列尾 基本操作： InitQueue(&Q) 操作结果：构造一个空队列Q。 DestroyQueue(&Q) 初始条件：队列Q已存在 操作结果：队列Q被销毁 ClearQueue(&Q) 初始条件：队列Q已存在 操作结果：将Q清为空队列
第 3 章
栈和队列
3.1 3.2 3.3
栈(*) 队列(*) 栈和队列的应用
3.1
3.1.1
栈
栈的抽象数据类型定义
3.1.2
栈的表示和算法实现(*)
3.1.1
栈的定义
1．栈的定义 栈（stack）是一种只允许在一端进行插入和删 除的线性表，它是一种操作受限的线性表。在 表中只允许进行插入和删除的一端称为栈顶（ top），另一端称为栈底(bottom)。栈的插入操 作通常称为入栈或进栈(push)，而栈的删除操 作则称为出栈或退栈(pop)。当栈中无数据元素 出栈 入栈 时，称为空栈。 栈是按照后进先 栈顶 top an 出（LIFO）的原 则组织数据的， a2 栈底 a1 因此，栈也被称 bottom 图3-1栈的示意图 为“后进先出” 的线性表。
