圆月山庄资源网

使用python实现数组、链表、队列、栈的方法
脚本专栏 2024/11/3 佚名
3 2
圆月山庄资源网 Design By www.vgjia.com

引言

什么是数据结构？

  • 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。
  • 简单来说，数据结构就是设计数据以何种方式组织并存储在计算机中。
  • 比如：列表，集合和字典等都是数据结构
  • 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。

通过各个节点直接的相互链接，最终串成一个链表。

使用python实现数组、链表、队列、栈的方法

实现

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)) # []

循环链表

双链表中每一个节点有两个指针，一个指向后面节点、一个指向前面节点。

使用python实现数组、链表、队列、栈的方法

循环链表实现

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)。

使用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


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

双向队列

两端都可以进行插入，删除。

使用python实现数组、链表、队列、栈的方法

基于双向链表实现双向队列

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

使用python实现数组、链表、队列、栈的方法

基于双向队列实现

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实现数组、链表、队列、栈的方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

标签：
python数组链表队列栈,python链表,栈,python,栈队列链表
圆月山庄资源网 Design By www.vgjia.com
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
圆月山庄资源网 Design By www.vgjia.com
www.vgjia.com 圆月山庄资源网
139,976互联网资源
144,792高清电影
21,817无损音乐
631,128技术资源

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 桃源资源网 杰网资源 富贵资源网 南强小屋 铁雪资源网 幽灵资源网 万梅资源网 狼山资源网 白云岛资源网 昆仑资源网 相思资源网 明霞山资源网 内蒙古资源网 黑松山资源网 茶园资源网 饿虎岗资源网 大旗谷资源网 常春岛资源网 岱庙资源网 兴国资源网 快活林资源网 蝙蝠岛资源网 帝王谷资源网 白云城资源网 伏龙阁资源网 清风细雨楼 天枫庄资源网 圆月山庄资源网 无争山庄资源网 神水资源网 移花宫资源网 神剑山庄资源网 无为清净楼资源网 金钱帮资源网 丐帮资源网 华山资源网 极乐门资源网 小李飞刀资源网 凤求凰客栈 风云阁资源网 金狮镖局 鸳鸯亭资源网 千金楼资源网 更多链接