1.栈
1.1栈的概念和结构
栈：特殊的线性表，只允许在固定的一端进行插入和删除数据。
进行数据插入和删除的一端称作栈顶，另一端称作栈底。
压栈：栈的插入操作称作压栈，压入栈的数据在栈顶
出栈：栈的删除操作称作出栈，出栈的数据也在栈顶
栈中数据遵守后进先出原则
压栈
出栈
1.2栈的实现
栈的实现有两个选择数组，链表
二者相比，数组实现栈更好些，根据栈的特点，在尾部插入数据的情况下，数组更方便。
数组实现栈
链表实现栈
这里采取数组的结构来实现栈
定义结构体和类型
typedef int SKdatatype; typedef struct Stack { SKdatatype* a; int top;//记录栈中元素的个数 int capacity;//栈的容量 }SK;
初始化栈
//初始化栈 void SKinit(SK* ps); void SKinit(SK* ps) { assert(ps); ps->a = NULL; ps->top = ps->capacity = 0; }
销毁栈
//销毁栈 void SKdestory(SK* ps); void SKdestory(SK* ps) { assert(ps); ps->capacity = ps->top = 0; free(ps->a); ps->a = NULL; }
数据压栈
//压栈 void SKpush(SK* ps, SKdatatype x); void SKpush(SK* ps, SKdatatype x) { assert(ps); //检查容量 if (ps->capacity == ps->top) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; SK* tmp = (SK*)realloc(ps->a, newcapacity * sizeof(SK)); if (tmp == NULL) { perror("realloc fail"); exit(-1); } ps->capacity = newcapacity; ps->a = tmp; } ps->a[ps->top] = x; ps->top++; }
压入两个数据进栈，监视如下
栈顶ps->top此时是2,说明栈中已经有两个数据。
数据出栈
//出栈 void SKpop(SK* ps); void SKpop(SK* ps) { assert(ps); assert(!SKempty(ps)); ps->top--; }
数组中删除元素，不需要清除元素
将栈顶的数据出栈，监视如下
栈顶ps->top此时是1,从上面可知，栈顶的数据已经出栈，栈中还有一个数据。
获得栈顶元素
//获得栈顶元素 SKdatatype SKtop(SK* ps); SKdatatype SKtop(SK* ps) { assert(ps); assert(!SKempty(ps)); return ps->a[ps->top - 1]; }
检查栈是否为空
//检查是否是空栈 bool SKempty(SK* ps); bool SKempty(SK* ps) { assert(ps); return ps->top == 0; }
计算栈中的数据个数
//计算栈中数据的个数 int SKsize(SK* ps); int SKsize(SK* ps) { assert(ps); return ps->top; }
2.队列
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，另一端进行删除数据操作的特殊线性表
队列遵守先进先出原则
队尾：进行插入数据操作的一端
队头：进行删除数据操作的一端
