栈数据结构详解 | Baeldung中文网

1. 简介

在本教程中，我们将学习什么是栈（Stack），以及它是如何工作的。同时，我们也会介绍栈的基本操作及其在编程中的典型应用场景。

栈是一种非常基础且广泛使用的数据结构，在算法、系统调用、表达式求值等多个领域都有重要应用。

2. 什么是栈

栈在生活中随处可见，比如：一摞书、一叠盘子、CD架上的光盘。以书本为例，我们只能从顶部插入或取出书本，这种“只允许在一端操作”的特性，就是栈的核心特征。

✅ 栈是一种只能在一端进行插入和删除的线性表。这一端被称为栈顶（Top）。

栈遵循后进先出（LIFO, Last In First Out）原则。也就是说，最后插入的元素最先被删除，最早插入的元素最后被删除。

因此，栈也被称为先进后出（FILO, First In Last Out）结构。

stack1-1

典型应用场景

函数调用栈（Call Stack）
表达式求值（如中缀转后缀）
括号匹配
浏览器的前进/后退功能
撤销（Undo）与重做（Redo）功能

3. 栈的表示方式

栈在内存中通常使用数组或链表实现。数组实现更常见，因为栈顶位置固定，便于操作。

下面是一个使用数组实现的栈示意图：

stack3-1

栈顶指针始终指向当前栈顶元素。只能通过栈顶进行插入或删除操作。

4. 栈的基本操作

以下是栈的几个基本操作：

push()：将元素压入栈顶
pop()：弹出栈顶元素
peek()：查看栈顶元素（不删除）
isFull()：判断栈是否已满
isEmpty()：判断栈是否为空

4.1 push() 入栈操作

将元素插入栈顶，栈顶指针上移。

function insertIntoStack(stack, data_element):
    // INPUT
    //   stack = the stack
    //   data_element = the element to be inserted
    // OUTPUT
    //   Inserts data_element if the stack isn't full; otherwise, returns an overflow condition

    if stack is full:
        return null
    else:
        top <- top + 1
        stack[top] <- data_element

示例：将 A、B、C 依次压入栈中：

stack5-1

4.2 pop() 出栈操作

将栈顶元素删除，栈顶指针下移。

function removeFromStack(stack):
    // INPUT
    //   stack = the stack
    // OUTPUT
    //   Removes data_element from the top of the stack

    if stack is empty:
        return null
    else:
        data_element <- stack[top]
        top <- top - 1
        return data_element

示例：从包含 A、B、C 的栈中弹出栈顶元素 C：

stack6-1

4.3 peek() 查看栈顶元素

查看栈顶元素但不删除它。

function peekStack(stack):
    // INPUT
    //   stack = the stack
    // OUTPUT
    //   Retrieves data_element from the top of the stack

    if stack is empty:
        return null
    else:
        data_element <- stack[top]
        return data_element

4.4 isFull() 判断栈是否已满

function isStackFull(stack):
    // INPUT
    //   stack = the stack
    // OUTPUT
    //   Returns true if the stack is full, and false otherwise

    if top = MAX_SIZE:
        return true
    else:
        return false

4.5 isEmpty() 判断栈是否为空

function isStackEmpty(stack):
    // INPUT
    //   stack = the stack
    // OUTPUT
    //   Returns true if the stack is empty; otherwise, returns false

    if top < 0:
        return true
    else:
        return false

5. 时间复杂度分析

栈的所有操作都发生在栈顶，不需要遍历整个结构，因此时间复杂度均为 **O(1)**。

操作	时间复杂度
push	O(1)
pop	O(1)
peek	O(1)
isFull	O(1)
isEmpty	O(1)

⚠️ 注意：如果是使用链表实现栈，仍可保持 O(1) 的时间复杂度；但如果使用动态数组实现，push 时可能需要扩容，均摊时间复杂度还是 O(1)。

6. 小结

本文介绍了栈这一基础数据结构的概念、表示方式以及常用操作。总结如下：

✅ 栈是一种 LIFO 结构，只能在栈顶进行插入和删除
✅ 常见操作包括 push、pop、peek、isFull、isEmpty
✅ 所有操作的时间复杂度都是 O(1)
✅ 栈在函数调用、表达式求值、浏览器历史记录等场景中非常实用

栈结构虽然简单，但其背后的“后进先出”思想在很多系统设计中都有体现。掌握它，对理解程序运行机制和算法设计都非常有帮助。

Persistence

REST

Security