2021-06-28

C++ std::stack 用法與範例

本篇 ShengYu 將介紹 C++ std::stack 用法與範例，stack 是個很基本也很重要的資料結構，stack 是後進先出原則(LIFO，Last In First Out)，在很多考題上都容易出現，stack 常用基本的操作方法有 push()、pop()、top()，是必學的基本功能。

因為 stack 的後進先出原則，你只能看到最上面 top 的元素是什麼，之前推 push 進去的元素無法去遍歷查看的。

以下 C++ stack 用法與範例將分為這幾部分，

將元素放入 stack 頂端
從 stack 頂端移出元素
取得 stack 裡的元素數量
判斷 stack 是否為空
stack 查看最頂端的元素

要使用 stack 容器的話，需要引入的標頭檔：<stack>

將元素放入 stack 頂端

stack 頂端要推入新元素的話，可以使用 push()，

std-stack.cpp

std::stack<int> mystack;
mystack.push(1);
mystack.push(2);
mystack.push(3);
std::cout << mystack.size() << "\n"; // 3

也可以從在 stack 建構時帶入元素，例如從 vector 複製元素，

1
2
3

std::vector<int> myvector = {4, 5};
std::stack<int, std::vector<int>> mystack2(myvector);
std::cout << mystack2.size() << "\n"; // 2

也可以從在 stack 建構時從 deque 複製元素，

1
2
3

std::deque<int> mydeque = {6, 7, 8};
std::stack<int, std::deque<int>> mystack3(mydeque);
std::cout << mystack3.size() << "\n"; // 3

從 stack 頂端移出元素

stack 頂端要移出元素的話，要使用 pop()，

std-stack2.cpp

std::stack<int> mystack;
mystack.push(1);
mystack.push(2);
std::cout << mystack.size() << "\n"; // 2
mystack.pop();
mystack.pop();
mystack.pop(); // Segmentation fault

值得注意的是，上例中 stack 為空時再 pop 會讓程式崩潰，
為了避免程式崩潰，所以通常在 pop 時會對 stack 進行檢查是否為空，非空才 pop()，例如下面這樣，

std::stack<int> mystack;
mystack.push(1);
mystack.push(2);
std::cout << mystack.size() << "\n"; // 2
if (!mystack.empty()) {
    mystack.pop();
}
if (!mystack.empty()) {
    mystack.pop();
}
std::cout << mystack.size() << "\n"; // 0
if (!mystack.empty()) {
    mystack.pop();
}

取得 stack 裡的元素數量

stack 要取得 stack 裡元素數量要使用 size()，

std-stack3.cpp

std::stack<char> mystack;
std::cout << mystack.size() << "\n";
mystack.push('a');
std::cout << mystack.size() << "\n";
mystack.push('b');
std::cout << mystack.size() << "\n";

輸出為

1
2
3

0
1
2

從 vector 複製元素初始化 stack，並且印出數量

// stack initialized from vector
std::vector<int> myvector = {1, 2};
std::stack<int, std::vector<int>> mystack2(myvector);
std::cout << mystack2.size() << "\n"; // 2

判斷 stack 是否為空

stack 要判斷是否為空的話，可以使用 empty()，

std-stack4.cpp

std::stack<int> mystack;
if (mystack.empty())
    std::cout << "empty\n";
else
    std::cout << "not empty\n";

mystack.push(1);

if (mystack.empty())
    std::cout << "empty\n";
else
    std::cout << "not empty\n";

輸出為

1 2	empty not empty

stack 查看最頂端的元素

stack 要查看最頂端的元素，可以使用 top()，要注意的是如果 stack 為空時呼叫 top() 會 Segmentation fault，正確作法為先判斷 stack 是否為空，stack 不為空才呼叫 top()。

std-stack5.cpp

std::stack<int> mystack;
// std::cout << mystack.top() << "\n"; // Segmentation fault
if (!mystack.empty())
    std::cout << mystack.top() << "\n";
mystack.push(1);
mystack.push(2);
mystack.push(3);
if (!mystack.empty())
    std::cout << mystack.top() << "\n"; // 3

以上就是 C++ std::stack 用法與範例的介紹，
如果你覺得我的文章寫得不錯、對你有幫助的話記得 Facebook 按讚支持一下！

其他參考
stack - C++ Reference
https://www.cplusplus.com/reference/stack/stack/

leetcode 一些使用到 stack 的題目
Valid Parentheses
https://leetcode.com/problems/valid-parentheses/
Min Stack
https://leetcode.com/problems/min-stack/