|
|
|
|
|
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO，或后进先出）的线性表。栈进行插入和删除操作的一端称为栈顶，另一端称为栈底。不含数据元素的栈称为空栈。
|
|
|
|
|
|
.置空栈InitStack(S)：创建一个空栈S。
|
|
|
|
.判栈空Empty(S)：当栈S为空栈时返回真值；否则返回假值。
|
|
|
|
.入栈Push(S,x)：将元素x加入栈顶，并更新栈顶指针。
|
|
|
|
.出栈Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将Pop(S)定义为一个函数，它返回栈顶元素的值。
|
|
|
|
.读栈顶元素Top(S)：返回栈顶元素的值，但不修改栈顶指针。
|
|
|
|
|
|
（1）顺序存储。栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说，栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满，若栈满，则元素入栈会发生上溢现象。
|
|
|
|
利用栈底位置不变的特性，可以让两个顺序栈共享一个一维数据空间，以互补余缺，实现方法是：将两个栈的栈底位置分别设在存储空间的两端，让它们的栈顶各自向中间延伸。这样，两个栈的空间就可以相互调节，只有在整个存储空间被占满时才发生上溢，这样一来产生上溢的概率要小得多。
|
|
|
|
（2）链式存储。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必设置头节点，链表的头指针就是栈顶指针。
|
|
|
|
|
|
栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现中以及将递归过程转变为非递归过程的处理中，栈有重要的作用。
|
|
|
