用最简单的办法实现栈和队列。

说起栈和队列，就要提到另外两个名词，先进先出（FIFO)和先进后出（FILO)，描述了栈和队列最原始的动作，存储和删除，只是顺序不一样。我们若是把存储数据的空间想象成一层层的空盒子，这些盒子称为“栈”，那么对于需要存储的每个数据，有如下特性：

1.每个数据占据整个盒子

2.移动每个数据只能取出再放入

于是我们定义每个数据叫做Node，代码如下：

class Node():
    def __init__(self, element=None):
        self.e = element
        self.next = None

然后用Node构造出一个“栈”：

node = Node()
n1 = Node(111)
n2 = Node(222)
n3 = Node(333)
n1.next = n2
n2.next = n3

接着定义存放的两种方式：
1.往Node的末尾添加数据(append):

def append(node, element):
  n = node
  if n.next is not None: 
  # 直到n是最后一个元素
        n = n.next()
  new_node = Node(element)
  n.next = new_node

2.往Node的前面添加数据（prepend):

def prepend(head, element):
    n = Node(element)
    # 设置新数据的next为head的next
    # 然后把head的next指向新数据
    n.next = head.next
    head.next = n

3.删除元素的函数:

def pop(head):
  # 删除“栈”底的元素
  tail = head
  # 找到里最后一个数据
  if tail.next is not None:
      tail = tail.next
  n = head
  # 找到最后一个数据前面的数据
  # 把这个数据的next设为空
  if n.next is not tail:
      n = n.next
  n.next = None
  # 返回删除的元素
  return tail.e

4.定义一个函数来打印出来这个“栈”并测试

def log_list(node):
  n = node()
  s = ''
  while n is not None:
    n = n.next
    s += str(n.e) + '>'
 print(s)


prepend(head, 000)
append(n3, 444)
log_list(head)
pop(head)
log_list(head)

输出：

image.png

注意到pop函数每次都删除最后一个元素，对于栈来说，先进后出，入栈和出栈就可以表示为prepend + pop。对于队列来说，先进先出，入队和出队则是append + pop。

更好的方式？包装成类？

栈的实现

class Stack(object):
  def __init__(self):
    self.head = Node()
  def push(self, element):
  # 相当于prepend
    return self.head.next = Node(element, self.head.next)
  def pop(self):
   # 删除的是最新加入的数据
    node = self.head.next
    if self.head.next is not None:
      self.head.next = node.next
    return node   

队列的实现

class Queue(object):
  def __init__(self,head,tail):
    self.head = head
    self.tail = tail
  def enqueue(self, element):
    node = Node(element)
    self.tail.next = node
    self.tail = node

可以看出栈总是在一个方向操作，从哪里写入数据就从哪里删除数据。
对于队列，写入数据的和删除数据的方向是相反的，所以队列的数据结构就有头节点和尾节点，而栈只需要头节点或者尾节点（取决写入数据的方向）。