堆栈简介

堆栈是 LIFO（后进先出）数据结构，即添加到堆栈的最新（或后进）元素将是第一个被移除的元素（先出）。

让我们考虑一个盒子里的书籍的例子。一次只能在框中添加或删除一本书，并且只能从顶部添加和删除。

现在，前两本书的盒子看起来像这样：

  |--------|
  | book 2 | ◀──── top of box
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

如果我们添加第 3 册，它将位于顶部。在第 3 册之前添加的其他书籍将保留在其下方：

  |--------|
  | book 3 | ◀──── top of box
  |--------|
  | book 2 |
  |--------|
  | book 1 | ◀──── bottom of box
  |--------|

盒子就像一个堆栈，书籍是数据元素。向框中添加书籍是推送操作，而从框顶部移除/获取书籍是弹出操作。如果我们执行 pop 操作，我们将获得第 3 册，该框将返回到我们推送第 3 册之前的方式。这意味着我们放入的最后一个（或最近的）元素是我们的第一个元素下了（LIFO）。为了获得第 1 册，我们必须再执行两次流行音乐：一种用于删除第二本书，第二本用于获取第一本书。

使用数组实现堆栈。为此，我们需要一个指向顶部位置（tos）的索引。每次将元素推入堆栈时，tos 递增 1，并且每当执行弹出操作时，指向堆栈顶部的索引（tos）递减 1。

推：

在 PUSH 操作之前

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

void push(dataElment item){
    stack[top]=item; //item = i4
    top++;
    
}

在 PUSH 操作之后堆栈有一个指向堆栈顶部的指针。无论何时调用推送操作，它都会将值放在顶部并将值更新。

        tos -- Top of the stack
                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |     |
        |-----|-----|-----|-----|

POP： pop 操作从堆栈顶部删除内容，并通过递减 1 来更新 tos 的值

在弹出操作之前：

                                  tos
                                   |
                                   |
        |-----|-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |     |
        |-----|-----|-----|-----|-----|

dataElment `pop()`{
    dataElment value = stack[tos--];
    return value;
}

弹出操作后：

                            tos
                             |
                             |
        |-----|-----|-----|-----|
        | i1  | i2  | i3  |  i4 |
        |-----|-----|-----|-----|
        When a push operation is performed it overwrites i4.