Python实现栈与队列：核心逻辑与代码解析

栈（Stack）的核心机制与Python实现

栈是一种运算受限的线性表，其核心特征在于“后进先出”（LIFO）。所有的插入（入栈）和删除（出栈）操作仅允许在栈顶进行，栈底则是相对固定的另一端。在Python中，我们可以利用列表（List）来模拟栈的行为，通过封装类来规范操作接口。

基础栈类的构建

实现一个基础的栈类需要包含判断空栈、入栈、出栈、查看栈顶元素以及获取栈大小的方法。以下代码展示了基于Python列表的栈实现：

class Stack(object):
  def __init__(self):
    self.stack=[]
  def isEmpty(self):
    return self.stack==[]
  def push(self,item):
    self.stack.append(item)
  def pop(self):
    if self.isEmpty():
      raise IndexError,'pop from empty stack'
    return self.stack.pop()
  def peek(self):
    return self.stack[-1]
  def size(self):
    return len(self.stack)

栈的典型应用场景

栈在计算机科学中有多种重要应用，包括检查程序中的成对符号、进制转换以及表达式求值。

1. 括号匹配检查

在语法检查中，栈用于验证成对符号（如 `(`, `{`, `[` 与 `)`, `}`, `]`）是否正确闭合。算法逻辑如下：

• 遍历字符串，遇到开放符号（`(`, `{`, `[`）时执行入栈操作。
• 遇到闭合符号（`)`, `}`, `]`）时，检查栈是否为空。若为空，则直接报错（缺少开放符号）。
• 若栈非空，弹出栈顶元素并与当前闭合符号进行匹配。若不匹配，则报错。
• 遍历结束后，若栈非空，说明存在未闭合的开放符号，同样报错。

以下是实现该逻辑的代码：

def match(i,j):
  opens='([{'
  closes=')]}'
  return opens.index(i)==closes.index(j)
def syntaxChecker(string):
  stack=Stack()
  balanced=True
  for i in string:
    if i in '([{':
      stack.push(i)
    elif i in ')]}':
      if stack.isEmpty():
        balanced=False
        break
      else:
        j=stack.pop()
        if not match(j,i):
          balanced=False
        break
  if not stack.isEmpty():
    balanced=False
  return balanced

2. 十进制转二进制

将十进制数转换为二进制数的过程，本质上是不断除以2取余数的过程。利用栈的LIFO特性，可以将余数依次入栈，最后依次出栈并拼接，即可得到正确的二进制字符串。具体步骤为：

1. 当商数大于0时，计算余数并入栈。
2. 更新商数为原商数除以2的整数部分。
3. 当商数为0时，将栈中所有元素依次弹出并拼接成字符串。

代码实现如下：

def decimal_to_bin(dec):
  stack=Stack()
  cur=dec
  while cur>0:
    a=cur%2
    cur=cur/2
    stack.push(a)
  binstr=''
  while not stack.isEmpty():
    binstr+=str(stack.pop())
  return binstr

3. 中缀表达式转后缀表达式

后缀记法（逆波兰记法）使用栈来处理表达式，避免了括号带来的优先级复杂性。转换规则如下：

• 遇到数字直接输出。
• 遇到运算符时，比较其与栈顶运算符的优先级。若栈顶运算符优先级大于或等于当前运算符，则弹出栈顶运算符并输出，直到栈空或栈顶优先级更低，然后将当前运算符入栈。
• 遇到左括号 `(` 直接入栈。
• 遇到右括号 `)` 时，不断弹出栈顶运算符并输出，直到弹出左括号（左括号不输出）。
• 表达式遍历结束后，将栈中剩余运算符全部弹出。

例如，`(7+8)/(3+2)` 的后缀记法为 `7 8 + 3 2 + /`。以下是转换及求值的代码：

def infixtoPostfix(infix):
  a={}
  a['*']=3
  a['/']=3
  a['+']=2
  a['-']=2
  a['(']=1
  stack=Stack()
  post=''
  for i in infix:
    if i not in a and i!=')':
      post+=i
    elif i=='(':
      stack.push(i)
    elif i==')':
      top=stack.pop()
      while top!='(':
        post+=top
        top=stack.pop()
    else:     
      while not stack.isEmpty() and a[i]<=a[stack.peek()]:
        post+=stack.pop()
      stack.push(i)
  while not stack.isEmpty():
    post+=stack.pop()
  return post
          
def postfixExp(postfix):
  stack=Stack()
  postlist=postfix.split()
  for i in postlist:
    if i not in '+-*/':
      stack.push(i)
    else:
      a=stack.pop()
      b=stack.pop()
      result=math(i,b,a)
      stack.push(result)
  return stack.pop()
def math(x,y,z):
  if x=='+':
    return float(y)+float(z)
  if x=='-':
    return float(y)-float(z)
  if x=='*':
    return float(y)*float(z)
  if x=='/':
    return float(y)/float(z)

队列（Queue）的实现逻辑

队列是一种特殊的线性表，遵循“先进先出”（FIFO）原则。与栈不同，队列在表的前端进行删除操作（出队），在表的后端进行插入操作（入队）。进行插入操作的端称为队尾，进行删除操作的端称为队头。

基础队列类的构建

在Python中，同样可以使用列表来模拟队列。需要注意的是，从列表前端删除元素的时间复杂度为O(n)，因此在处理大规模数据时，建议使用 `collections.deque` 以获得O(1)的性能。以下是基础队列类的实现：

class Queue(object):
  def __init__(self):
    self.queue=[]
  def isEmpty(self):
    return self.queue==[]
  def enqueue(self,x):
    self.queue.append(x)
  def dequeue(self):
    if self.queue:
      a=self.queue[0]
      self.queue.remove(a)
      return a
    else:
      raise IndexError,'queue is empty'
  def size(self):
    return len(self.queue)

通过上述代码，我们实现了栈和队列的基本数据结构，并展示了它们在括号匹配、进制转换和表达式求值中的实际应用。掌握这些基础数据结构及其实现原理，是深入理解算法和解决复杂编程问题的关键。

以上就是Python数据结构之栈、队列的实现代码分享的详细内容，更多关于Python数据结构、算法实现资料请关注本站其它相关文章！