Try   HackMD

Python 及 C++ 堆疊 (stack)

作者:王一哲
日期:2023年8月4日

前言

堆疊 (stack) 是一種 後進先出 (the last in is the first out, LIFO) 的資料格式,只能從最後面(最上面)填入資料,從最後面(最上面)取出資料,無法從堆疊中間存取資料,以下是在 Python 及 C++ 的實作方法。


Python 方法1:引入 queue 函式庫中的 LifoQueue

要先引入函式庫,函式庫的官方說明書在此 queue — A synchronized queue class,操作方式與 queue 基本上相同,可以參考另一篇文章〈Python 及 C++ 佇列 (queue)〉。

from queue import LifoQueue

建立堆疊

語法為

堆疊名稱 = LifoQueue(maxsize=長度)

maxsize 可以不加,預設值為 0;如果有設定 maxsize,當堆疊已滿且要填入新資料時,會回傳錯誤訊息 Full。以下的程式碼會建立名稱為 mystack、maxsize 為3的堆疊。

mystack = LifoQueue(maxsize=3)

填入資料

語法為

堆疊名稱.put(資料, block=布林, timeout=秒數)

block 可以不加,預設值為 True。timeout 可以不加,預設值為 None。

  1. 如果 block=True,當堆疊已滿且要填入新資料時,會先等待一段時間,當堆疊有空間時再填入資料,或是到達 timeout 設定的秒數時回傳錯誤訊息 Full,但如果沒有設定 timeout,程式就會停在這一行,不會執行後面的程式碼。
  2. 如果 block=False,當堆疊已滿且要填入新資料時,立刻回傳錯誤訊息 Full

延續前面的程式碼,可以試試看第5、6行程式碼執行時的差異。

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

檢查堆疊是否為空

語法為

堆疊名稱.empty()

不需要加上任何參數,如果堆疊是空的回傳 True,如果堆疊中有資料回傳 Fasle。

檢查堆疊是否填滿

語法為

堆疊名稱.full()

不需要加上任何參數,如果堆疊已填滿回傳 True,如果堆疊還有空間回傳 Fasle。

取得堆疊長度

語法為

堆疊名稱.qsize()

不需要加上任何參數,回傳堆疊長度,格式為 int。

取得堆疊最後面(最上面)的資料

回傳並移除堆疊最後面(最上面)的資料,語法為

堆疊名稱.get(block=布林, timeout=秒數)

block 可以不加,預設值為 True。timeout 可以不加,預設值為 None。

  1. 如果 block=True,當堆疊中已無資料且要取出資料時,會先等待一段時間,當堆疊中有資料時再取出資料,或是到達 timeout 設定的秒數時回傳錯誤訊息 Empty,但如果沒有設定 timeout,程式就會停在這一行,不會執行後面的程式碼。
  2. 如果 block=False,當堆疊中已無資料且要取出資料時,立刻回傳錯誤訊息 Empty

例如以下的程式碼,可以試試看第2、3行程式碼執行時的差異。

mystack = LifoQueue() mystack.get(block=True, timeout=1) # 等待 1 秒後回傳錯誤訊息 Empty #mystack.get(block=False) # 立刻回傳錯誤訊息 Empty

由堆疊取出所有資料

這是很常用的技巧,假設堆疊 mystack 的內容為 [0, 1, 2, 3, 4],程式碼通常是以下的寫法,回傳值 n 依序為 4、3、2、1、0。

while not mystack.empty():  # 當堆疊中還有資料時繼續執行 while 迴圈
    n = mystack.get()       # 回傳並移除堆疊最後面(最上面)的資料,回傳的資料指定給變數 n

Python 方法2:使用串列 (list)

關於串列的基本操作請看這篇〈串列〉,以下是把串列當作堆疊的方法。

建立空的串列

語法為

串列名稱 = []

填入資料

語法為

串列名稱.append(資料)

檢查串列長度

語法為

len(串列名稱)

如串列是空的,長度為 0,

取得串列最後面的資料

回傳並移除串列最後面的資料,語法為

串列名稱.pop()

參數為索引值,預設值為 -1,也就是最後一筆資料。其實 pop 可以回傳串列中任何索引值的資料,在此是為了配合堆疊的操作方式,因此省略索引值。

由串列取出所有資料

為了配合堆疊的操作方式,假設串列 mystack 的內容為 [0, 1, 2, 3, 4],程式碼通常是以下的寫法,回傳值 n 依序為 4、3、2、1、0。

while mystack:              # 當串列中還有資料時繼續執行 while 迴圈
    n = mystack.pop()       # 回傳並移除串列最後面的資料,回傳的資料指定給變數 n

C++ STL stack 函式庫

要先引入函式庫,函式庫的官方說明書在此 cplusplus.com std::stack

#include <stack>

建立堆疊

語法為

stack<資料格式> 堆疊名稱;

可以使用所有內建的資料格式,例如 int、float、string,甚至也可以使用自訂的資料格式。

填入資料

語法為

堆疊名稱.push(資料);

例如

#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; }

呼叫已定義的建構子處理資料後再填入

看起來功能和 push 很像,官方說明書在此std::stack::emplace,語法為

堆疊名稱.emplace(資料);

檢查堆疊是否為空

語法為

堆疊名稱.empty();

不需要加上任何參數,如果堆疊是空的回傳 1,如果堆疊中有資料回傳 0。

取得堆疊長度

語法為

堆疊名稱.size();

不需要加上任何參數,回傳堆疊長度,格式為 size_t,沒有正負號的整數。

取得堆疊最上面的資料

回傳堆疊最上面的資料,語法為

堆疊名稱.top();

移除堆疊最上面的資料

移除堆疊最前面的資料,語法為

堆疊名稱.pop();

交換兩個堆疊的資料

語法為

堆疊1.swap(堆疊2);

由堆疊取出所有資料

這是很常用的技巧,假設堆疊 mystack 的內容為 [0, 1, 2, 3, 4],,程式碼通常是以下的寫法,回傳值 n 依序為 4、3、2、1、0。

while(!mystack.empty()) {   // 當堆疊中還有資料時繼續執行 while 迴圈
    int n = mystack.top();  // 回傳堆疊最前面的資料並指定給變數 n
    mystack.pop();          // 移除堆疊最前面的資料 
}

結語

以上是我目前常用到的堆疊功能,如果之後有遇到其它需求會再補充內容。

參考資料

  1. Python 3.11.4 queue — A synchronized queue class
  2. cplusplus.com std::stack

tags:C++Python