Python数据结构实现：栈、队列、双端队列与链表详解

清欢

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

原创

本文详细讲解如何在Python中手动实现栈、队列、双端队列和链表四种基础数据结构。通过具体代码示例，演示了Stack、Queue、Deque和Link类的核心方法，包括入栈、出队、添加节点及遍历等功能，并结合烫手山芋游戏和回文检查案例说明实际应用。

Python栈的实现与操作

模拟栈

Stack() 用于创建一个新的空栈实例。该方法不接受任何参数，执行后返回一个初始状态为空的栈对象。
push(item) 方法用于将指定元素 item 压入栈顶。此操作需要传入 item 作为参数，执行后不返回任何值，但栈的结构会随之改变。
pop() 方法用于移除并返回栈顶的元素。该方法无需参数，执行后会修改栈的状态，并返回被移除的那个 item。
peek() 方法用于查看栈顶元素但不将其移除。该方法无需参数，执行后不会修改栈的内容，仅返回栈顶的 item。
isEmpty() 方法用于检测栈是否为空状态。该方法无需参数，执行后返回布尔值，若栈为空则返回 True，否则返回 False。
size() 方法用于获取栈中当前包含的元素数量。该方法无需参数，执行后返回一个表示元素个数的整数。


class Stack():
  def __init__(self):
    self.items = []
  def push(self,item):
    self.items.append(item)
  def pop(self):
    return self.items.pop()
  def peek(self):
    return len(self.items) - 1
  def isEmpty(self):
    return self.items == []
  def size(self):
    return len(self.items)
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop())
print(s.pop())
print(s.pop())
print(s.isEmpty())

Python队列的模拟应用

模拟队列

Queue() 用于创建一个新的空队列实例。该方法不接受任何参数，执行后返回一个初始状态为空的队列对象。
enqueue(item) 方法用于将新元素 item 添加到队列尾部。该方法需要传入 item 作为参数，执行后不返回任何值，但队列内容会更新。
dequeue() 方法用于移除并返回队列头部的元素。该方法无需参数，执行后会修改队列状态，并返回被移除的 item。
isEmpty() 方法用于判断队列是否为空。该方法无需参数，执行后返回布尔值，若队列为空则返回 True，否则返回 False。
size() 方法用于返回队列中当前元素的总数。该方法无需参数，执行后返回一个表示元素数量的整数。


class Queue():
  def __init__(self):
    self.items = []
  def enqueue(self,item):
    self.items.insert(0,item)
  def dequeue(self):
    return self.items.pop()
  def isEmpty(self):
    return self.items == []
  def size(self):
    return len(self.items)
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

烫手山芋游戏策略模拟

案例：烫手山芋

烫手山芋游戏规则如下：6个孩子围成一圈，顺序由孩子们自行指定。起始时第一个孩子手持烫手山芋，计时器每秒传递一次给下一位孩子。规则设定为每计时7秒，持有山芋的孩子退出游戏。游戏持续进行直到仅剩一名孩子，该孩子即为获胜者。请使用队列数据结构来模拟此策略，并确定最终获胜者的初始位置。

核心准则：在模拟过程中，必须确保队列头部始终持有山芋，以便进行传递和移除操作。


queue = Queue()
kids = ['A','B','C','D','E','F']
#将六个孩子添加到队列中，A是队头位置的孩子
for kid in kids:
  queue.enqueue(kid)

while queue.size() > 1:
  #在7秒之内山芋会被传递6次
  for i in range(6):
    kid = queue.dequeue()
    queue.enqueue(kid)
  queue.dequeue()

print('获胜者为：',queue.dequeue())

双端队列的功能与实现

模拟双端队列

与普通队列不同，双端队列（Deque）拥有两个开口（头部和尾部），允许在两端进行数据的插入和删除操作，从而兼具栈和队列的部分特性。

Deque() 用于创建一个新的空双端队列实例。该方法不接受任何参数，执行后返回一个初始状态为空的 deque 对象。
addFront(item) 方法用于将新元素 item 添加到双端队列的头部。该方法需要传入 item 作为参数，执行后不返回任何值。
addRear(item) 方法用于将新元素 item 添加到双端队列的尾部。该方法需要传入 item 作为参数，执行后不返回任何值。
removeFront() 方法用于从双端队列头部移除元素。该方法无需参数，执行后会修改 deque 状态，并返回被移除的 item。
removeRear() 方法用于从双端队列尾部移除元素。该方法无需参数，执行后会修改 deque 状态，并返回被移除的 item。
isEmpty() 方法用于测试双端队列是否为空。该方法无需参数，执行后返回布尔值，若为空则返回 True。
size() 方法用于返回双端队列中元素的总数。该方法无需参数，执行后返回一个表示元素数量的整数。

基于双端队列的回文检查

案例：回文检查

回文是指一个字符串从前往后读和从后往前读字符序列完全相同，例如 'radar'、'toot' 或 'madam'。


def isHuiWen(s):
  ex = True
  q = Dequeue()
  # 将字符串的每一个字符添加到双端队列中
  for ch in s:
    q.addFront(ch)
  for i in range(len(s) // 2):
    font = q.removeFront()
    rear = q.removeRear()
    if font != rear:
      ex = False
      break
  return ex

Python链表的构建与遍历

模拟链表

.is_empty()：用于判断链表是否为空。
.length()：用于获取链表的节点总数。
.travel()：用于遍历并输出链表中的所有元素。
.add(item)：用于在链表头部插入新元素。
.append(item)：用于在链表尾部追加新元素。
.insert(pos, item)：用于在指定位置 pos 插入新元素 item。
.remove(item)：用于删除链表中第一个匹配的元素 item。
.search(item)：用于查找链表中是否存在元素 item，并返回布尔结果。

结点对象：


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

链表对象：


class Link():
  #构建出一个空的链表
  def __init__(self):
    self._head = None #永远指向链表中的头节点
    #想链表的头部插入节点
  def add(self,item):
    node = Node(item)
    node.next = self._head
    self._head = node

  def travel(self):  
    cur = self._head
    #链表为空则输出‘链表为空'
    if self._head == None:
      print('链表为空！')
    while cur:
      print(cur.item)
      cur = cur.next
  def isEmpty(self):
    return self._head == None
  def length(self):
    cur = self._head
    count = 0
    while cur:
      count += 1
      cur = cur.next
    return count     
  def search(self,item):
    cur = self._head
    find = False
    while cur:
      if cur.item == item:
        find = True
        break
      cur = cur.next
    return find

  def append(self,item):
    node = Node(item)
    #链表为空的情况
    if self._head == None:
      self._head = node
      return

    cur = self._head #头节点
    pre = None #cur的前一个节点
    while cur:
      pre = cur
      cur = cur.next
    pre.next = node

  def insert(self,pos,item):
    node = Node(item)

    if pos < 0 or pos > self.length():
      print('重新给pos赋值！！！')
      return

    cur = self._head
    pre = None

    for i in range(pos):
      pre = cur
      cur = cur.next
    pre.next = node
    node.next = cur
  def remove(self,item):
    cur = self._head
    pre = None

    if self._head == None:#链表为空
      print('链表为空，没有可删除的节点！！1')
      return
    #删除的是第一个节点的情况
    if self._head.item == item:
      self._head = self._head.next
      return

    #删除的是非第一个节点的情况
    while cur:
      pre = cur
      cur = cur.next
      if cur.item == item:
        pre.next = cur.next
        return

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。