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