如何使用python實現(xiàn)數(shù)組、鏈表、隊列、棧

這篇文章將為大家詳細講解有關(guān)如何使用python實現(xiàn)數(shù)組、鏈表、隊列、棧，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

引言

什么是數(shù)據(jù)結(jié)構(gòu)？

• 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。

• 簡單來說，數(shù)據(jù)結(jié)構(gòu)就是設(shè)計數(shù)據(jù)以何種方式組織并存儲在計算機中。

• 比如：列表，集合和字典等都是數(shù)據(jù)結(jié)構(gòu)

• N.Wirth：“程序=數(shù)據(jù)結(jié)構(gòu)+算法”

數(shù)據(jù)結(jié)構(gòu)按照其邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)

• 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的互相關(guān)系。

• 樹結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的互相關(guān)系。

• 圖結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的互相關(guān)系。

數(shù)組

在python中是沒有數(shù)組的，有的是列表，它是一種基本的數(shù)據(jù)結(jié)構(gòu)類型。

實現(xiàn)

class Array(object):
 def __init__(self, size=32):
  """
  :param size: 長度
  """
  self._size = size
  self._items = [None] * size

 # 在執(zhí)行array[key]時執(zhí)行
 def __getitem__(self, index):
  return self._items[index]

 # 在執(zhí)行array[key] = value 時執(zhí)行
 def __setitem__(self, index, value):
  self._items[index] = value

 # 在執(zhí)行l(wèi)en(array) 時執(zhí)行
 def __len__(self):
  return self._size
 
 # 清空數(shù)組
 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value

 # 在遍歷時執(zhí)行
 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

鏈表

鏈表中每一個元素都是一個對象，每一個對象被稱為節(jié)點，包含有數(shù)據(jù)域value和指向下一個節(jié)點的指針next。

通過各個節(jié)點直接的相互鏈接，最終串成一個鏈表。

實現(xiàn)

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
  # 定義一個根節(jié)點
  self.root = Node()
  # 尾節(jié)點始終指向最后一個節(jié)點
  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")
  # 構(gòu)建節(jié)點
  node = Node(value)
  tail_node = self.tail_node
  # 判斷尾節(jié)點是否為空
  if tail_node is None:
   # 還沒有 append 過，length = 0， 追加到 root 后
   self.root.next = node
  else:
   # 否則追加到最后一個節(jié)點的后邊，并更新最后一個節(jié)點是 append 的節(jié)點
   tail_node.next = node
  # 把尾節(jié)點指向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")
  # 構(gòu)建節(jié)點
  node = Node(value)
  # 鏈表為空，則直接添加設(shè)置
  if self.tail_node is None:
   self.tail_node = node
  # 設(shè)置頭節(jié)點為根節(jié)點的下一個節(jié)點
  head_node = self.root.next
  # 把根節(jié)點的下一個節(jié)點指向node
  self.root.next = node
  # 把node的下一個節(jié)點指向原頭節(jié)點
  node.next = head_node
  # 長度加一
  self.length += 1
 # 遍歷節(jié)點
 def iter_node(self):
  # 第一個節(jié)點
  current_node = self.root.next
  # 不是尾節(jié)點就一直遍歷
  while current_node is not self.tail_node:
   yield current_node
   # 移動到下一個節(jié)點
   current_node = current_node.next
  # 尾節(jié)點
  if current_node is not None:
   yield current_node
 # 實現(xiàn)遍歷方法
 def __iter__(self):
  for node in self.iter_node():
   yield node.value
 # 刪除指定元素
 def remove(self, value):
  # 刪除一個值為value的節(jié)點，只要使該節(jié)點的前一個節(jié)點的next指向該節(jié)點的下一個
  # 定義上一個節(jié)點
  perv_node = self.root
  # 遍歷鏈表
  for current_node in self.iter_node():
   if current_node.value == value:
    # 把上一個節(jié)點的next指向當前節(jié)點的下一個節(jié)點
    perv_node.next = current_node.next
    # 判斷當前節(jié)點是否是尾節(jié)點
    if current_node is self.tail_node:
     # 更新尾節(jié)點 tail_node
     # 如果第一個節(jié)點就找到了，把尾節(jié)點設(shè)為空
     if perv_node is self.root:
      self.tail_node = None
     else:
      self.tail_node = perv_node
    # 刪除節(jié)點，長度減一，刪除成功返回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
 # 刪除第一個節(jié)點
 def popleft(self):
  # 鏈表為空
  if self.root.next is None:
   raise Exception("pop from empty LinkedList")
  # 找到第一個節(jié)點
  head_node = self.root.next
  # 把根節(jié)點的下一個節(jié)點，指向第一個節(jié)點的下一個節(jié)點
  self.root.next = head_node.next
  # 獲取刪除節(jié)點的value
  value = head_node.value
  # 如果第一個節(jié)點是尾節(jié)點, 則把尾節(jié)點設(shè)為None
  if head_node is self.tail_node:
   self.tail_node = None
  # 長度減一，刪除節(jié)點，返回該節(jié)點的值
  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
 # 反轉(zhuǎn)鏈表
 def reverse(self):
  # 第一個節(jié)點為當前節(jié)點，并把尾節(jié)點指向當前節(jié)點
  current_node = self.root.next
  self.tail_node = current_node
  perv_node = None
  while current_node:
   # 下一個節(jié)點
   next_node = current_node.next
   # 當前節(jié)點的下一個節(jié)點指向perv_node
   current_node.next = perv_node
   # 當前節(jié)點的下一個節(jié)點為空，則把根節(jié)點的next指向當前節(jié)點
   if next_node is None:
    self.root.next = current_node
   # 把當前節(jié)點賦值給perv_node
   perv_node = current_node
   # 把下一個節(jié)點賦值為當前節(jié)點
   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)) # []

循環(huán)鏈表

雙鏈表中每一個節(jié)點有兩個指針，一個指向后面節(jié)點、一個指向前面節(jié)點。

循環(huán)鏈表實現(xiàn)

class Node(object):
 def __init__(self, value=None, prev=None, next=None):
  self.value = value
  self.prev = prev
  self.next = next


class CircularDoubleLinkedList(object):
 """
 雙向循環(huán)鏈表
 """

 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

循環(huán)鏈表的使用

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)是一個數(shù)據(jù)集合，僅允許在列表的一端進行插入，另一端進行刪除。

進行插入的一端成為隊尾(rear)，插入動作稱為進隊或入隊。

進行刪除的一端稱為隊頭(front)，刪除動作稱為出隊。

隊列的性質(zhì)：先進先出(First-in, First-out)。

基于數(shù)組實現(xiàn)環(huán)形隊列

class Array(object):
 def __init__(self, size=32):
  """
  :param size: 長度
  """
  self._size = size
  self._items = [None] * size

 # 在執(zhí)行array[key]時執(zhí)行
 def __getitem__(self, index):
  return self._items[index]

 # 在執(zhí)行array[key] = value 時執(zhí)行
 def __setitem__(self, index, value):
  self._items[index] = value

 # 在執(zhí)行l(wèi)en(array) 時執(zhí)行
 def __len__(self):
  return self._size
 
 # 清空數(shù)組
 def clear(self, value=None):
  for i in range(len(self._items)):
   self._items[i] = value

 # 在遍歷時執(zhí)行
 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

基于雙向鏈表實現(xiàn)雙向隊列

class Node(object):
 def __init__(self, value=None, prev=None, next=None):
  self.value = value
  self.prev = prev
  self.next = next


class CircularDoubleLinkedList(object):
 """
 雙向循環(huán)鏈表
 """

 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

雙向隊列

兩端都可以進行插入，刪除。

基于雙向鏈表實現(xiàn)雙向隊列

class Node(object):
 def __init__(self, value=None, prev=None, next=None):
  self.value = value
  self.prev = prev
  self.next = next


class CircularDoubleLinkedList(object):
 """
 雙向循環(huán)鏈表
 """

 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)是一個數(shù)據(jù)集合，可以理解為只能在一端插入或刪除操作的鏈表。

棧的特點：后進先出(Last-in, First-out)

棧的概念：

• 棧頂

• 棧底

棧的基本操作：

• 進棧（壓棧）：push

• 出棧：pop

基于雙向隊列實現(xiàn)

class Node(object):
 def __init__(self, value=None, prev=None, next=None):
  self.value = value
  self.prev = prev
  self.next = next


class CircularDoubleLinkedList(object):
 """
 雙向循環(huán)鏈表
 """
 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

關(guān)于“如何使用python實現(xiàn)數(shù)組、鏈表、隊列、?！边@篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。