資料結構（Data Structure）

資料結構是一種設計、組織、儲存資料的方式，以實現最佳性能和效率。這些結構包含不同形式，像是陣列、鍊結列表、樹、圖等等。選擇適當的資料結構對於解決特定的問題至關重要，不同的資料結構可以用於不同的應用，並且可以極大地影響程序的運行時間和記憶體使用。

陣列（Array）

可隨機存取的一串連續記憶體位址。

陣列 (Array) 簡介

補充：List Are Arrays in Python

Leetcode

鏈結串列（Linked List）

元素間彼此串聯在一起，形成一條鍊子的資料結構。

也可以是上圖雙向連結的形式。

Leetcode

堆疊（Stack, Last-In-First-Out, LIFO）

單向進出，後進先出的資料結構，如同把東西堆疊起來。

佇列（Queue, First-In-First-Out, FIFO）

單向進出，先進先出的資料結構，如同在排隊一般。

Stack & Queue in Python: Collections.deque()

Deque（發音類似 Deck）為 Double-Ended Queue 的縮寫，顧名思義，Deque 是一個支援雙向存取的 Queue，也就是說，你可以從頭跟尾插入或移除元素。

官方說明文件

from collections import deque
D = deque([1,2,3])
D.append(4)
D.appendleft(0)
print(D[2], D)
print(D.pop(), D)
print(D.popleft(), D)

Output:
2 deque([0,1,2,3,4])
4 deque([0,1,2,3])
0 deque([1,2,3])

Q：那他與 Stack 跟 Queue 有甚麼關係呢？

A：
Stack: 只使用 D.append() 與 D.pop() 的 deque
Queue: 只使用 D.append() 與 D.popleft() 的 deque

其實只要符合 Stack 跟 Queue 的性質都可以。
因此以下使用方式也對，但較不建議使用：
Stack: 只使用 D.appendleft() 與 D.popleft() 的 deque
Queue: 只使用 D.appendleft() 與 D.pop() 的 deque

以下為使用 collections.deque 來實作 stack 與 queue 的例子：

from collections import deque

# For Stack, you can only use the following operations
S = deque()
# push from a stack:
S.append(val)
# pop from a stack:
val = S.pop()
# peek from a stack:
top = S[-1]
# check size of a stack:
size = len(S)
# check stack is empty:
isEmpty = (size == 0)

# =========================================
# For Queue, you can only use the following operations
Q = deque()
# push from a queue: 
Q.append(val)
# pop from a queue:
val = Q.popleft()
# peek from a queue:
top = Q[0]
# check size of a queue:
size = len(Q)
# check queue is empty:
isEmpty = (size == 0)

另外也可以參考 Python 官方對將 List 作為 Stack / Queue 使用的說明。

介紹完 collections.deque() 以後，讓我們來實際練習一下 Leetcode 的題目吧！