25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!
目录
一.栈的基本概念
栈(stack)作为一种限定性线性表，是将线性表的插入和删除操作限制为仅在表的一端（表尾）进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)（表尾），栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器来指示；将表的另一端称为栈底（表头）。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为删栈或退栈。
根据上述定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。在图 3.1(a)所示的栈中，元素是以，... ，
，
，...，
的顺序进栈的，而退栈的次序却是
，... ，
，
，
。栈的操作是按后进先出的原则进行的，因此，栈又称为后进先出(last in first out,LFO)的线性表，简称为IFO表。在日常生活中也可以见到很多后进先出的例子，例如，手枪子弹夹中的子弹，子弹装入与子弹出膛均在弹夹的一端进行，先装人的子弹后发出，而后装入的子弹先发出；又如，如图3.1(b)所示的铁路调度站的表示，都是栈结构的实际应用。
栈的基本操作除了进栈(栈顶插入)、出栈(删除栈顶)外，还有建立(栈的初始化)、判空、判满及取栈顶元素等。下面给出栈的抽象数据类型定义。
ADT Stack{
数据对象:可以是任意类型的数据,但必须性质相同
结构关系:栈中数据元素之间是线性关系。
基本操作:
① InitStack(S)
操作前提:S为未初始化的栈。
操作结果:将S初始化为空栈。
②ClearStack(S)
操作前提:栈S已经存在。
操作结果:将栈S置成空栈。
③IsEmpty(S)
操作前提:栈S已经存在。
操作结果:判栈S是否为空栈。若S为空栈,则返回TRUE,否则返回FALSE。
④IsFull(S)
操作前提:栈S已经存在。
操作结果:判栈S是否为满栈。若S栈已满,则返回TRUE,否则返回FALSE。
⑤Push(S,x)
操作前提:栈S已经存在。
操作结果:在S的顶部插入(亦称入栈)元素x。若S栈未满,将x插入栈顶位置,并返回TRUE;若栈已满,则返回FALSE,表示操作失败。
⑥ Pop(S,x)
操作前提:栈S已经存在。
操作结果:删除(亦称出栈)栈S的顶部元素,并用x带回该值,返回TRUE;若栈为空,返回值为FALSE,表示操作失败。
⑦ GetTop(S,x)操作前提:栈S已经存在。
操作结果:取栈S的顶部元素赋给x所指向的单元,也称读栈顶。该操作与Pop(S,x)的不同之处在于,GetTop(S,x)不改变栈顶的位置。若栈为空,返回值为FALSE,表示操作失败。
}ADT Stack;
