006栈.md

实现栈数据结构

什么是栈

栈也是非常常见的数据结构，类比现实中的木桶，特点是先进后出，也就是每次插入都在最上面，每次取都取最上面的。

因此栈的操作比较特别，只需要实现push和pop的接口即可。

如何实现栈

实际上，Python已经提供了数组，已经提供append和pop接口，能够满足栈的使用场景，用法也简单介绍下。

a = [1, 2, 3]

a.append(4)

print(a)
# Print [1, 2, 3, 4]

a.pop()

print(a)
# Print [1, 2, 3]

但我们希望自己实现栈这个数据结构，首先是定义Node类和Stack类。

class Node(object):

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

class Stack(object):

  def __init__(self, top=None):
    self.top = top

  def is_empty(self):
    pass

  def push(self, data):
    pass

  def pop(self):
    pass

stack = Stack()

然后我们需要去实现push、pop和is_empty这几个函数。其中push和pop需要注意如果top为空的情况。

class Stack(object):

  def __init__(self, top=None):
    self.top = top

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

  def push(self, data):
    if self.top == None:
      self.top = Node(data)
    else:
      new_node = Node(data)
      new_node.next = self.top
      self.top = new_node

  def pop(self):
    if self.top == None:
      print("No node in stack")
      return
    else:
      top = self.top
      self.top = self.top.next
      return top

stack = Stack()
stack.push("node1")
stack.push("node2")
stack.push("node3")
print(stack.pop().data)
# Print "node3"

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