溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關如何使用python實現數組、鏈表、隊列、棧，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
引言
什么是數據結構？
數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成。
簡單來說，數據結構就是設計數據以何種方式組織并存儲在計算機中。
比如：列表，集合和字典等都是數據結構
N.Wirth：“程序=數據結構+算法”
數據結構按照其邏輯結構可分為線性結構、樹結構、圖結構
線性結構：數據結構中的元素存在一對一的互相關系。
樹結構：數據結構中的元素存在一對多的互相關系。
圖結構：數據結構中的元素存在多對多的互相關系。
數組
在python中是沒有數組的，有的是列表，它是一種基本的數據結構類型。
實現
class Array(object): def __init__(self, size=32): """ :param size: 長度 """ self._size = size self._items = [None] * size # 在執行array[key]時執行 def __getitem__(self, index): return self._items[index] # 在執行array[key] = value 時執行 def __setitem__(self, index, value): self._items[index] = value # 在執行len(array) 時執行 def __len__(self): return self._size # 清空數組 def clear(self, value=None): for i in range(len(self._items)): self._items[i] = value # 在遍歷時執行 def __iter__(self): for item in self._items: yield item
使用
a = Array(4) a[0] = 1 print(a[0]) # 1 a.clear() print(a[0]) # None a[0] = 1 a[1] = 2 a[3] = 4 for i in a: print(i) # 1, 2, None, 4
鏈表
鏈表中每一個元素都是一個對象，每一個對象被稱為節點，包含有數據域value和指向下一個節點的指針next。
通過各個節點直接的相互鏈接，最終串成一個鏈表。
實現
class Node(object):
def __init__(self, value=None, next=None):
self.value, self.next = value, next
class LinkedList(object):
def __init__(self, size=None):
"""
:param size: int or None, 如果None，則該鏈表可以無限擴充
"""
self.size = size
# 定義一個根節點
self.root = Node()
# 尾節點始終指向最后一個節點
self.tail_node = None
self.length = 0
def __len__(self):
return self.length
def append(self, value):
# size 不為 None, 且長度大于等于size則鏈表已滿
if self.size and len(self) >= self.size:
raise Exception("LinkedList is full")
# 構建節點
node = Node(value)
tail_node = self.tail_node
# 判斷尾節點是否為空
if tail_node is None:
# 還沒有 append 過，length = 0， 追加到 root 后
self.root.next = node
else:
# 否則追加到最后一個節點的后邊，并更新最后一個節點是 append 的節點
tail_node.next = node
# 把尾節點指向node
self.tail_node = node
# 長度加一
self.length += 1
# 往左邊添加
def append_left(self, value):
if self.size and len(self) >= self.size:
raise Exception("LinkedList is full")
# 構建節點
node = Node(value)
# 鏈表為空，則直接添加設置
if self.tail_node is None:
self.tail_node = node
# 設置頭節點為根節點的下一個節點
head_node = self.root.next
# 把根節點的下一個節點指向node
self.root.next = node
# 把node的下一個節點指向原頭節點
node.next = head_node
# 長度加一
self.length += 1
# 遍歷節點
def iter_node(self):
# 第一個節點
current_node = self.root.next
# 不是尾節點就一直遍歷
while current_node is not self.tail_node:
yield current_node
# 移動到下一個節點
current_node = current_node.next
# 尾節點
if current_node is not None:
yield current_node
# 實現遍歷方法
def __iter__(self):
for node in self.iter_node():
yield node.value
# 刪除指定元素
def remove(self, value):
# 刪除一個值為value的節點，只要使該節點的前一個節點的next指向該節點的下一個
# 定義上一個節點
perv_node = self.root
# 遍歷鏈表
for current_node in self.iter_node():
if current_node.value == value:
# 把上一個節點的next指向當前節點的下一個節點
perv_node.next = current_node.next
# 判斷當前節點是否是尾節點
if current_node is self.tail_node:
# 更新尾節點 tail_node
# 如果第一個節點就找到了，把尾節點設為空
if perv_node is self.root:
self.tail_node = None
else:
self.tail_node = perv_node
# 刪除節點，長度減一，刪除成功返回1
del current_node
self.length -= 1
return 1
else:
perv_node = current_node
# 沒找到返回-1
return -1
# 查找元素，找到返回下標，沒找到返回-1
def find(self, value):
index = 0
# 遍歷鏈表，找到返回index,沒找到返回-1
for node in self.iter_node():
if node.value == value:
return index
index += 1
return -1
# 刪除第一個節點
def popleft(self):
# 鏈表為空
if self.root.next is None:
raise Exception("pop from empty LinkedList")
# 找到第一個節點
head_node = self.root.next
# 把根節點的下一個節點，指向第一個節點的下一個節點
self.root.next = head_node.next
# 獲取刪除節點的value
value = head_node.value
# 如果第一個節點是尾節點, 則把尾節點設為None
if head_node is self.tail_node:
self.tail_node = None
# 長度減一，刪除節點，返回該節點的值
self.length -= 1
del head_node
return value
# 清空鏈表
def clear(self):
for node in self.iter_node():
del node
self.root.next = None
self.tail_node = None
self.length = 0
# 反轉鏈表
def reverse(self):
# 第一個節點為當前節點，并把尾節點指向當前節點
current_node = self.root.next
self.tail_node = current_node
perv_node = None
while current_node:
# 下一個節點
next_node = current_node.next
# 當前節點的下一個節點指向perv_node
current_node.next = perv_node
# 當前節點的下一個節點為空，則把根節點的next指向當前節點
if next_node is None:
self.root.next = current_node
# 把當前節點賦值給perv_node
perv_node = current_node
# 把下一個節點賦值為當前節點
current_node = next_node使用
ll = LinkedList() ll.append(0) ll.append(1) ll.append(2) ll.append(3) print(len(ll)) # 4 print(ll.find(2)) # 2 print(ll.find(-1)) # -1 ll.clear() print(len(ll)) # 0 print(list(ll)) # []
循環鏈表
雙鏈表中每一個節點有兩個指針，一個指向后面節點、一個指向前面節點。
循環鏈表實現
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node循環鏈表的使用
dll = CircularDoubleLinkedList() dll.append(0) dll.append(1) dll.append(2) assert list(dll) == [0, 1, 2] print(list(dll)) # [0, 1, 2] print([node.value for node in dll.iter_node()]) # [0, 1, 2] print([node.value for node in dll.iter_node_reverse()]) # [2, 1, 0] headnode = dll.head_node() print(headnode.value) # 0 dll.remove(headnode) print(len(dll)) # 2
隊列
隊列(Queue)是一個數據集合，僅允許在列表的一端進行插入，另一端進行刪除。
進行插入的一端成為隊尾(rear)，插入動作稱為進隊或入隊。
進行刪除的一端稱為隊頭(front)，刪除動作稱為出隊。
隊列的性質：先進先出(First-in, First-out)。
基于數組實現環形隊列
class Array(object):
def __init__(self, size=32):
"""
:param size: 長度
"""
self._size = size
self._items = [None] * size
# 在執行array[key]時執行
def __getitem__(self, index):
return self._items[index]
# 在執行array[key] = value 時執行
def __setitem__(self, index, value):
self._items[index] = value
# 在執行len(array) 時執行
def __len__(self):
return self._size
# 清空數組
def clear(self, value=None):
for i in range(len(self._items)):
self._items[i] = value
# 在遍歷時執行
def __iter__(self):
for item in self._items:
yield item
class ArrayQueue(object):
def __init__(self, maxsize):
self.maxsize = maxsize
self.array = Array(maxsize)
self.head = 0
self.tail = 0
def __len__(self):
return self.head - self.tail
# 入隊
def push(self, value):
if len(self) >= self.maxsize:
raise Exception("Queue is full")
self.array[self.head % self.maxsize] = value
self.head += 1
# 出隊
def pop(self):
value = self.array[self.tail % self.maxsize]
self.tail += 1
return value使用
size = 5 q = ArrayQueue(size) for i in range(size): q.push(i) print(len(q)) # 5 print(q.pop()) # 0 print(q.pop()) # 1
基于雙向鏈表實現雙向隊列
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
# 雙向隊列
class Deque(CircularDoubleLinkedList):
# 從右邊出隊
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
# 從左邊出隊
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value雙向隊列
兩端都可以進行插入，刪除。
基于雙向鏈表實現雙向隊列
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
# 雙向隊列
class Deque(CircularDoubleLinkedList):
# 從右邊出隊
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
# 從左邊出隊
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value雙向隊列的使用
dq = Deque() dq.append(1) dq.append(2) print(list(dq)) # [1, 2] dq.appendleft(0) print(list(dq)) # [0, 1, 2] dq.pop() print(list(dq)) # [0, 1] dq.popleft() print(list(dq)) # [1] dq.pop() print(len(dq)) # 0
棧
棧(Stack)是一個數據集合，可以理解為只能在一端插入或刪除操作的鏈表。
棧的特點：后進先出(Last-in, First-out)
棧的概念：
棧頂
棧底
棧的基本操作：
進棧（壓棧）：push
出棧：pop
基于雙向隊列實現
class Node(object):
def __init__(self, value=None, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
class CircularDoubleLinkedList(object):
"""
雙向循環鏈表
"""
def __init__(self, maxsize=None):
self.maxsize = maxsize
node = Node()
node.prev = node
node.next = node
self.root = node
self.length = 0
def __len__(self):
return self.length
def head_node(self):
return self.root.next
def tail_node(self):
return self.root.prev
# 遍歷
def iter_node(self):
if self.root.next is self.root:
return
current_node = self.root.next
while current_node.next is not self.root:
yield current_node
current_node = current_node.next
yield current_node
def __iter__(self):
for node in self.iter_node():
yield node.value
# 反序遍歷
def iter_node_reverse(self):
if self.root.prev is self.root:
return
current_node = self.root.prev
while current_node.prev is not self.root:
yield current_node
current_node = current_node.prev
yield current_node
def append(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
tail_node = self.tail_node() or self.root
tail_node.next = node
node.prev = tail_node
node.next = self.root
self.root.prev = node
self.length += 1
def append_left(self, value):
if self.maxsize is not None and len(self) >= self.maxsize:
raise Exception("LinkedList is full")
node = Node(value)
if self.root.next is self.root:
self.root.next = node
node.prev = self.root
node.next = self.root
self.root.prev = node
else:
node.next = self.root.next
self.root.next.prev = node
self.root.next = node
node.prev = self.root
self.length += 1
def remove(self, node):
if node is self.root:
return
node.next.prev = node.prev
node.prev.next = node.next
self.length -= 1
return node
class Deque(CircularDoubleLinkedList):
def pop(self):
if len(self) <= 0:
raise Exception("stark is empty!")
tail_node = self.tail_node()
value = tail_node.value
self.remove(tail_node)
return value
def popleft(self):
if len(self) <= 0:
raise Exception("stark is empty!")
head_node = self.head_node()
value = head_node.value
self.remove(head_node)
return value
class Stack(object):
def __init__(self):
self.deque = Deque()
# 壓棧
def push(self, value):
self.deque.append(value)
# 出棧
def pop(self):
return self.deque.pop()使用
s = Stack() s.push(0) s.push(1) s.push(2) print(s.pop()) # 2 print(s.pop()) # 1 print(s.pop()) # 0
關于“如何使用python實現數組、鏈表、隊列、棧”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
