python 堆栈|极客教程

python 堆栈

堆栈（Stack）是一种常见的数据结构，它遵循先进后出（FILO）的原则。在堆栈中，元素只能在一端进行插入和删除操作，这一端称为栈顶。堆栈通常用于函数调用、表达式求值、内存分配等方面。在本文中，我们将详细讨论堆栈的概念、实现以及在Python中的应用。

堆栈的基本概念

堆栈是一种线性数据结构，它包含一组元素，这些元素按照特定的方式进行添加和删除。堆栈的基本操作包括压栈（push）和弹栈（pop）两种。压栈是将一个新元素放入堆栈顶部，而弹栈则是从堆栈顶部取出一个元素。

堆栈的特点是后进先出，也就是最后压入堆栈的元素最先被弹出。这一特性使得堆栈非常适用于一些特定的应用场景，比如函数调用时保存上下文信息、表达式求值时保存运算符和操作数等待、括号匹配等。

堆栈的实现

堆栈的实现可以通过数组或链表来完成。在本文中，我们将使用Python中的列表（list）来实现堆栈。具体来说，通过列表的append()方法向堆栈顶部添加元素，通过pop()方法从堆栈顶部删除元素。

下面是一个简单的堆栈类的实现：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None

    def is_empty(self):
        return len(self.items) == 0

    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        else:
            return None

    def size(self):
        return len(self.items)

在上面的代码中，我们定义了一个Stack类，其中包括push()、pop()、is_empty()、peek()和size()等方法。push()方法用于压入元素，pop()方法用于弹出元素，is_empty()方法用于判断堆栈是否为空，peek()方法用于查看堆栈顶部元素，size()方法用于返回堆栈的大小。

堆栈的应用

在Python中，堆栈有着广泛的应用。下面我们将介绍一些堆栈在实际开发中的应用场景。

函数调用

在函数调用过程中，每次调用函数时都会将函数的参数、局部变量和返回地址等信息保存在堆栈中。当函数执行完毕时，这些信息会被依次弹出，恢复到调用函数的上下文中。

下面是一个简单的示例，演示了函数调用时堆栈的应用：

def func1():
    print("enter func1")
    func2()
    print("exit func1")

def func2():
    print("enter func2")

func1()

运行上面的代码，会输出以下结果：

enter func1
enter func2
exit func1

在上面的示例中，调用func1()函数时，会先打印”enter func1″，然后调用func2()函数，打印”enter func2″，最后再打印”exit func1″。这个过程符合堆栈的先进后出特性。

表达式求值

在表达式求值过程中，我们通常会使用堆栈来保存运算符和操作数，以便按正确的顺序计算表达式的值。下面是一个简单的示例：

def evaluate_expression(expression):
    stack = Stack()
    for char in expression:
        if char.isdigit():
            stack.push(int(char))
        else:
            if char == '+':
                a = stack.pop()
                b = stack.pop()
                stack.push(a + b)
            elif char == '*':
                a = stack.pop()
                b = stack.pop()
                stack.push(a * b)
    return stack.pop()

result = evaluate_expression("52+3*4+")
print(result)

在上面的代码中，我们定义了一个evaluate_expression()函数，用于计算一个简单的后缀表达式。通过堆栈来保存操作数，每当遇到运算符时，弹出两个操作数进行计算，并将结果压回堆栈中。最终，计算得出的结果就是表达式的值，输出为20。