Python栈如何实现 Python栈基于列表和单链表实现方法

本篇文章小编给大家分享一下Python栈基于列表和单链表实现方法，小编觉得挺不错的，现在分享给大家供大家参考，有需要的小伙伴们可以来看看。

Python实现栈

栈的数组实现：利用python列表方法

代码如下：

# 列表实现栈，利用python列表方法
class listStack(object):

  def __init__(self):
    self.items = []

  def is_empty(self):
    return self.items == 0

  def size(self):
    return len(self.items)

  def top(self):
    return self.items[len(self.items)-1]

  def push(self, value):
    return self.items.append(value)

  def pop(self):
    return self.items.pop()
if __name__ =="__main__":
  stack = listStack()
  stack.push("welcome")
  stack.push("www")
  stack.push("jb51")
  stack.push("net")
  print "栈的长度:", stack.size()
  print "n".join(['%s:%s' % item for item in stack.__dict__.items()]) #打印栈stack所有元素
  print "出栈：",stack.pop()
  print "出栈：",stack.pop()
  print "出栈：",stack.pop()

运行结果：

栈的长度: 4

items:['welcome', 'www', 'jb51', 'net']

出栈： net

出栈： jb51

出栈： www

栈的链表实现：

栈的链表实现中，压栈(push)类似于在单链表中表头添加节点；出栈(pop)类似于链表中表头删除节点并返回对应节点值；栈顶元素(top)就是获取链表中的第一个元素

链表节点的定义直接嵌套在链表栈类中

代码如下：

# 链表实现栈
class linkedStack(object):

  class Node(object):
    def __init__(self, value=None, next=None):
      self.value = value
      self.next = next

  def __init__(self):
    self.top = None
    self.length = 0

  def is_empty(self):
    return self.length == 0

  def size(self):
    return self.length

  # 获取栈顶元素
  def get(self):
    if self.is_empty():
      raise Exception("Stack is empty!")
    return self.top.value

  # 压栈
  def push(self, value):
    node = self.Node(value)
    old_top = self.top
    self.top = node
    node.next = old_top
    self.length += 1

  # 出栈
  def pop(self):
    if self.length == 0:
      raise Exception("Stack is empty!")

    item = self.top.value
    curnode = self.top.next
    self.top.next = self.top
    self.top = curnode
    self.length -= 1
    return item
if __name__ =="__main__":
  stack = linkedStack()
  stack.push("welcome")
  stack.push("www")
  stack.push("jb51")
  stack.push("net")
  print "栈的长度:", stack.size()
  print "出栈：",stack.pop()
  print "出栈：",stack.pop()
  print "出栈：",stack.pop()
  print "出栈：",stack.pop()

运行结果：

栈的长度: 4

出栈： net

出栈： jb51

出栈： www

出栈： welcome