写一个栈的代码

<think>好的，用户现在想获取栈数据结构的代码实现，并且之前已经询问过关于数据结构1800题PDF的问题。需要结合站内引用的两个关于栈实现的例子，同时参考用户上一次的问题和回答。 首先，用户的上一次问题涉及到合法获取资料的建议，但这次转向具体的代码实现，因此需要专注于技术指导。引用的[1]和[2]提供了C语言实现栈的例子，用户可能希望得到类似的详细代码，但需要确认用户偏好的编程语言。不过用户这次的问题没有明确说明语言，可能需要默认使用C，或者提供多种语言的示例。 用户可能的需求是清晰的代码示例，包含初始化、入栈、出栈等基本操作，并且希望代码结构良好，有注释说明。同时，用户可能关心代码的正确性和效率，比如动态扩容的处理，避免内存泄漏等。 需要注意用户之前的问题提到过Python示例（如快速排序和二叉树遍历），但这次的引用是C语言，所以可能需要同时提供C和Python的实现，以满足不同用户的需求。此外，用户可能对栈的应用场景和常见问题感兴趣，所以相关问题可以涉及这些方面。 需要确保回答结构清晰，分步骤讲解，并附带代码示例。同时，引用之前的参考资料，如动态扩容和初始化方法，以增强可信度。最后，生成的相关问题应引导用户深入理解栈的实现和应用。</think>以下是基于C语言实现栈数据结构的详细指南，结合站内引用内容并优化实现细节： ### 一、栈的代码实现（动态数组版） ```c #include <stdio.h> #include <stdlib.h> #include <stdbool.h> typedef int STDataType; // 栈元素类型可修改 typedef struct Stack { STDataType* array; // 动态数组指针 int top; // 栈顶指针（指向下一个空位） int capacity; // 当前容量 } Stack; // 初始化栈（带动态扩容机制） void StackInit(Stack* ps, int initialCapacity) { ps->array = (STDataType*)malloc(initialCapacity * sizeof(STDataType)); ps->top = 0; ps->capacity = initialCapacity; } // 动态扩容检查（参考引用[2]的容量管理思路） void CheckCapacity(Stack* ps) { if (ps->top == ps->capacity) { int newCapacity = ps->capacity * 2; STDataType* temp = (STDataType*)realloc(ps->array, newCapacity * sizeof(STDataType)); if (temp) { ps->array = temp; ps->capacity = newCapacity; } } } // 入栈操作 void StackPush(Stack* ps, STDataType data) { CheckCapacity(ps); ps->array[ps->top++] = data; // top指向下一个空位[^2] } // 出栈操作 void StackPop(Stack* ps) { if (ps->top > 0) ps->top--; } // 获取栈顶元素 STDataType StackTop(Stack* ps) { if (ps->top == 0) { printf("Stack is empty!\n"); exit(EXIT_FAILURE); } return ps->array[ps->top - 1]; // 注意top指向的是下一个空位[^1] } // 判空操作 bool StackIsEmpty(Stack* ps) { return ps->top == 0; } // 销毁栈 void StackDestroy(Stack* ps) { free(ps->array); ps->array = NULL; ps->top = ps->capacity = 0; } ``` ### 二、代码使用示例 ```c int main() { Stack s; StackInit(&s, 4); // 初始容量设为4 StackPush(&s, 10); StackPush(&s, 20); StackPush(&s, 30); printf("Top element: %d\n", StackTop(&s)); // 输出30 StackPop(&s); printf("After pop, top element: %d\n", StackTop(&s)); // 输出20 StackDestroy(&s); return 0; } ``` ### 三、关键实现细节说明 1. **动态扩容机制**：当栈满时自动扩容为原容量的2倍，避免频繁内存操作（参考引用[2]的容量管理思路） 2. **top指针设计**：采用"指向下一个空位"的方案，初始为0时表示空栈[^1] 3. **类型通用性**：通过`typedef`可快速修改存储数据类型 4. **内存安全**：`StackDestroy`函数确保资源释放，避免内存泄漏 ### 四、复杂度分析 | 操作 | 时间复杂度 | 空间复杂度 | |------------|------------|------------| | Push | O(1)均摊 | O(n) | | Pop | O(1) | O(1) | | Top | O(1) | O(1) |