文档介绍：数据结构
Data Structures
张凯
计算机学院软件工程系
2011年3月12日
队列类型的定义和实现
第3章栈和队列
栈的类型定义
栈的应用举例
栈类型的实现
§ 栈的类型定义
栈示意图
§ 栈的类型定义
a1
a2
a3
an
栈顶
栈底
……
栈的相关概念
§ 栈的类型定义
与同线性表相同,仍为一对一关系。
用顺序栈或链栈存储均可,但以顺序栈更常见
只能在栈顶运算,且访问结点时依照后进先出(LIFO)的原则。
关键是编写入栈和出栈函数,具体实现依顺序栈或链栈的不同而不同。
限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作)
栈与一般线性表有什么不同
§ 栈的类型定义
栈与一般线性表的区别:仅在于运算规则不同。
一般线性表栈
逻辑结构:一对一逻辑结构:一对一
存储结构:顺序表、链表存储结构:顺序栈、链栈
运算规则:随机存取运算规则:后进先出(LIFO)
“进”=压入=PUSH(x)
“出”=弹出=POP ( y )
栈的相关概念
§ 栈的类型定义
栈是仅在表尾进行插入、删除操作的线性表。
表尾(即an端)称为栈顶 Top;表头(即a1端)称为栈底Base
例如: 栈 s = (a1, a2, a3,……, an-1, an)
a1称为栈底元素 an称为栈顶元素
插入元素到栈顶(即表尾)的操作,称为入栈。
从栈顶(即表尾)删除最后一个元素的操作,称为出栈。
思考题
一个栈的入栈序列是a, b, c, d, e,则栈的不可能的输出序列是( )。
§ 栈的类型定义
A) e d c b a B) d e c b a
C) d c e a b D) a b c d e