堆栈简介

堆栈是 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.