1.栈的概念
栈，一种特殊的线性表，特殊在于只允许在固定的一端进行插入删除数据，插入和删除数据的一端是栈顶，另一端是栈底，已经在栈中的数据满足Fist In Last Out的原则。
压栈：栈顶插入数据
出栈：栈顶弹出数据
2.栈的结构
总体而言，用顺序表和链表实现都可以，但是由于栈只支持在栈顶插入删除数据，且要满足后进先出，而顺序表尾插尾删的效率比链表高，（顺序表唯一的缺点在这就是扩容有性能和空间的消耗）同时也满足后进先出的原则，所以选择顺序表实现好！
有人可能会说用链表，然后定义一个尾指针，这样尾插效率不是也很高吗？
答：定义一个尾指针，链表的插入时很方便，但是尾删呐？？
其实顺序表，双向循环链表，头上操作单链表都行，但是由于顺序表命中率高的优点，还是选择顺序表。
3.实现栈的基本操作
3.1栈的初始化
选择哪一个方式初始化top都可以，但是记得做到和后面的push等做到统一。
建议再主函数内判空操作不直接自己if(ps->top==0)等，因为这个内部怎么实现的不一定是初始化为ps->top=0,而是建议调用函数去判空if(StackEmpty(&ST)
void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; }
3.2压栈
void StackPush(Stack* ps, STDateType x) { assert(ps); if(ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2; STDateType* temp = (STDateType*)realloc(ps->a, sizeof(STDateType)*newcapacity); if (temp == NULL) { perror("malloc fail.\n"); exit(-1); } ps->capacity = newcapacity; ps->a = temp; } ps->a[ps->top] = x; ps->top++; }
3.3出栈
void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; }
3.4 取栈顶元素
STDateType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; }
3.5 计算栈内元素个数
1. int StackSize(Stack* ps) 2. { 3. assert(ps); 4. return ps->top; 5. }
3.6栈的判空
1. bool StackEmpty(Stack* ps) 2. { 3. assert(ps); 4. return ps->top == 0; 5. }
3.7栈的销毁
void StackDestory(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
4.源代码
4.1stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"stack.h" void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(Stack* ps, STDateType x) { assert(ps); if(ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2; STDateType* temp = (STDateType*)realloc(ps->a, sizeof(STDateType)*newcapacity); if (temp == NULL) { perror("malloc fail.\n"); exit(-1); } ps->capacity = newcapacity; ps->a = temp; } ps->a[ps->top] = x; ps->top++; } void StackPop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); ps->top--; } STDateType StackTop(Stack* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->top; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } void StackDestory(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
4.2stack.h
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int STDateType; typedef struct Stack { STDateType* a; int top; int capacity; }Stack; void StackInit(Stack* ps); void StackPush(Stack* ps,STDateType x); void StackPop(Stack* ps); STDateType StackTop(Stack* ps); bool StackEmpty(Stack* ps); int StackSize(Stack* ps); void StackDestory(Stack* ps);
4.3test.c
#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); STDateType top = StackTop(&ST); printf("top:%d\n", top); StackPop(&ST); top = StackTop(&ST); printf("top:%d\n", top); int size = StackSize(&ST); printf("size:%d\n", size); StackDestory(&ST); return 0; }
4.4效果图
