跳转至

棧

引入

棧是 OI 中常用的一種線性數據結構。請注意，本文主要講的是棧這種數據結構，而非程序運行時的系統棧/棧空間。

棧的修改與訪問是按照後進先出的原則進行的，因此棧通常被稱為是後進先出（last in first out）表，簡稱 LIFO 表。

Warning

LIFO 表達的是 當前在容器 內最後進來的最先出去。

我們考慮這樣一個棧

1
2
3
4
push(1)
pop(1)
push(2)
pop(2)

如果從整體考慮，1 最先入棧，最先出棧，2 最後入棧，最後出棧，這樣就成了一個先進先出表，顯然是錯誤的。

所以，在考慮數據結構是 LIFO 還是 FIFO 的時候，應當考慮在當前容器內的情況。

使用數組模擬棧

我們可以方便的使用數組來模擬一個棧，如下：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int st[N];
// 這裏使用 st[0] (即 *st) 代表棧中元素數量，同時也是棧頂下標

// 壓棧 ：
st[++*st] = var1;
// 取棧頂 ：
int u = st[*st];
// 彈棧 ：注意越界問題, *st == 0 時不能繼續彈出
if (*st) --*st;
// 清空棧
*st = 0;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
st = [0] * N
# 這裏使用 st[0] 代表棧中元素數量，同時也是棧頂下標

# 壓棧 ：
st[st[0] + 1] = var1
st[0] = st[0] + 1
# 取棧頂：
u = st[st[0]]
# 彈棧：注意越界問題, *st == 0 時不能繼續彈出
if st[0]:
    st[0] = st[0] - 1
# 清空棧
st[0] = 0

C++ STL 中的棧

C++ 中的 STL 也提供了一個容器 std::stack，使用前需要引入 stack 頭文件。

STL 中對 stack 的定義 
1
2
3
4
5
// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class stack;

T 為 stack 中要存儲的數據類型。

Container 為用於存儲元素的底層容器類型。這個容器必須提供通常語義的下列函數：

  • back()
  • push_back()
  • pop_back()

STL 容器 std::vector、std::deque 和 std::list 滿足這些要求。如果不指定，則默認使用 std::deque 作為底層容器。

STL 中的 stack 容器提供了一眾成員函數以供調用，其中較為常用的有：

  • 元素訪問
    • st.top() 返回棧頂
  • 修改
    • st.push() 插入傳入的參數到棧頂
    • st.pop() 彈出棧頂
  • 容量
    • st.empty() 返回是否為空
    • st.size() 返回元素數量

此外，std::stack 還提供了一些運算符。較為常用的是使用賦值運算符 = 為 stack 賦值，示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 新建兩個棧 st1 和 st2
std::stack<int> st1, st2;

// 為 st1 裝入 1
st1.push(1);

// 將 st1 賦值給 st2
st2 = st1;

// 輸出 st2 的棧頂元素
cout << st2.top() << endl;
// 輸出: 1

使用 Python 中的 list 模擬棧

在 Python 中，你可以使用列表來模擬一個棧：

實現 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
st = [5, 1, 4]

# 使用 append() 向棧頂添加元素
st.append(2)
st.append(3)
# >>> st
# [5, 1, 4, 2, 3]

# 使用 pop 取出棧頂元素
st.pop()
# >>> st
# [5, 1, 4, 2]

# 使用 clear 清空棧
st.clear()

參考資料

  1. std::stack - zh.cppreference.com
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用