数据结构其它线性结构数据结构其它线性结构其它线性结构其它线性结构栈队列串数组广义表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非空。操作结果：删除栈顶元素。}1.2栈的存储结构及操作实现1.2栈的存储结构及操作实现栈是一种操作受限的特殊的线性表。因此，线性表的存储结构同样适用于栈，故栈也可以采用顺序存储结构和链式存储结构。顺序栈链栈栈的顺序存储表示——顺序栈栈的顺序存储表示——顺序栈•栈的顺序存储表示——顺序栈用一维数组来模拟连续的存储空间。将0下标端设为栈底，栈的第i个元素存放在i-1下标位置。设置一个栈顶指针（或称指示器）top来指示栈顶位置。初始时，栈为空，置top=0；入栈时，top加1；出栈时，top减1；当栈满时，top等于数组空间大小。因此，top总是指在栈顶元素的后一个下标位置。(b)A入栈(c)BCDE入栈43210(a)栈空(d)EDC出栈AEDCBAEDCBAtoptoptoptop顺序栈类定义顺序栈类定义template//声明一个类模板classSqStack//顺序栈类{public:SqStack(intm);//构造函数~SqStack();//析构函数voidClear();//清空栈boolEmpty()const;//判栈空intLength()const;//求长度ElemType&Top()const;//取栈顶元素voidPush(constElemType&e);//入栈voidPop();//出栈private:ElemType*m_base;//基地址指针intm_top;//栈顶指针intm_size;//向量空间大小};顺序栈的基本操作的实现顺序栈的基本操作的实现1.栈初始化//构造函数，分配m个结点的顺序空间，构造一个空的顺序栈templateSqStack::SqStack(intm){m_top=0;m_base=newElemType[m];m_size=m;}m_topm_base…(栈底)(栈顶)m_size顺序栈的基本操作的实现顺序栈的基本操作的实现2.销毁栈//析构函数，将栈结构销毁templateSqStack::~SqStack(){if(m_base!=NULL)delete[]m_base;}顺序栈的基本操作的实现顺序栈的基本操作的实现3.清空栈//清空栈templatevoidSqStack::Clear(){m_top=0;}顺序栈的基本操作的实现顺序栈的基本操作的实现4.判栈空//若栈为空，则返回true，否则返回falsetemplateboolSqStack::Empty()const{returnm_top==0;}顺序栈的基本操作的实现顺序栈的基本操作的实现5.求长度//求栈中元素的个数templateintSqStack::Length()const{returnm_top;}顺序栈的基本操作的实现顺序栈的基本操作的实现6.取栈顶元素的值//取栈顶元素的值。先决条件是栈不空templateElemType&SqStack::Top()const{returnm_base[m_top-1];}顺序栈的基本操作的实现顺序栈的基本操作的实现7.入栈//入栈，若栈满，则先扩展空间。插入e到栈顶templatevoidSqStack::Push(constElemType&e){if(m_top>=m_size){//若栈满，则扩展空间ElemType*newbase;newbase=newE...
