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]

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):
    #初始化節(jié)點
    self.head = Head()
  def enqueue(self, value):
    #插入一個元素
    newnode = Node(value)
    p = self.head
    if p.right:
      #如果head節(jié)點的右邊不為None
      #說明隊列中已經(jīng)有元素了
      #就執(zhí)行下列的操作
      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):
      #說明隊列中已經(jīng)有元素
      #但是這是最后一個元素
      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!')