博客

Python数据结构与算法中的栈详解(1)

  • Post category:Python

Python数据结构与算法中的栈详解(1)

简介

在Python中，栈(Stack)是一种常用的数据结构，该数据结构为一种先进后出(FILO，即First In Last Out)的结构。

举个例子，如同叠盘子一般，你叠一个盘子在另一个盘子上，你只能往上盖盘子，只有最上面的盘子能够被取下，下面的盘子只有等到上面的盘子被取下，才能够被取下来。

栈的特点

栈的特点可以总结为以下三点：

  1. 只能在表尾进行插入和删除操作。
  2. 栈中的元素具有后进先出的特点。
  3. 在栈中，除了栈顶元素之外，没有任何一个元素能够直接访问。

Python中栈的实现

列表实现

Python中可以通过列表的操作实现栈，使用append函数模拟入栈操作，使用pop函数模拟出栈操作。

stack = []

# 入栈操作
stack.append(1)
stack.append(2)
stack.append(3)

# 出栈操作
print(stack.pop()) # 输出3
print(stack.pop()) # 输出2
print(stack.pop()) # 输出1

queue模块实现

Python中还可以借助queue模块实现栈。

import queue

stack = queue.LifoQueue()

# 入栈操作
stack.put(1)
stack.put(2)
stack.put(3)

# 出栈操作
print(stack.get()) # 输出3
print(stack.get()) # 输出2
print(stack.get()) # 输出1

以上两种方式都可以实现栈的基本操作，在实现中需要注意栈空和栈满的情况。

实际应用

括号匹配问题

括号匹配问题是一个经典的应用场景，判断一个字符串中的各个括号是否为匹配的括号。

例如({[()]})是匹配的，({[]})}是不匹配的。

代码实现：

def match_brackets(s):
    stack = []
    brackets = {'(':')', '{':'}', '[':']'}
    for c in s:
        if c in brackets:    # 左括号入栈
            stack.append(c)
        elif stack and c == brackets[stack[-1]]:    # 匹配的右括号出栈
            stack.pop()
        else:
            return False
    return not stack    # 如果栈为空则说明全部匹配

栈的运用

栈的应用非常广泛，例如计算器就可以利用栈来实现。以下示例为利用栈解决逆波兰表达式的问题。

在逆波兰表达式中，操作符在操作数之后。例如：

2 1 + 3 *

等价于

(2 + 1) * 3 = 9

代码实现：

def eval_rpn(tokens):
    stack = []
    operations = {
        "+": lambda x, y: x + y,
        "-": lambda x, y: x - y,
        "*": lambda x, y: x * y,
        "/": lambda x, y: int(x / y)
    }
    for token in tokens:
        if token in operations:
            a, b = stack.pop(), stack.pop()
            stack.append(operations[token](b, a))
        else:
            stack.append(int(token))
    return stack[0]

总结

本文通过介绍栈的定义和特点，了解了Python中栈的基本实现方式，并通过示例代码展示了栈在实际应用中的使用。在Python中，栈的应用非常广泛，如果想要成为一个优秀的Python程序员，栈应该是必须要掌握的基本单元之一。

Tags: ,