本文将使用python實作資料結構中的棧、隊列；有關棧、隊列的理論原理請參考：《資料結構與算法》-3-棧和隊列；
1. 棧的Python實作
1.1 以清單的形式簡單實作棧
"""
以清單的形式簡單實作棧
棧：先進後出
"""
class Stack:
def __init__(self):
self.stack = [] # 初始化
def is_empty(self):
return not bool(self.stack) # 判空
def push(self, value):
self.stack.append(value) # 入棧
return True
def pop(self):
if self.stack:
return self.stack.pop() # 出棧
else:
raise LookupError('stack is empty!')
def peek(self):
if self.stack:
return self.stack[-1] # 擷取棧頂元素
else:
raise LookupError('stack is empty')
def length(self):
return len(self.stack) # 擷取棧内元素個數
1.2 以單連結清單形式實作棧
"""
以單連結清單形式實作棧
棧：先進後出
"""
class Node:
def __init__(self, val=None, nxt=None):
self.value = val # 資訊域
self.next = nxt # 指針域
class Stack:
# 初始化一個空棧
def __init__(self):
self._top = None # 棧頂元素
def is_empty(self):
return self._top is None
def push(self, item):
if not self._top:
self._top = Node(item) # 空棧：直接将新結點設定為棧頂元素
return True
node = self._top # 擷取棧頂元素
self._top = Node(item) # 将新結點設定為棧頂元素
self._top.next = node # 将棧頂元素的指針指向原棧頂元素
return True
def pop(self):
if self.is_empty():
raise LookupError('stack is empty!')
node = self._top # 擷取棧頂元素
self._top = self._top.next # 将原棧頂元素的下一個元素設定為棧頂元素
return node.value # 傳回原棧頂元素的資訊域
def peek(self):
if self.is_empty():
raise LookupError('stack is empty!')
node = self._top # 擷取棧頂元素
return node.value # 傳回棧頂元素的資訊域
def length(self):
if self.is_empty():
return 0
node = self._top # 擷取棧頂元素
count = 1 # 計數
while node.next: # 棧頂元素的下一個元素，直到初始None
node = node.next
count += 1
return count
def stack_to_list(self):
if self.is_empty():
return []
node = self._top # 擷取棧頂元素
li = [node.value]
while node.next:
node = node.next
li.append(node.value)
return li[::-1] # 按照進棧的順序，先後在清單中排列
2. 隊列的Python實作
2.1 以清單實作簡單隊列
"""
以清單的形式簡單實作隊列
隊列：先進先出
"""
class Queue:
def __init__(self):
self.li = []
def is_empty(self):
return not bool(self.li)
def enqueue(self, items):
self.li.append(items)
return True
def dequeue(self):
if self.is_empty():
raise LookupError('queue is empty!')
return self.li.pop(0)
def length(self):
return len(self.li)
def show(self):
if self.is_empty():
raise LookupError('queue is empty!')
return self.li
2.2 以單連結清單形式實作隊列
"""
以連結清單的形式實作隊列
"""
class Node:
def __init__(self, val=None, nxt=None):
self.value = val # 資料域
self.next = nxt # 指針域
class Queue:
def __init__(self):
self.first = None # 頭指針，指向隊頭結點
self.last = None # 尾指針，指向隊尾結點
self.size = 0 # 表示隊列内的結點數
def is_empty(self):
return self.first is None # 判空
def enqueue(self, items):
node = Node(items) # 建立新結點
self.size += 1 # 結點個數加1
if self.is_empty():
self.first = self.last = node # 加入第一個結點
return True
self.last.next = node # 隊尾結點的指針域指向新結點
self.last = node # 尾指針指向隊尾結點
return True
def dequeue(self):
if self.is_empty():
raise LookupError('queue is empty!')
node = self.first # 需要傳回的隊頭結點
self.first = node.next # 隊頭指針指向新隊頭結點
self.size -= 1
return node.value
def length(self):
return self.size
def queue_to_list(self):
if self.is_empty(): # 判空
return []
first_ = self.first
node = self.first
li = [node.value]
while node.next:
node = node.next
li.append(node.value)
return li # 按照的進隊列的順序，在清單中排列