第3章栈和队列 3.1栈《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 WWw.ZXXK.COM 第三章：栈和队列 6学科网 WWw.ZXXK.COM 栈和队列是两种特殊的线性表，是操作受限的 线性表，称限定性数据结构。本章主要教授内 栈 栈的应用 队列 队列的应用 6学科网 wWW,zX×K,COM 3.1栈（stack) 3.1.1栈的定义： 限定仅在表尾进行插入或删除操作的线性表，表尾一 栈顶，表头一栈底，不含元素的空表称空栈。 ●特点：先进后出(FILO)或后进先出(LIFO)。 进栈 出栈 顶 an 栈s=(al,a2,,an a2 栈底 al 6学科网 WWW.ZXXK.COM 栈的特点： 根据栈的定义可知，最先放入栈中元素在栈底，最 后放入的元素在栈顶，而删除元素刚好相反，最后 放入的元素最先删除，最先放入的元素最后删除。 也就是说，栈是一种后进先出(Last In First Out)的线性表，简称为LIFO表。 6学科网 栈的基本操作 WWW.ZXXK.COM 1.置空栈：SETNULL(S) 锊栈S置为一个空栈（不含任何元素）。 2进栈：PUSH(S,X) 将元素X插入到栈S顶部中，也称为“入栈”、“插入”、“压入”。 3.出栈：POP(S) 删除栈S中的栈顶元素，也称为"”退栈”、“删除”、“弹出”。 4.取栈顶元素：TOP(S) 取栈S中栈顶元素。与POP(S)不同，POP(S)不改变栈的状态。 5.判栈空：Empty(S) 判断栈S是否为空，若为空，返回值为true,否则返回值为false。 6学科网 WWW.ZXXK.COM 例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。WHY? 6 学科网 WWw.ZXXK.COM 例2：一个栈的输入序列是12345，若在入栈的过程中允许出 栈，则栈的输出序列43512可能实现吗？12345的输出呢？ 答：43512不可能实现，主要是其中的12顺序不能实 现； 12345的输出可以实现，只需压入一个立即弹出一 例3：如即可栈的输入序列为123456，能否得 到435612和135426的出栈序列？ 答：435612中到了12顺序不能实现： 135426可以实现。 6学科网 wWW,zX×K,COM 例4：某校计算机系考研题（程序设计基础） 设依次进入一个栈的元素序列为c,a,b,d,则可得 到出栈的元素序列是： A)a,b,c,d B)C,d,a,b C)b,c,d,a D)a,c,d,b 答：A、D可以（B、C不行) 6学科网 WWW.ZXXK.COM 3.1.2 顺序栈 由于栈是运算受限的线性表，因此线性表的存储结 构对栈也适应。 栈的顺序存储结构简称为顺序栈，它是运算受限的 线性表。因此，可用数组来实现顺序栈。因为栈底位 置是固定不变的，所以可以将栈底位置设置在数组的 两端的任何一个端点；栈顶位置是随着进栈和退栈操 作而变化的，故需用一个整型变量top来指示当前栈顶 的位置，通常称top为栈顶指钍 o6学科网 因此，顺序栈的类型定义只需将顺序表的类型 定义中的last成员改为top即可。 顺序栈的类型定义及变量说明如下： typedef int datatype; define MAXSIZE 100 typedef struct datatype data[MAXSIZE]; int top; }seqstack; seqstack *s;