数据结构是计算机科学中的核心概念，它涉及到如何高效地存储和操作数据。在这个主题中，我们将专注于栈（Stack）这一特殊的数据结构，以及它的实现算法。栈被誉为“后进先出”（Last In, First Out，简称LIFO）的数据结构，意味着最后存入的数据将首先被取出。
栈在许多计算问题中都有应用，例如表达式求值、函数调用、深度优先搜索等。在C++这样的编程语言中，虽然标准库提供了`<stack>`容器来直接使用栈，但理解栈的基本原理和自定义实现有助于我们更好地掌握其工作方式。
栈的基本操作包括：
1. 入栈（Push）：向栈顶添加一个元素。
2. 出栈（Pop）：移除并返回栈顶的元素。
3. 查看栈顶元素（Top）：不移除地查看栈顶元素。
4. 检查栈是否为空（Empty）：判断栈是否没有任何元素。
在C++中，我们可以使用数组或链表来实现栈。数组实现简单且效率高，但大小固定；链表实现则更灵活，可以动态扩展。
下面我们将以C++为例，讨论栈的两种常见实现：
### 数组实现
```cpp
#include <iostream>
class Stack {
private:
int* arr;
int capacity;
int top;
public:
Stack(int size) : arr(new int[size]), capacity(size), top(-1) {}
~Stack() { delete[] arr; }
bool push(int value) {
if (top >= capacity - 1) return false;
arr[++top] = value;
return true;
}
int pop() {
if (empty()) throw "Stack is empty.";
return arr[top--];
}
int topValue() const {
if (empty()) throw "Stack is empty.";
return arr[top];
}
bool empty() const { return top == -1; }
};
```
### 链表实现
```cpp
#include <iostream>
#include <stdexcept>
struct Node {
int data;
Node* next;
};
class Stack {
private:
Node* top;
public:
Stack() : top(nullptr) {}
~Stack() {
while (top) {
Node* temp = top;
top = top->next;
delete temp;
}
}
void push(int value) {
Node* newNode = new Node{value, top};
top = newNode;
}
int pop() {
if (empty()) throw std::runtime_error("Stack is empty.");
int value = top->data;
Node* temp = top;
top = top->next;
delete temp;
return value;
}
int topValue() const {
if (empty()) throw std::runtime_error("Stack is empty.");
return top->data;
}
bool empty() const { return top == nullptr; }
};
```
在上述代码中，`test001.cpp`可能包含了一些示例代码，用于测试这两种栈实现的正确性。通过编写和运行测试用例，我们可以确保栈的功能正常工作，例如验证`push`、`pop`、`topValue`和`empty`方法的行为。
了解栈的实现不仅有助于我们理解数据结构，还能帮助我们在编程实践中选择最适合特定应用场景的实现方式。同时，这也是对C++内存管理（如动态内存分配和释放）以及异常处理机制的锻炼。在实际项目中，我们可以根据需求选择标准库的`<stack>`容器，或者自定义更高效、更符合特定需求的栈实现。
