栈与队列的深入解析与应用实践

创作时间:

作者:

@小白创作中心

栈与队列的深入解析与应用实践

引用

CSDN

https://blog.csdn.net/qq_57179696/article/details/146318601

栈（Stack）和队列（Queue）是编程中两种基础且重要的数据结构，它们在处理各种算法问题时发挥着关键作用。本文将深入探讨栈与队列的应用，包括括号匹配问题、双栈实现队列、循环队列设计，以及使用栈实现表达式求值的案例。通过详细的代码示例，我们将展示这些数据结构在实际问题中的强大应用。

一、括号匹配问题

括号匹配是栈的一个经典应用。在这个问题中，我们需要检查给定的字符串中的括号是否正确匹配。这包括圆括号()、方括号[]和花括号{}。

栈在括号匹配中的应用

栈的后进先出（LIFO）特性使得它非常适合处理括号匹配问题。每当我们遇到一个左括号时，我们将其压入栈中；每当我们遇到一个右括号时，我们检查栈顶的元素是否与之匹配。如果匹配，则弹出栈顶元素；如果不匹配，则说明括号不匹配。

示例代码

def is_valid_parentheses(s: str) -> bool:
    stack = []
    mapping = {")": "(", "]": "[", "}": "{"}
    
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    
    return not stack

# 示例使用
print(is_valid_parentheses("()"))        # 输出: True
print(is_valid_parentheses("()[]{}"))    # 输出: True
print(is_valid_parentheses("(]"))        # 输出: False
print(is_valid_parentheses("([)]"))      # 输出: False
print(is_valid_parentheses("{[]}"))      # 输出: True

二、双栈实现队列

队列是一种先进先出（FIFO）的数据结构，而栈是后进先出（LIFO）的。然而，我们可以使用两个栈来模拟一个队列的行为。

双栈实现队列的原理

入队操作：将元素压入第一个栈（stack_in）。
出队操作：如果第二个栈（stack_out）为空，则将stack_in中的所有元素弹出并压入stack_out，然后从stack_out弹出栈顶元素；如果stack_out不为空，则直接从stack_out弹出栈顶元素。

示例代码

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []
 
    def enqueue(self, item):
        self.stack_in.append(item)
 
    def dequeue(self):
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
        if self.stack_out:
            return self.stack_out.pop()
        else:
            raise IndexError("dequeue from an empty queue")
 
# 示例使用
queue = QueueUsingStacks()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue())  # 输出: 1
print(queue.dequeue())  # 输出: 2

三、循环队列设计

循环队列是一种特殊的队列，它利用数组实现，并通过两个指针（front和rear）来追踪队列的头和尾。当队列的尾指针到达数组的末尾时，如果数组的前端还有空间，则可以将尾指针循环到数组的开头。

循环队列的关键操作

入队操作：在rear指针的位置插入元素，并更新rear指针。
出队操作：从front指针的位置移除元素，并更新front指针。

示例代码（简化版，不处理动态扩容）

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = 0
        self.rear = -1
        self.size = 0
 
    def enqueue(self, item):
        if self.size == self.capacity:
            raise OverflowError("Queue is full")
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item
        self.size += 1
 
    def dequeue(self):
        if self.size == 0:
            raise IndexError("dequeue from an empty queue")
        item = self.queue[self.front]
        self.queue[self.front] = None  # 不是必需的，但有助于调试
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item
 
# 示例使用
cq = CircularQueue(5)
cq.enqueue(10)
cq.enqueue(20)
print(cq.dequeue())  # 输出: 10
print(cq.dequeue())  # 输出: 20

四、栈实现表达式求值

表达式求值是栈的另一个经典应用。在这里，我们将使用中缀表达式转后缀表达式（逆波兰表达式），然后使用栈来计算后缀表达式的值。

中缀表达式转后缀表达式（简化版，仅支持加减乘除和整数）

def infix_to_postfix(expression):
    precedence = {'+':1, '-':1, '*':2, '/':2}
    stack = []  # 运算符栈
    output = []  # 输出列表
    for char in expression:
        if char.isdigit():
            output.append(char)
        elif char in precedence:
            while (stack and stack[-1] != '(' and
                   precedence[stack[-1]] >= precedence[char]):
                output.append(stack.pop())
            stack.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 弹出 '('
    while stack:
        output.append(stack.pop())
    return ''.join(output)
 
# 示例使用（注意：此简化版未处理多位数和空格）
print(infix_to_postfix("3+5*2"))  # 输出: 352*+ （实际使用时需完善以处理完整表达式）

后缀表达式求值

def evaluate_postfix(expression):
    stack = []
    for char in expression:
        if char.isdigit():
            stack.append(int(char))
        else:
            b = stack.pop()
            a = stack.pop()
            if char == '+':
                stack.append(a + b)
            elif char == '-':
                stack.append(a - b)
            elif char == '*':
                stack.append(a * b)
            elif char == '/':
                stack.append(a / b)  # 注意：这里使用真除法，可根据需要改为整除
    return stack[0]
 
# 结合中缀转后缀（此处直接给后缀示例，实际应使用完整转换后的结果）
# 假设我们已经有了后缀表达式 "352*+" 的完整生成逻辑，这里直接求值
postfix_expr = "352*+"  # 实际上应由完整的中缀转后缀逻辑生成
print(evaluate_postfix(postfix_expr))  # 输出: 13 （基于假设的后缀表达式）

注意：上述中缀转后缀的示例为简化版，未处理多位数、空格和错误输入等情况。在实际应用中，需要更完善的解析逻辑来生成正确的后缀表达式。