首先，栈是一个表，栈限制了插入和删除操作只能在一个位置上进行，这个位置是表的末端，所以栈是一种先进后出的数据结构
栈的实现非常简单，尤其是使用链表，只需要维护一个栈顶指针，入栈时将指针移到新加入的节点，出栈时将指针移到下一个节点
本文介绍栈的数组实现
实现思路：
1.维护一个栈顶索引
2.入栈时将索引 + 1
3.出栈时将索引 - 1
4.入栈和出栈前判断栈是否为满和空
代码实现
1.定义栈结构体：
typedef struct { int *data; // 栈的实际内存空间,是一个数组 int top; //栈顶索引 int capacity; // 栈空间的大小 } stack;
2.初始化栈
void init_stack(stack *stack) { stack->data = (int *)malloc(INITIAL_CAPACITY * sizeof(int)); // 分配空间 stack->top = -1; // 栈顶初始索引为-1 stack->capacity = INITIAL_CAPACITY; // 默认大小 }
3.动态扩容
void expand(stack* stack) { stack->capacity *= 2; // 增长栈空间，为原来的2倍 stack->data = (int *)relloc(stack->data, stack->capacity * sizeof(int)); }
4.入栈
void push(stack *stack, int value) { if (stack->top == stack->capacity - 1) { // 空间是否足够 expand(stack); // 不够则扩容 } stack->data[++stack->top] = value; // 入栈 }
5.出栈
int pop(stack *stack) { if (is_empty(stack)) { printf ("stack is empty now!\n"); exit(EXIT_FAILURE); } return stack->data[stack->top--]; }
6.销毁栈
void free_stack(stack *stack) { free(stack->data); stack->data = NULL; stack->top = -1; stack->capacity = 0; }
7.测试
int main() { stack stack; init_stack(&stack); push(&stack, 10); push(&stack, 11); push(&stack, 12); push(&stack, 13); printf("Top element is %d\n", peek(&stack)); printf("Popped element is %d\n", pop(&stack)); printf("Top element is now %d\n", peek(&stack)); free_stack(&stack); return 0; }
