基础算法-数组模拟栈

**基础算法 - 数组模拟栈**

在计算机科学中，栈是一种非常重要的数据结构，它遵循后进先出(Last In First Out, LIFO)原则。栈通常使用数组来实现，这样可以有效地利用内存空间。下面我们将介绍如何使用数组模拟栈。

**栈的基本操作**

栈支持以下四种基本操作：

1. **push**: 将元素添加到栈顶。
2. **pop**: 移除栈顶元素。
3. **peek**: 查看栈顶元素（但不移除）。
4. **isEmpty**: 判断栈是否为空。

**数组模拟栈的实现**

我们将使用一个动态大小的数组来模拟栈。这个数组将作为栈的底层存储结构。

cppclass ArrayStack {
private:
 int* array; // 数组指针 int size; // 当前元素数量 int capacity; // 最大容量public:
 ArrayStack(int initialCapacity =10) {
 capacity = initialCapacity;
 array = new int[capacity];
 size =0;
 }

 ~ArrayStack() {
 delete[] array;
 }

 void push(int element) {
 if (size == capacity) {
 // 如果栈满了，需要扩容 capacity *=2; // 扩容为原来的两倍 int* newArray = new int[capacity];
 for (int i =0; i < size; ++i) {
 newArray[i] = array[i]; // 将原数组元素复制到新数组中 }
 delete[] array;
 array = newArray;
 }

 array[size++] = element; // 添加元素 }

 int pop() {
 if (isEmpty()) {
 throw std::runtime_error("Stack is empty");
 }

 return array[--size]; // 移除栈顶元素并返回其值 }

 int peek() {
 if (isEmpty()) {
 throw std::runtime_error("Stack is empty");
 }

 return array[size -1]; // 返回栈顶元素的值（不移除）
 }

 bool isEmpty() const {
 return size ==0;
 }
};

cppint main() {
 ArrayStack stack;

 stack.push(5);
 stack.push(10);
 stack.push(15);

 std::cout << "栈顶元素：" << stack.peek() << std::endl; // 输出：15 int poppedElement = stack.pop();
 std::cout << "弹出元素：" << poppedElement << std::endl; // 输出：15 std::cout << "栈是否为空：" << (stack.isEmpty() ? "是" : "否") << std::endl; // 输出：否 return0;
}