Python栈的两种实现方式：列表与单链表详解

Theo

发布时间：2026-10-14| 3人浏览过

原创

本文详细介绍Python中栈的两种核心实现方法。首先演示如何利用Python内置列表特性构建栈，包括压栈、出栈及获取栈顶元素的操作；随后深入讲解基于单链表的栈实现，通过定义节点类处理头插与头删逻辑。文中提供完整代码及运行结果，帮助开发者理解栈的结构与操作原理。

Python栈的实现原理

本文通过具体实例展示Python语言中栈结构的实现方案，旨在为读者提供可参考的代码与实践思路。

Python栈的实现原理

第一种实现方式基于数组结构，即利用Python列表（List）的特性来模拟栈的行为。

列表实现栈的代码示例

具体代码实现如下：


# 列表实现栈，利用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()

运行链表栈代码后的输出结果如下：