本文将使用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 # 按照的进队列的顺序，在列表中排列