栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，它只允许在一端（称为栈顶）进行插入和删除操作。栈的这种特性使得它在解决函数调用、括号匹配、表达式求值等问题时具有天然的优势。在C++中，栈可以通过标准库中的`std::stack`模板类来实现，也可以手动使用数组或链表等数据结构来实现。
根据底层实现的不同，栈可以分为静态栈和动态栈。静态栈是在编译时确定其大小，通常使用数组来实现；动态栈则是在运行时动态分配内存，大小可以随需调整，通常使用链表或动态数组来实现。
基于数组的栈通常包括以下几个部分：
1. 一个数组，用于存储栈中的元素。
2. 一个整型变量，用于记录栈顶元素的位置（通常指向栈顶元素的下一个位置）。
当进行入栈操作时，将元素放入数组的末尾，并更新栈顶位置；当进行出栈操作时，从数组的末尾移除元素，并更新栈顶位置。
下面是一个简单的基于数组的栈操作的C++实现：
#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;
template <typename T>
class ArrayStack {
private:
vector<T> elements;
public:
// 判断栈是否为空
bool isEmpty() const {
return elements.empty();
}
// 获取栈的大小
size_t size() const {
return elements.size();
}
// 入栈操作
void push(const T& value) {
elements.push_back(value);
}
// 出栈操作
void pop() {
if (isEmpty()) {
throw out_of_range("Stack is empty!");
}
elements.pop_back();
}
// 获取栈顶元素
T& top() {
if (isEmpty()) {
throw out_of_range("Stack is empty!");
}
return elements.back();
}
// 获取栈顶元素（常量版本）
const T& top() const {
if (isEmpty()) {
throw out_of_range("Stack is empty!");
}
return elements.back();
}
};
int main() {
ArrayStack<int> stack;
// 入栈操作
stack.push(1);
stack.push(2);
stack.push(3);
// 输出栈的大小
cout << "Size of stack: " << stack.size() << std::endl;
// 输出栈顶元素
cout << "Top element: " << stack.top() << std::endl;
// 出栈操作
stack.pop();
stack.pop();
// 再次输出栈顶元素
cout << "Top element after popping: " << stack.top() << std::endl;
return 0;
}结果如下所示：
在这个例子中，我们使用`vector`作为底层数组来实现栈。`push`方法用于入栈操作，将元素添加到数组的末尾；`pop`方法用于出栈操作，移除数组的最后一个元素；`top`方法用于获取栈顶元素。此外，我们还提供了`isEmpty`和`size`方法来检查栈是否为空以及获取栈的大小。在`main`函数中，我们展示了如何使用这个基于数组的栈类进行基本的栈操作。
