什么是栈 (Stack)？

推荐答案

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。栈的操作主要包括入栈（Push）和出栈（Pop），通常还会提供**查看栈顶元素（Peek）**的功能。栈可以用数组或链表来实现。

本题详细解读

栈的基本概念

• 后进先出（LIFO）：栈的核心特性是最后入栈的元素最先出栈。这种特性使得栈在处理某些问题时非常高效，例如函数调用栈、表达式求值等。
• 入栈（Push）：将元素添加到栈的顶部。
• 出栈（Pop）：移除并返回栈顶的元素。
• 查看栈顶元素（Peek）：返回栈顶的元素但不移除它。

栈的实现

栈可以通过数组或链表来实现：

• 数组实现：使用数组来存储栈中的元素，通常需要一个指针（或索引）来跟踪栈顶的位置。数组实现的栈在空间上是连续的，访问速度快，但大小固定。
• 链表实现：使用链表来存储栈中的元素，每个节点包含数据和指向下一个节点的指针。链表实现的栈在空间上是动态的，可以根据需要扩展或缩小，但访问速度相对较慢。

栈的应用场景

• 函数调用栈：在程序执行过程中，函数调用的顺序和返回顺序就是栈的典型应用。
• 表达式求值：栈可以用于解析和计算表达式，例如中缀表达式转后缀表达式。
• 括号匹配：栈可以用于检查代码中的括号是否匹配。
• 撤销操作：许多应用程序中的撤销操作（如文本编辑器中的撤销）通常使用栈来实现。

栈的复杂度分析

• 入栈（Push）：时间复杂度为 O(1)。
• 出栈（Pop）：时间复杂度为 O(1)。
• 查看栈顶元素（Peek）：时间复杂度为 O(1)。
• 空间复杂度：O(n)，其中 n 是栈中元素的数量。

示例代码（Python）

// www.javascriptcn.com code example
class Stack:
    def __init__(self):
        self.stack = []

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

    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
        else:
            raise IndexError("Pop from an empty stack")

    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
        else:
            raise IndexError("Peek from an empty stack")

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

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

# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 输出 2
print(stack.peek())  # 输出 1