概念

昨天，我們以排隊吃拉麵的情境為例，介紹了佇列（Queue）的基本概念。今天，我們將深入探討 stack 的實作方式，以及在 C++ 中如何使用陣列和 C++ STL 的 stack 來實現 stack 操作。

堆疊是一種常見的資料結構，遵循「後進先出」（Last-In First-Out，簡稱 LIFO）的原則。簡單來說，這意味著最後放入 stack 的元素會最先被取出，就像在拉麵店中，碗是一直向上堆放的，只能從最上面取出或放入。而這個概念不僅適用於拉麵碗，還常被用於函數呼叫等情境中。

實作

首先，我們將示範如何手動實作一個 stack，使用了 C++ 的陣列來存儲元素。以下是程式碼範例：

#include <bits/stdc++.h>
using namespace std;
int st[100100],now = 0;
// 將元素放入 stack
void push(int num){
    st[now] = num;
    now++;
}
// 確認 stack 是否為空
bool isempty(){
    return now == 0;
}
// 回傳 stack 大小
int size(){
    return now;
}
// 清空 stack
void clear(){
    now = 0;
}
// 拿出 stack 最上層的元素
int top(){
    if(!isempty()){
        return st[now - 1];
    }
    return -1;
}
// 將 stack 最上層的元素刪除
void pop(){
    if(!isempty()){
        now--;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    push(2); // st[] = {2}
    push(5); // st[] = {2,5}
    push(8); // st[] = {2,5,8}
    push(22); // st[] = {2,5,8,22}
    cout << size() << "\n"; // 4
    cout << top() << "\n"; // 22
    pop(); // st[] = {2,5,8}
    cout << size() << "\n"; // 3
    cout << top() << "\n"; // 8
    clear(); // // st[] = {}
    cout << size() << "\n"; // 0
    cout << top() << "\n"; // -1
    return 0;
}

陣列實作的壞處

值得注意的是，使用陣列實作堆疊有一個明顯的壞處，就是受限於宣告陣列的大小。如果 stack 中的元素數量超過事先宣告的陣列大小，就會產生問題。這限制了 stack 的彈性和應用範圍。

C++ STL 的 stack

好消息是 C++ 已經提供了內建的 STL 類別，可以動態調整 stack 的大小，從而解決了陣列實作的大小限制。因此使用 STL stack，我們可以更方便地進行堆疊操作。

STL 的 stack 操作

以下是C++ STL stack常用的操作：

• empty()
  • 回傳一個布林值，表示 stack 是否為空
• size()
  • 回傳一個無號整數，表示 stack 的長度
• top()
  • 回傳 stack 最頂端的元素
• push()
  • 將元素放入 stack 的頂端
• pop()
  • 移除 stack 頂端的元素
• ...

除了上述操作，STL stack 還有其他一些可用的操作，詳情請參考 cpp reference

#include <iostream>
#include <stack>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    stack<int> st;
    st.push(12); // st = {12}
    st.push(25); // st = {12,25}
    st.push(8); // st = {12,25,8}
    st.push(90); // st = {12,25,8,90}
    cout << st.size() << "\n"; // 4
    cout << st.top() << "\n"; // 90
    st.pop(); // st = {12,25,8}
    cout << st.size() << "\n"; // 3
    cout << st.top() << "\n"; // 8
    cout << st.empty() << "\n"; // 0，代表 false
    return 0;
}

總結

這篇文章中，我們深入瞭解了 stack 的概念，並提供兩種不同的實作方式：手動使用陣列實作和使用C++ STL stack。手動實作的部分讓我們更深入地理解 stack 的內部運作，但限制了 stack 大小。另一方面，C++ STL stack 則提供了動態改變大小的優點，更適合實際應用。

預告

接下來的文章會不定時穿插一些各主題的相關題目，以藉此讓大家知道可以應用於什麼題目，大家可以期待一下