什么是堆栈堆栈（Stack）？

堆栈是一种遵循后进先出（LIFO）原则的数据结构，支持两种核心操作：

1. 压栈（Push）：将元素添加到栈顶

2. 弹栈（Pop）：移除栈顶元素

C++实现堆栈的原理3种方式

1. 数组实现

```cpp

define MAX 1000

class Stack {

int top;

public:

int a[MAX];

Stack { top = -1; }

bool push(int x) {

if (top >= MAX-1) return false;

a[++top] = x;

return true;

int pop {

if (top < 0) return 0;

return a[top--];

};

```

2. 链表实现

```cpp

struct Node {

int data;

Node next;

Node(int val) : data(val), next(nullptr) { }

};

class Stack {

Node top;

public:

void push(int val) {

Node temp = new Node(val);

temp->next = top;

top = temp;

void pop {

if (!top) return;

Node temp = top;

top = top->next;

delete temp;

};

```

3. STL标准库（推荐）

```cpp

include

std::stackstk;

// 基本操作

stk.push(10); // 压栈

stk.pop; // 弹栈（需先检查空栈）

int top = stk.top; // 获取栈顶

bool isEmpty = stk.empty; // 判空

```

堆栈的典型应用场景

  • 函数调用时的内存管理
  • 撤销操作（CTRL+Z）的历史记录
  • 括号匹配校验
  • 表达式求值（后缀表达式）

    • 常见问题解决方案

    1. 栈溢出

    通过动态扩容（如STL实现）或预先分配足够空间

    2. 空栈访问

    调用top或pop前检查是否为空：

    ```cpp

    if (!stk.empty) {

    stk.pop;

    ```

    3. 性能优化

  • 优先选用STL（时间复杂度O(1)）
  • 避免频繁的小数据压栈操作

    • 选择建议

  • 学习目的：手动实现理解原理
  • 生产环境：直接使用STL stack
  • 特殊需求（如内存限制）：自定义数组/链表实现

    • 掌握堆栈的底层逻辑和STL的高效用法，能显著提升算法实现和系统设计的堆栈代码质量。

    原理