堆疊簡介

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