Python list列表實現棧和佇列

佇列和棧是兩種資料結構，其內部都是按照固定順序來存放變數的，二者的區別在於對資料的存取順序：

• 佇列是，先存入的資料最先取出，即“先進先出”。
• 棧是，最後存入的資料最先取出，即“後進先出”。

考慮到 list 型別資料本身的存放就是有順序的，而且內部元素又可以是各不相同的型別，非常適合用於佇列和棧的實現。本節將演示如何使用 list 型別變數來實現佇列和棧。

Python list實現佇列

使用 list 列表模擬佇列功能的實現方法是，定義一個 list 變數，存入資料時使用 insert() 方法，設定其第一個引數為 0，即表示每次都從最前面插入資料；讀取資料時，使用 pop() 方法，即將佇列的最後一個元素彈出。

如此 list 列表中資料的存取順序就符合“先進先出”的特點。實現程式碼如下：

#定義一個空列表，當做佇列
queue = []
#向列表中插入元素
queue.insert(0,1)
queue.insert(0,2)
queue.insert(0,"hello")
print(queue)
print("取一個元素：",queue.pop())
print("取一個元素：",queue.pop())
print("取一個元素：",queue.pop())

執行結果為：

['hello', 2, 1]
取一個元素： 1
取一個元素： 2
取一個元素： hello

Python list實現棧

使用 list 列表模擬棧功能的實現方法是，使用 append() 方法存入資料；使用 pop() 方法讀取資料。

append() 方法向 list 中存入資料時，每次都在最後面新增資料，這和前面程式中的 insert() 方法正好相反。

舉個例子：

#定義一個空 list 當做棧
stack = []
stack.append(1)
stack.append(2)
stack.append("hello")
print(stack)
print("取一個元素：",stack.pop())
print("取一個元素：",stack.pop())
print("取一個元素：",stack.pop())

輸出結果為：

[1, 2, 'hello']
取一個元素： hello
取一個元素： 2
取一個元素： 1

collections模組實現棧和佇列

前面使用 list 實現佇列的例子中，插入資料的部分是通過 insert() 方法實現的，這種方法效率並不高，因為每次從列表的開頭插入一個資料，列表中所有元素都得向後移動一個位置。

這裡介紹一個相對更高效的方法，即使用標準庫的 collections 模組中的 deque 結構體，它被設計成在兩端存入和讀取都很快的特殊 list，可以用來實現棧和佇列的功能。

舉個例子：

queueAndStack = deque()
queueAndStack.append(1)
queueAndStack.append(2)
queueAndStack.append("hello")
print(list(queueAndStack))

#實現佇列功能，從佇列中取一個元素，根據先進先出原則，這裡應輸出 1
print(queueAndStack.popleft())
#實現棧功能，從棧裡取一個元素，根據後進先出原則，這裡應輸出 hello
print(queueAndStack.pop())
#再次列印列表
print(list(queueAndStack))

輸出結果為：

[1, 2, 'hello']
1
hello
[2]