数据结构-栈(1)
< 返回列表时间: 2020-07-22来源:OSCHINA
栈(stack)是 限定仅在表尾插入和删除操作的线性表。
把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。
栈又称为后进先出(Last In First Out) LIFO 或者 先进后出 (First In Last Out) FILO。
栈是一个线性表,栈的元素具有线性关系,即前驱后继关系。只不过栈是一种特殊的线性表。只支持栈顶进行插入和删除操作。

栈的插入操作,叫作进栈,也称压栈,入栈。
栈的删除操作,叫作出栈,也称弹栈。

进栈出栈变化形式
栈对线性表的插入和删除的位置进行了限制, 并没有对元素进出的时间进行限制。
在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以。

示例: 1、2、3进, 再3、2、1出。 出栈次序为321 1进、1出、2进、2出、3进、3出。 出栈次序为123 1进、2进、2出、1出、3进、3出。 出栈次序为213 1进、1出、2进、3进、3出、2出。 出栈次序为132 1进、2进、2出、3进、3出、1出。 出栈次序为231

栈的抽象数据类型
栈的插入和删除操作,可以改名为push(压)和pop(弹)。
ADT Abstract Data Type 栈 (stack)
Data
同线性表。元素具有相同的类型,相邻元素具有前驱和后继元素。
Operation
InitStack(*S): 初始化操作,建立一个空栈S。
DestroyStack(*S): 若栈存在, 则销毁它。
ClearStack(*S): 将栈清空。
StackEmpty(S): 若栈为空,返回true,否则返回false。
GetTop(S,*e): 若栈存在且非空,用e返回S的栈顶元素。
Push(*S,e): 若栈S存在,插入新元素e到栈S中并成为栈顶元素。
Pop(*S,*e): 删除栈S中栈顶元素,并用e返回其值。
StackLength(S): 返回栈S的元素个数。
endData
热门排行