第 六 讲 栈和队列（一）

教学目标 了解栈基本概念； 掌握栈的顺序表示及其实现； 了解栈的链式表示及其实现。 2/14

前言：上两次课讲了线性表，线性表的特点是：元素与元素之间是一一对应关系，在日常生活中，线性表的例子比比皆是如学生基本信息表，图书信息表等，我们可以对线性表做初始化、查找、插入、删除等操作。下面我们再来看几个现实生活中的例子，一叠盘子，一桶羽毛球，这也符合线性表的特点，元素与元素之间是一一对应的关系，但是我们只能在一端进行插入和删除，如取走盘子，放新盘子，这就是这一节课给大家讲的一种数据类型：栈。

栈（stack） 栈和队列是两种特殊的线性表，是操作受限的线性 表，称限定性DS 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an)

例1： 对于一个栈，给出输入项A、B、C，如果输入项序列 由ABC组成，试给出所有可能的输出序列。 A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB

例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？ 12345的输出呢？ 43512不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。

3.1.1 抽象数据类型栈的定义 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 端为栈底。 基本操作： Push(&S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(&S, &e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 … } ADT Stack 7/14

3.1.2 栈的表示与实现 顺序栈 链式栈 静态分配或动态分配 栈顶指针top是整数或指针 3.1.2 栈的表示与实现 顺序栈 静态分配或动态分配 栈顶指针top是整数或指针 栈顶指针top指向栈顶元素或 指向栈顶元素的下一个位置 链式栈 a1 top top  8/14

顺序栈的数据类型定义 typedef struct{ SElemType *base; // 栈底 int top; //栈顶指示器 下标表示法 typedef struct{ 　SElemType *base; // 栈底 　int top; //栈顶指示器 int stackSize; }SqStack;　 指针表示法 typedef struct{ 　SElemType *base; // 栈底 　SElemType *top; //栈顶指针 int stackSize; }SqStack ; 9/14

顺序栈 栈空 栈满 top top top 1 2 3 4 5 A B C D E F 1 2 3 4 5 top 1 2 3 4 5 F A B C D E F 1 2 3 4 5 top 1 2 3 4 5 F top top E top top D top top C top top B top top A base base base 栈空 出栈 进栈 栈顶指针top,指向实际栈顶 后的空位置，初值指向栈底，即top=base 设数组维数为stacksize top=base,栈空，此时出栈，则下溢（underflow) top=base+stacksize,栈满，此时入栈，则上溢（overflow)

顺序栈的基本操作-初始化 #define MAXSIZE 100 Status initStack(SqStack &S){ S.base= (SElemType *) malloc(INIT_SIZE*sizeof(SElemType)) if (S.base = =NULL) return FALSE; S.top = S.base ； S. stackSize = MAXSIZE ; return TRUE; } // initStack top  11/14

顺序栈的基本操作-入栈 if (S.top-S.base= =S.stacksize) return ERROR; Status Push(SqStack &S,SElemType e){ 　if (S.top-S.base= =S.stacksize) return ERROR; 　*S.top++=e;　//新元素入栈后栈顶指针移动 　return OK; }//Push top a1 top  12/14

顺序栈的基本操作-出栈 Status Pop(SqStack &S,SElemType &e){ 　if (S.top==S.base ) return ERROR; 　 e =*--S.top;　 　return OK; }//Pop top a1 top  13/14

取栈顶元素 int GetTop(SqStack S, SElemType &e){ 　if (S.top==S.base ) return ERROR; 　 e =*--S.top; 如何修改?　 　return OK; }//Pop top a1 top  14/14

链栈的数据类型定义 typedef struct LSNode{ SElemType data; //数据域 　SElemType *next;　//指针域 }LSNode,*LinkStack; 思考：栈顶设置应该在什么地方？ 15/14

链栈的基本操作-入栈 p = (LinkStack)(malloc(sizeof(LSNode))); P->data = e; p->next = s->next; s->next = p; 16/14

栈顶的基本操作-出栈 p = s->next; s->next = p->next; e= p->data ; free (p); 17/14

小结 本讲主要介绍了抽象数据类型栈的定义，顺序栈和链栈的基本操作及其实现。重点介绍了顺序栈的入栈和出栈操作。 18/14

作业与实验 作业 实验 实验二 栈的操作及其应用 如果序列1,2,3按顺序进栈，则可能得到的出栈序列是什么？如果序列1,2,3,4,5,6按顺序进栈，则能否得到435612和135426的出栈序列？ 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。 回文判断（P91，2.2题） 实验 实验二 栈的操作及其应用 19/14