第三章 栈_顺序栈和链栈的时间复杂度

一、栈

只允许从一端插入或删除的线性表，“先进后出”。

向栈中插入元素称为“入栈”，删除元素称为“出栈”。

二、共享栈

两个栈共同开辟一个存储空间，让一个栈的栈底为该空间的始端，另一栈的栈底为该空间的末端。

当元素进栈时，都从两端向中间延伸，这样能使剩余空间为任意一个栈使用。

三、链栈

链栈就是使用链式结构来实现栈，链栈的空间可以是不连续分配。

         顺序栈和链栈的比较

        1）时间性能比较

                顺序栈和链栈的基本操作的算法，时间复杂度均为O（1）。

        2）空间性能比较

                初始时顺序栈必须确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。

                链栈无满栈问题，只有当内存没有可用空间时才会出现满栈，但是每个元素都需要一个指针域，从而产生了结构性开销。

        一般结论：当栈在使用过程中元素个数变化较大时，用链栈比较好，反之，应该采用顺序栈。

四、栈的应用

主要在括号匹配、表达式求值、递归中。

        前缀、中缀和后缀表达式

        前、中、后缀表达式的区别取决于操作符和操作数的位置：

        1、前缀表达式：操作符在操作数前面，可通过前序遍历表达式树获得。

        2、中缀表达式：操作符在操作数中间，可通过中序遍历表达式树获得（中缀表达式通过中序遍历得到后的括号是必须的）。

        3、后缀表达式：操作符在操作数后面，可通过后序遍历表达式树获得。