数据结构--栈

**栈（Stack）数据结构**

栈是一种线性数据结构，它遵循后进先出（LIFO）的原则，即最后添加的元素将首先被移除。栈通常使用数组或链表来实现。

**栈的基本操作**

栈支持以下基本操作：

1. **push（x）**: 将元素 x 添加到栈顶。
2. **pop（）：** 移除并返回栈顶元素。
3. **peek（）：** 返回但不移除栈顶元素。
4. **isEmpty（）：** 检查栈是否为空。
5. **size（）：** 返回栈中元素的数量。

**栈的实现**

我们可以使用数组或链表来实现栈。下面是使用数组实现栈的示例代码：

cppclass Stack {
private:
 int* elements;
 int capacity;
 int top;

public:
 // 构造函数，初始化栈大小为10 Stack(int size =10) : capacity(size), top(-1) {
 elements = new int[capacity];
 }

 // 销毁栈 ~Stack() {
 delete[] elements;
 }

 // 将元素 x 添加到栈顶 void push(int x) {
 if (top == capacity -1) {
 // 栈满，需要扩容 int* temp = new int[capacity *2];
 for (int i =0; i <= top; ++i) {
 temp[i] = elements[i];
 }
 delete[] elements;
 elements = temp;
 capacity *=2;
 }
 elements[++top] = x;
 }

 // 移除并返回栈顶元素 int pop() {
 if (isEmpty()) {
 throw std::runtime_error("Stack is empty");
 }
 return elements[top--];
 }

 // 返回但不移除栈顶元素 int peek() {
 if (isEmpty()) {
 throw std::runtime_error("Stack is empty");
 }
 return elements[top];
 }

 // 检查栈是否为空 bool isEmpty() const {
 return top == -1;
 }

 // 返回栈中元素的数量 int size() const {
 return top +1;
 }
};