Python实现栈和行列的简单操纵要领_F11 - 专业站长和开发者的学习网站

先简单的了解一下数据布局里面的栈和堆：

栈和行列是两种根基的数据布局，同为容器类型。两者底子的区别在于：

stack:后进先出

queue:先进先出

stack和queue是不能通过查询具体某一个位置的元素而进行操纵的。但是他们的排列是按顺序的

对付stack我们可以使用python内置的list实现，因为list是属于线性数组，，在末尾插入和删除一个元素所使用的时间都是O(1),这很是切合stack的要求。虽然，我们也可以使用链表来实现。

stack的实现代码（使用python内置的list），实现起来长短常的简单，就是list的一些常用操纵

class Stack(object):
  def __init__(self):
    self.stack = []
  def push(self, value):  # 进栈
    self.stack.append(value)
  def pop(self): #出栈
    if self.stack:
      self.stack.pop()
    else:
      raise LookupError('stack is empty!')
  def is_empty(self): # 如果栈为空
    return bool(self.stack)
  def top(self): 
    #取出目前stack中最新的元素
    return self.stack[-1]

我们界说如下的链表来实现行列数据布局：

界说一个头结点，左边指向行列的开头，右边指向行列的末尾，这样就可以担保我们插入一个元素和取出一个元素都是O(1)的操纵，使用这种链表实现stack也长短常的方便。实现代码如下：

class Head(object):
  def __init__(self):
    self.left = None
    self.right = None
class Node(object):
  def __init__(self, value):
    self.value = value
    self.next = None
class Queue(object):
  def __init__(self):
    #初始化节点
    self.head = Head()
  def enqueue(self, value):
    #插入一个元素
    newnode = Node(value)
    p = self.head
    if p.right:
      #如果head节点的右边不为None
      #说明行列中已经有元素了
      #就执行下列的操纵
      temp = p.right
      p.right = newnode
      temp.next = newnode
    else:
      #这说明行列为空，插入第一个元素
      p.right = newnode
      p.left = newnode
  def dequeue(self):
    #取出一个元素
    p = self.head
    if p.left and (p.left == p.right):
      #说明行列中已经有元素
      #但是这是最后一个元素
      temp = p.left
      p.left = p.right = None
      return temp.value
    elif p.left and (p.left != p.right):
      #说明行列中有元素，并且不止一个
      temp = p.left
      p.left = temp.next
      return temp.value
    else:
      #说明行列为空
      #抛出查询错误
      raise LookupError('queue is empty!')
  def is_empty(self):
    if self.head.left:
      return False
    else:
      return True
  def top(self):
    #查询目前行列中最早入队的元素
    if self.head.left:
      return self.head.left.value
    else:
      raise LookupError('queue is empty!')