# Python 及 C++ 堆疊 (stack)
> 作者：王一哲
> 日期：2023年8月4日
## 前言
堆疊 (stack) 是一種 **後進先出** (the last in is the first out, LIFO) 的資料格式，只能從最後面（最上面）填入資料，從最後面（最上面）取出資料，無法從堆疊中間存取資料，以下是在 Python 及 C++ 的實作方法。
<br />
## Python 方法1：引入 queue 函式庫中的 LifoQueue
要先引入函式庫，函式庫的官方說明書在此 [queue — A synchronized queue class](https://docs.python.org/3/library/queue.html)，操作方式與 queue 基本上相同，可以參考另一篇文章〈[Python 及 C++ 佇列 (queue)](https://hackmd.io/@yizhewang/ryA70lSi3#Python-%E6%96%B9%E6%B3%951%EF%BC%9A%E5%BC%95%E5%85%A5-queue-%E5%87%BD%E5%BC%8F%E5%BA%AB%E4%B8%AD%E7%9A%84-Queue)〉。
```python
from queue import LifoQueue
```
<br />
### 建立堆疊
語法為
```python
堆疊名稱 = LifoQueue(maxsize=長度)
```
maxsize 可以不加，預設值為 0；如果有設定 maxsize，當堆疊已滿且要填入新資料時，會回傳錯誤訊息 **Full**。以下的程式碼會建立名稱為 mystack、maxsize 為3的堆疊。
```python
mystack = LifoQueue(maxsize=3)
```
<br />
### 填入資料
語法為
```python
堆疊名稱.put(資料, block=布林, timeout=秒數)
```
block 可以不加，預設值為 True。timeout 可以不加，預設值為 None。
1. 如果 block=True，當堆疊已滿且要填入新資料時，會先等待一段時間，當堆疊有空間時再填入資料，或是到達 timeout 設定的秒數時回傳錯誤訊息 **Full**，但如果沒有設定 timeout，程式就會停在這一行，不會執行後面的程式碼。
2. 如果 block=False，當堆疊已滿且要填入新資料時，立刻回傳錯誤訊息 **Full**。
延續前面的程式碼，可以試試看第5、6行程式碼執行時的差異。
```python=
mystack = LifoQueue(maxsize=3)
mystack.put(0) # mystack 的內容為 [0]
mystack.put(1) # mystack 的內容為 [0, 1]
mystack.put(2) # mystack 的內容為 [0, 1, 2] 且已填滿
mystack.put(3, block=True, timeout=1) # 等待 1 秒後回傳錯誤訊息 Full
#mystack.put(3, block=False) # 立刻回傳錯誤訊息 Full
```
<br />
### 檢查堆疊是否為空
語法為
```python
堆疊名稱.empty()
```
不需要加上任何參數，如果堆疊是空的回傳 True，如果堆疊中有資料回傳 Fasle。
<br />
### 檢查堆疊是否填滿
語法為
```python
堆疊名稱.full()
```
不需要加上任何參數，如果堆疊已填滿回傳 True，如果堆疊還有空間回傳 Fasle。
<br />
### 取得堆疊長度
語法為
```python
堆疊名稱.qsize()
```
不需要加上任何參數，回傳堆疊長度，格式為 int。
<br />
### 取得堆疊最後面（最上面）的資料
回傳並移除堆疊最後面（最上面）的資料，語法為
```python
堆疊名稱.get(block=布林, timeout=秒數)
```
block 可以不加，預設值為 True。timeout 可以不加，預設值為 None。
1. 如果 block=True，當堆疊中已無資料且要取出資料時，會先等待一段時間，當堆疊中有資料時再取出資料，或是到達 timeout 設定的秒數時回傳錯誤訊息 **Empty**，但如果沒有設定 timeout，程式就會停在這一行，不會執行後面的程式碼。
2. 如果 block=False，當堆疊中已無資料且要取出資料時，立刻回傳錯誤訊息 **Empty**。
例如以下的程式碼，可以試試看第2、3行程式碼執行時的差異。
```python=
mystack = LifoQueue()
mystack.get(block=True, timeout=1) # 等待 1 秒後回傳錯誤訊息 Empty
#mystack.get(block=False) # 立刻回傳錯誤訊息 Empty
```
<br />
### 由堆疊取出所有資料
這是很常用的技巧，假設堆疊 mystack 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```python
while not mystack.empty(): # 當堆疊中還有資料時繼續執行 while 迴圈
n = mystack.get() # 回傳並移除堆疊最後面（最上面）的資料，回傳的資料指定給變數 n
```
<br />
## Python 方法2：使用串列 (list)
關於串列的基本操作請看這篇〈[串列](https://hackmd.io/@yizhewang/H1rSL1W8K)〉，以下是把串列當作堆疊的方法。
<br />
### 建立空的串列
語法為
```python
串列名稱 = []
```
<br />
### 填入資料
語法為
```python
串列名稱.append(資料)
```
<br />
### 檢查串列長度
語法為
```python
len(串列名稱)
```
如串列是空的，長度為 0，
<br />
### 取得串列最後面的資料
回傳並移除串列最後面的資料，語法為
```python
串列名稱.pop()
```
參數為索引值，預設值為 -1，也就是最後一筆資料。其實 pop 可以回傳串列中任何索引值的資料，在此是為了配合堆疊的操作方式，因此省略索引值。
<br />
### 由串列取出所有資料
為了配合堆疊的操作方式，假設串列 mystack 的內容為 [0, 1, 2, 3, 4]，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```python
while mystack: # 當串列中還有資料時繼續執行 while 迴圈
n = mystack.pop() # 回傳並移除串列最後面的資料，回傳的資料指定給變數 n
```
<br />
## C++ STL stack 函式庫
要先引入函式庫，函式庫的官方說明書在此 [cplusplus.com std::stack](https://cplusplus.com/reference/stack/stack/)。
```cpp
#include <stack>
```
<br />
### 建立堆疊
語法為
```cpp
stack<資料格式> 堆疊名稱;
```
可以使用所有內建的資料格式，例如 int、float、string，甚至也可以使用自訂的資料格式。
<br />
### 填入資料
語法為
```cpp
堆疊名稱.push(資料);
```
例如
```cpp=
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack<int> mystack;
mystack.push(0); // mystack 的內容為 [0]
mystack.push(1); // mystack 的內容為 [0, 1]
mystack.push(2); // mystack 的內容為 [0, 1, 2]
return 0;
}
```
<br />
### 呼叫已定義的建構子處理資料後再填入
看起來功能和 push 很像，官方說明書在此[std::stack::emplace](https://cplusplus.com/reference/stack/stack/emplace/)，語法為
```cpp
堆疊名稱.emplace(資料);
```
<br />
### 檢查堆疊是否為空
語法為
```cpp
堆疊名稱.empty();
```
不需要加上任何參數，如果堆疊是空的回傳 1，如果堆疊中有資料回傳 0。
<br />
### 取得堆疊長度
語法為
```cpp
堆疊名稱.size();
```
不需要加上任何參數，回傳堆疊長度，格式為 size_t，沒有正負號的整數。
<br />
### 取得堆疊最上面的資料
回傳堆疊最上面的資料，語法為
```cpp
堆疊名稱.top();
```
<br />
### 移除堆疊最上面的資料
移除堆疊最前面的資料，語法為
```cpp
堆疊名稱.pop();
```
<br />
### 交換兩個堆疊的資料
語法為
```cpp
堆疊1.swap(堆疊2);
```
<br />
### 由堆疊取出所有資料
這是很常用的技巧，假設堆疊 mystack 的內容為 [0, 1, 2, 3, 4]，，程式碼通常是以下的寫法，回傳值 n 依序為 4、3、2、1、0。
```cpp
while(!mystack.empty()) { // 當堆疊中還有資料時繼續執行 while 迴圈
int n = mystack.top(); // 回傳堆疊最前面的資料並指定給變數 n
mystack.pop(); // 移除堆疊最前面的資料
}
```
<br />
## 結語
以上是我目前常用到的堆疊功能，如果之後有遇到其它需求會再補充內容。
## 參考資料
1. [Python 3.11.4 queue — A synchronized queue class](https://docs.python.org/3/library/queue.html)
2. [cplusplus.com std::stack](https://cplusplus.com/reference/stack/stack/)
---
###### tags:`C++`、`Python`
Sign in with Wallet
Connect another wallet