007队列.md

实现队列数据结构

什么是队列

队列和栈类似都是很常见的数据结构，和现实中排队对应，都先进先出的模型。

因此队列这个数据结构，提供的接口是enqueue和dequeue。

如何实现

阅读前建议先看看006栈的数据结构介绍，我们首先要定义的Node类和前面定义的是一样的，并且要定义Queue类的基本接口，注意这时应该有left和right两个节点引用（假设是左进右出）。

class Node(object):

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

class Queue(object):

  def __init__(self, left=None, right=None):
    self.left = left
    self.right = right

  def is_empty(self):
    pass

  def enqueue(self, data):
    pass

  def dequeue(self):
    pass

然后实现这些函数，发现如果每个node之前前后的node会更容易实现些，当然也是牺牲空间换时间。

class Node(object):

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

class Queue(object):

  def __init__(self, left=None, right=None):
    self.left = left
    self.right = right

  def is_empty(self):
    if self.left != None:
      return True
    else:
      return False

  def enqueue(self, data):
    if self.left == None and self.right == None:
      new_node = Node(data)
      self.left = new_node
      self.right = new_node
    else:
      new_node = Node(data)
      new_node.next = self.left
      self.left = new_node

  def dequeue(self):
    if self.left == None and self.right == None:
      print("No node in queue")
      return
    else:
      node = self.right
      # TODO: Need to find the right node for self.right
      return node

queue = Queue()
queue.enqueue("node1")
queue.enqueue("node2")
queue.enqueue("node3")
print(queue.dequeue().data)
# Print "node1"

这是本章内容，希望对你有所帮助。进入下一章