歡迎加入我的 Discord 群組與我討論程式相關的問題!

堆疊 (stacks)

stack 顧名思義就是一個堆,就像是把一疊盤子堆起來一樣。跟 queue 相反,stack 會是先進先出的一種資料結構,就像是你要拿一疊盤子,一定是從最上面開始拿

圖片來源: https://www.programiz.com/dsa/stack

跟 queue 很像,你可以每次從 stack 的最上面加入或刪除東西,也可以取到最上面的元素是甚麼。

複雜度:

插入 (push): O(1)
刪除 (pop): O(1)

宣告

// 語法:
#include <stack>
stack <資料型別> 名字;

// Ex:
stack <int> s; // 宣告裡面存 int 的 queue
stack <pair<int,int> > s2; // 宣告裡面存 pair 的 queue

加入東西 (push)

push 函數可以讓你把東西加到 stack 的最上面

// 語法:
名字.push(元素);

// Ex: 
stack <int> s;
s.push(3);
s.push(3+5);

得到最上面的元素 (top)

// 語法:
名字.top();

// Ex:
stack <int> s;
s.push(3);
s.push(4);
cout << s.top() << '\n'; 
// s.top 會是 4,因為 4 在最上面

移除最上面的元素 (pop)

// 語法:
名字.pop();

// Ex:
stack <int> s;
s.push(3);
s.pop(); 
// 移除最前面的元素

得到 stack 的大小 (empty, size)

// 語法:
名字.size(); // 大小
名字.empty(); // 是否是空的

stack <int> s;
s.push(3);
s.push(4);
cout << s.size(); // 2
if(s.empty()) {
    cout << "Empty\n";
} else {
    cout << "Not Empty\n";
} 
// Not empty

stack <int> s2;
s2.push(3);
s2.pop();
cout << s2.size(); // 0
if(s2.empty()) {
    cout << "Empty\n";
} else {
    cout << "Not Empty\n";
} 
// Empty

Blog at WordPress.com.