专栏首页只为你下使用python实现数组、链表、队列、栈
原创

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

  

  复制代码

  

  回到顶部

  

  使用

  

  复制代码

  

  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

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • linux环境下的时间编程

    Linux下提供了丰富的api以供开发者们处理和时间相关的问题。然而这些接口看似各自为政实则有有着千丝万缕的联系,在学习和时间中引发了各种各样的混乱。因此时间处...

    不会飞的小鸟
  • 使用Rancher在K8S上部署高性能PHP应用程序

    PHP是网络上最流行的编程语言之一,许多被广泛使用的内容管理系统都使用它开发,如WordPress和Drupal,并为现代服务器端框架(如Laravel和Sym...

    不会飞的小鸟
  • 三次握手和四次挥手简单理解

    PS:ACK、SYN和FIN这些大写的单词表示标志位,其值要么是1,要么是0;ack、seq小写的单词表示序号。

    不会飞的小鸟
  • Django 1.10中文文档-第一个应用Part5-测试

    目录[-] 本教程上接教程Part4。 前面已经建立一个网页投票应用,现在将为它创建一些自动化测试。 自动化测试简介 什么是自动化测试 测试是检查你的代码是...

    jhao104
  • 【玩转腾讯云】使用 serverless 在腾讯云部署第一个函数

    serverless 是各大云服务商提供出来的一种无服务的计算资源。为什么叫无服务呢,因为如果你使用 serverless,你只需要关注应用层,而无需关心底层基...

    YINUXY
  • 如何在一对一语音聊天系统的开发上寻找突破点?

    早在1943年的《人类激励理论》一文中,马斯洛就曾通过提出的需求层次理论告诉我们,社交需求是人类基于生理和安全需求之上的一大心理需求。然而这种社交无疑又包含熟人...

    就爱吃小笼包
  • 使用ffpython嵌入和扩展python

    ffpython ffpython is a c++ lib,which is to simplify task that embed python and e...

    知然
  • Leetcode-Easy 543. Diameter of Binary Tree

    543. Diameter of Binary Tree 描述: 求二叉树最长路径长度 ? 思路: 深度优先搜索 代码 # Definit...

    致Great
  • ESP8266刷AT固件与nodemcu固件NodeMCU初探

    这回是使用的这一款 ? ? ? 因为这款默认的是支持AT指令的固件,,所以我们就刷nodemcu的 先看接线 ? GPIO0 默认是工作模式(不接线)。如果接了...

    杨奉武
  • R tips:使用enframe和map2优雅的迭代列表

    在R中更易于处理的数据形式是data.frame,list并不是太好处理,常用操作就是对它进行循环迭代。

    生信菜鸟团

扫码关注云+社区

领取腾讯云代金券