使用python实现数组、链表、队列、栈的方法
作者：学海无涯苦作舟 发布时间：2021-01-03 22:40:20
标签：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实现数组、链表、队列、栈的方法网站的支持！
如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
来源：https://www.cnblogs.com/pungchur/p/12068073.html
0
投稿猜你喜欢
- 这个收藏本站、设为首页代码相信每个网站都会用到，这么常用的代码，网络上流行的一般是很多年前的代码版本，只有兼容IE，对其它浏览器没有考虑，下
1. 镜像源列表清华：https://pypi.tuna.tsinghua.edu.cn/simple阿里云：http://mirrors.- 索引优化，查询优化，查询缓存，服务器设置优化，操作系统和硬件优化，应用层面优化（web服务器，缓存）等等。这里的记录的优化技巧更适用于开发人
- 版权所有：Copyright 1997 Netscape Communications Corporation原文链接：Object Hie
- append() 方法向列表的尾部添加一个新的元素。只接受一个参数。>>> num = [1,2]>>>
- 今天记录一下pandas筛选出一个表中满足另一个表中所有条件的数据。例如：list1 结构：名字，ID，颜色，数量，类型。list1 = [
- 1、前期准备通过 pip 或 easy_install 安装了 pymongo 之后, 就能通过 Python 调教 mongodb 了.接
- MySQL有的时候需要用到类似lastIndexOf的功能，然而它没有现成直接可用的函数，就需要自己来琢磨了。首先，MySQL提供了以下3个
- 当我们想对python中原有的模块进行覆盖，又不希望退出当前的程序，就需要用到重载的概念。这样既能使模块得到更新，又不影响解释器的使用。在导
- map()是python的一个内建函数， 他能够通过函数来处理序列，比如，我们相关一个数组[0，1，2，3，4，5]所有的数字都+2 , 当
- 本文实例讲述了Python设计模式之状态模式原理与用法。分享给大家供大家参考，具体如下：状态模式(State Pattern):当一个对象的
- Laravel通过传统的登录表单已经让用户认证变得很简单，但是API怎么办？API通常使用token进行认证并且在请求之间不维护sessio
- 介绍 os模块是Python和操作系统进行交互的一个接口，它提供了许多操作文件及文件夹的函数。可以用于文件名、文件路径、文件夹相
- 动态展示这是一个动态图哦导读兄弟们可以收藏一下哦！情人节可以送出去，肥学找了几朵python写的花给封装好送给大家。不是多炫酷但是有足够的用
- 本文实例讲述了Python 继承，重写，super()调用父类方法操作。分享给大家供大家参考，具体如下：demo.py（继承，重写，supe
- 前言数据清洗是一项复杂且繁琐(kubi)的工作，同时也是整个数据分析过程中最为重要的环节。有人说一个分析项目80％的时间都是在清洗数据，这听
- 使用了Python一段时间后，可以说Python的基本单位就是模块了，在使用模块的时候我们一般会使用通过import语句来将其导入，但是我们
- 昨天晚上在家里把WM设计好的好台界面做成Html，在家里只用IE8和FF做了测试，感觉还行，除了感觉IE8还不成熟，渲染比较慢且不稳定外，标
- arguments定义所有的函数都有一个自己的arguments对象，用来储存它实际接受到的参数，而不局限于函数声明时所定义的参数列表。它不
- 跨浏览器的本地存储（一）：userData behaviorDOM Storage，是基于 Web Applications 1.0 spe
