11 - 堆栈 - 堆栈

**堆栈**

堆栈是一种线性数据结构，类似于一个书架。它支持两种基本操作：入栈（push）和出栈（pop）。入栈是指将元素添加到栈顶，而出栈则是指从栈顶移除元素。

**堆栈的定义**

堆栈可以用数组或链表来实现。下面是一个使用数组实现的堆栈的例子：

ctypedef struct {
 int* data;
 int top; // 栈顶索引 int capacity; // 容量} Stack;

// 初始化堆栈void initStack(Stack* stack, int capacity) {
 stack->data = (int*)malloc(sizeof(int) * capacity);
 stack->top = -1;
 stack->capacity = capacity;
}

// 入栈void push(Stack* stack, int value) {
 if (stack->top == stack->capacity -1) {
 // 栈满，需要扩容 stack->capacity *=2;
 int* newData = (int*)malloc(sizeof(int) * stack->capacity);
 for (int i =0; i <= stack->top; i++) {
 newData[i] = stack->data[i];
 }
 free(stack->data);
 stack->data = newData;
 }
 stack->data[++stack->top] = value;
}

// 出栈int pop(Stack* stack) {
 if (stack->top == -1) {
 // 栈空，无法出栈 return -1; // 或抛出异常 }
 int value = stack->data[stack->top--];
 free(stack->data);
 stack->data = (int*)malloc(sizeof(int) * stack->capacity /2);
 for (int i =0; i <= stack->top; i++) {
 stack->data[i] = stack->data[i +1];
 }
 return value;
}

**堆栈的应用**

堆栈有很多应用场景，例如：

* **表达式求值**: 使用堆栈可以很容易地实现表达式求值。例如，表达式 `3+4*5` 可以使用堆栈来计算。
* **HTML解析**: HTML 解析器通常使用堆栈来存储 HTML 元素的结构信息。
* **逆波兰表达式**: 使用堆栈可以很容易地实现逆波兰表达式的求值。

**堆栈的优点**

堆栈有很多优点，例如：

* **高效**: 堆栈的入栈和出栈操作都是 O(1) 的。
* **空间效率**: 堆栈可以很容易地扩容或收缩来适应数据的大小。

**堆栈的缺点**

堆栈也有很多缺点，例如：

* **难以实现**: 堆栈的实现需要考虑到入栈和出栈操作的顺序和逻辑。
* **容易溢出**: 如果堆栈过度使用或没有适当扩容，可能会导致溢出。

**总结**

堆栈是一种线性数据结构，支持两种基本操作：入栈和出栈。它有很多应用场景，如表达式求值、HTML 解析和逆波兰表达式的求值。堆栈的优点包括高效和空间效率，但也有一些缺点，如难以实现和容易溢出。