数据结构其它线性结构数据结构其它线性结构其它线性结构其它线性结构栈队列串数组广义表1栈1栈栈（Stack）是只允许在表的同一端进行插入和删除操作的特殊的线性表
(top)(bottom)入栈(push)出栈(pop)…栈底栈顶a1a2an-1an（进栈、压入）（退栈、弹出）当栈中没有任何元素时称为空栈
1栈1栈由于栈的插入和删除操作总是在栈顶进行，所以，后进去的元素一定先出来
因而，栈又被称为后进先出（LastInFirstOut）的线性表，简称LIFO表
1,3,21,2,32,1,33,2,12,3,1若输入序列是1,2,3，则可能的输出序列有哪些
思考：1栈1栈栈的抽象数据类型定义栈的存储结构及操作实现栈的应用举例1
1栈的抽象数据类型定义1
1栈的抽象数据类型定义ADTStack{数据对象：D={ai|ai∈ElemType,i=1,2,．．．,n,n≥0}数据关系：R1={|ai-1,ai∈D,i=2,3,．．．,n}基本操作：Init(&S)操作结果：构造一个空的栈SDestroy(&S)初始条件：栈S已存在操作结果：销毁栈SClear(&S)初始条件：栈S已存在操作结果：将栈S清空Empty(S)初始条件：栈S已存在
操作结果：若S为空栈，则返回true，否则返回false
Length(S)初始条件：栈S已存在
操作结果：返回栈S的长度
Top(S)初始条件：栈S已存在，且S非空
操作结果：返回栈顶元素的值
Push(&S,e)初始条件：栈S已存在，且S未满
操作结果：插入新的元素e到栈顶
Pop(&S)初始条件：栈S已存在，且S非空
操作结果：删除栈顶元素
2栈的存储结构及操作实现1
2栈的存储结构及操作实现栈是一种操作受限的特殊的线性表
因此，线性表的存储结构同样适用于栈，故栈也可以采用顺序存储结构和链式存储结构
顺序栈链栈栈的顺序存储表示——顺序
