|
栈和队列是两种特殊的线性表它们的逻辑结构和线性表相同只是其运算规则较线性表有更多的限制故又称它们为运算受限 的线性表栈和队列被广泛应用于各种程序设计中 栈的定义及基本运算 栈的定义 栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表 ()通常称插入删除的这一端为 栈顶 (Top)另一端称为 栈底 (Bottom) ()当表中没有元素时称为 空栈 ()栈为后进先出(Last In First Out)的线性表简称为 LIFO表 栈的修改是按后进先出的原则进行每次删除( 退栈 )的总是当前栈中最新的元素即最后插入( 进栈 )的元素而最先 插入的是被放在栈的底部要到最后才能删除 【示例】元素是以a a …a n 的顺序进栈退栈的次序却是a n a n …a 栈的基本运算 ()InitStack(S) 构造一个空栈S ()StackEmpty(S) 判栈空若S为空栈则返回TRUE否则返回FALSE ()StackFull(S) 判栈满若S为满栈则返回TRUE否则返回FALSE 注意 该运算只适用于栈的顺序存储结构 ()Push(Sx) 进栈若栈S不满则将元素x插入S的栈顶 ()Pop(S) 退栈若栈S非空则将S的栈顶元素删去并返回该元素 ()StackTop(S) 取栈顶元素若栈S非空则返回栈顶元素但不改变栈的状态 |
