链式队列LinkedQueue

发表于 | 分类于 | 阅读次数 ℃
本文字数： 628 | 阅读时长 ≈ 1 分钟

先进者先出，后进者后出，这就是典型的“队列”。队列跟栈一样，也是一种操作受限的线性表数据结构。队列最基本的操作就是入队（添加一个数据到队列尾部）和出队（从队列取一个元素）。用数组实现的队列叫顺序队列，用链表实现的队列叫链式队列。

链式队列的结点结构

1
2
3
4
5
class Node(object):

	def __init__(self, data=None, _next=None):
		self.data = data
		self._next = _next

链式队列类

队列需要两个指针：一个是_head指针，指向队头；一个是tail指针，指向队尾。

1
2
3
4
5
class LinkedQueue(object):

	def __init__(self, _head=None, _tail=None):
		self._head = _head
		self._tail = _tail

入队操作：

1
2
3
4
5
6
7
def enqueue(self, value):
	new_node = Node(value)
	if self._tail:
		self._tail._next = new_node
	else:
		self._head = new_node
	self._tail = new_node

出队操作：

1
2
3
4
5
6
def pop(self):
	top = self._top
	if top:
		value = top.data
		self._top = top._next
		return value