概念及结构：
栈是一种特殊的线性表，它只允许在固定的一端进行插入和删除元素的操作。进行数据插入和删除操作的一端被我们称之为栈顶，另一端被称之为栈底。栈中的数据元素遵守后进先出、先进后出的原则。
压栈：栈的插入操作被叫做进栈/压栈/入栈，进入的数据在栈顶。
出栈：栈的删除操作被叫做出栈。删除的数据也在栈顶。
栈的实现：
栈的实现一般可以使用数组或者链表实现，相对于而言数组的结构实现更优一些。因为数组尾插数据的代价要比链表小。
代码实现：
#pragma once #include <stdbool.h> #include <stdio.h> #include <assert.h> #include <stdlib.h> // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* a; int top; // 栈顶 int capacity; // 容量 }Stack; //初始化栈 void StackInit(Stack* ps); //入栈 void StackPush(Stack* ps, STDataType x); //出栈 void StackPop(Stack* ps); //获取栈顶元素 STDataType StackTop(Stack* ps); //获取栈中有效元素个数 int StackSize(Stack* ps); //检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); //销毁栈 void StackDestroy(Stack* ps);
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" //初始化栈 void StackInit(Stack* ps) { assert(ps); //开空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { perror("malloc fail"); exit(-1); } ps->top = 0; ps->capacity = 4; } //入栈 void StackPush(Stack* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity *= 2; } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } //获取栈顶元素 STDataType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } //获取栈中有效元素个数 int StackSize(Stack* ps) { assert(ps); return ps->top; } //检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps) { assert(ps); //如-1为空，如果等式成立，结果为真，返回真，非零为真 return ps->top == -1; } //销毁栈 void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a == NULL; ps->top = ps->capacity = 0; }
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" int main() { Stack st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); printf("size:%d\n", StackSize(&st)); printf("size:%d\n", st.top + 1); StackPop(&st); StackPop(&st); StackPop(&st); printf("size:%d\n", StackSize(&st)); StackDestroy(&st); return 0; }
