栈（Stack）：是限定只能在表的一端栈顶top进行插入/删除操作的线性表，另一端称为栈底bottom

出入栈与合法性

• 在新的元素入栈之前，栈顶元素都可以选择出栈或者不出栈；因此对于相同的入栈序列，可以有多种不同的出栈序列

• 示例：当入栈序列为(1, 2, 3)时，合法的出栈序列可以有：

  • (3, 2, 1)：

    • 1入栈(1)、2入栈(1, 2)、3入栈(1, 2, 3)
    • 3出栈(1, 2)、2出栈(1)、1出栈(空栈)

  • (1, 2, 3)：

    • 1入栈(1)

  • 1出栈(空栈)

    • 2入栈(2)

  • 2出栈(空栈)

    • 3入栈(3)

  • 3出栈(空栈)

    • (1, 3, 2)：
      • 1入栈(1)
      • 1出栈(空栈)
      • 2入栈(2)、3入栈(2, 3)
      • 3出栈(2)、2出栈(空栈)
    • (2, 1, 3)：
      • 1入栈(1)、2入栈(1, 2)
      • 2出栈(1)、1出栈(空栈)
      • 3入栈(3)
      • 3出栈(空栈)
    • (2, 3, 1)：
      • 1入栈(1)、2入栈(1, 2)
      • 2出栈(1)
      • 3入栈(1, 3)
      • 3出栈(1)、1出栈(空栈)

• 而对于出栈序列(3, 1, 2)，则是不合法的出栈序列，容易解释：

  • 由于3是第一个出栈的，所以必须将1、2、3先压入栈得到(1, 2, 3)；而当3出栈后，栈顶元素为2(1, 2)，所以下一个出栈的元素只能是2，而不能是1

习题

• 1、栈S的入栈序列为e1, e2, e3, e4, e5, e6，出栈序列为e2, e4, e3, e6, e5, e1，则栈S的容量至少为（）

  • 易得，整个出入栈过程如下：
    • e1入栈、e2入栈：(e1, e2)
    • e2出栈：(e1)
    • e3入栈、e4入栈：(e1, e3, e4)
    • e4出栈**、**e3出栈：(e1)
    • e5入栈、e6入栈：(e1, e5, e6)
    • e6出栈**、e5出栈、**e1出栈：(空栈)
  • 容易看出，在整个过程中，栈中元素最多的时候为3个

• 2、元素1, 2, 3, 4, 5依次入栈，如果第一个出栈的是3，则第5个出栈的不可能是（）

  • 由于第一个出栈的是3，故1、2、3必须按顺序压入栈；从而导致1在2的下方，所以当1想要出栈时，必须先将2出栈，因此2不可能作为最后一个（第5个）出栈