目录
栈
1、栈的基本概念
2、栈的实现方式——数组
存储结构
初始化
销毁
入栈
取出栈顶元素
获取栈顶元素
判空
获取栈的长度
3、实现方式——链表
存储结构
初始化
销毁
入栈
出栈
获取栈顶元素
获取栈中有效元素个数
判空
队列
基本概念
队列的存储结构
初始化
销毁
判空
队列长
获取头的元素
入队列
出队列
栈
1、栈的基本概念
栈：栈(stack)是限定仅在⼀端进⾏插⼊或删除操作的线性表。
栈顶（top）：能插入和删除的一端
栈顶(bottom)：不能插入和删除的一端
出栈：删除数据（在栈顶）
入栈：放入数据（在栈顶）——也叫压栈/入栈/进栈
空栈：没用任何元素
栈也被称为后进先出的顺序表（Last In First Out），简称LIFO结构
2、栈的实现方式——数组
使用结构选择数组：
因为栈是“尾部操作”最频繁的数据结构（后进先出），而数组在尾部操作（入栈/出栈）的时间复杂度是 O(1)，且内存连续、缓存利用率极高，所以用数组是最自然、最高效的选择。
基本操作：
void STInit(ST* st);//初始化
void STDestroy(ST* st);//销毁
void STPush(ST* st,STDataType x);//入栈
void STPop(ST* st);//出栈
STDataType STTop(ST* st);//获取栈顶元素
bool STEmpty(ST* st);//判空
int STSize(ST* st);//取长度
存储结构
typedef int STDataType; typedef struct Stack { STDataType* a;//存储数组 int top;//栈顶的下一位 int capacity;//容量 }ST;注意：这里的top到底是指向栈顶元素还是栈顶的下一位，如果指向栈顶元素，那么top的初始化就要是-1，如果是栈顶元素的下一位就是0。因为这里要思考一个问题， 就是当top==0的时候，数组是否有元素，如果top==0的时候没用，那么我们就要让top指向栈顶元素的下一位。
下面的top指向的是栈顶元素的下一位。
初始化
void STInit(ST* st) { assert(st); st->a = NULL; st->top = 0; st->capacity = 0; }销毁
void STDestroy(ST* st) { assert(st); free(st->a); st->a = NULL; st->capacity = 0; st->top = 0; }入栈
void STPush(ST* st, STDataType x) { assert(st); if (st->top == st->capacity) { int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2; STDataType* tmp = (STDataType*)realloc(st->a, newcapacity*sizeof(STDataType)); if (tmp==NULL) { perror("realloc fail"); return; } st->a=tmp; st->capacity = newcapacity; } st->a[st->top] = x; st->top++; }取出栈顶元素
void STPop(ST* st) { assert(st); assert(st->top>0); st->top--; }获取栈顶元素
STDataType STTop(ST* st) { assert(st); assert(st->top > 0); return st->a[st->top-1]; }判空
bool STEmpty(ST* st) { assert(st); return st->top == 0; }获取栈的长度
int STSize(ST* st) { assert(st); return st->top; }3、实现方式——链表
链式栈的结构：
可以选择单链表，也可以选择双向链表，但是需要知道的是如果选择单链表，要用头当作栈顶，因为栈的特点就是在栈顶取数据和出数据，单链表在头节点取出和放入数据的时间复杂度都是
O（1），尾节点还要遍历找尾，时间复杂度是O(N)。当然也可以使用双向链表，而且无论是用头还是尾做栈顶，时间复杂度都是O（1），但是建议还是选择单链表，因为单链表相比双向链表节省空间，因此使用单链表。
在使用单链表的时候可以不使用哨兵位头结点，也可用，这里我不用，因为哨兵位头结点，并没有给头删和头插带来遍历，所以不用，也可以节省一个节点的空间。
存储结构
typedef int LSDataType; typedef struct LinkStackNode { struct LinkStackNode* Next; LSDataType data; }LSNode; typedef struct { LSNode* phead; int size; }LinkStack;这里定义了两个结构体，对应了链表的"节点"和"栈的管理结构"，他们的作用是不一样的，可以把他们看作一个火车的车厢和火车头，其中LinkStack是用来控制链表的起点和长度，LSNode就是车厢的行李，他们就构成了一个栈。
初始化
// 初始化链式栈s void LinkStackInit(LinkStack* s) { assert(s); s->phead = NULL; s->size = 0; }初始化的对象是LinkStack，而不是LSNode，因为要先有火车头，LSNode等到入栈的时候才初始化，因为入栈才开始创造节点。
销毁
// 销毁链式栈s void LinkStackDestroy(LinkStack* s) { assert(s); LSNode* cur = s->phead; while (cur) { LSNode* nextNode = cur->Next; free(cur); cur = nextNode; } s->phead = NULL; s->size = 0; }入栈
void LinkStackPush(LinkStack* s, LSDataType x) { assert(s); LSNode* newNode = (LSNode*)malloc(sizeof(LSNode));//这里就要开始利用LSNode if (newNode == NULL) { perror("malloc fail"); return; } newNode->data = x; newNode->Next = s->phead; s->phead= newNode; s->size++; }出栈
// 出栈，并返回栈顶元素 LSDataType LinkStackPop(LinkStack* s) { assert(s); assert(s->size>0); LSDataType ret = s->phead->data; LSNode* nextNode = s->phead->Next; free(s->phead); s->phead= nextNode; s->size--; return ret; }获取栈顶元素
// 获取栈顶元素 LSDataType LinkStackTop(LinkStack* s) { assert(s); assert(s->size > 0); return s->phead->data; }获取栈中有效元素个数
int LinkStackSize(LinkStack* s) { assert(s); return s->size; }判空
bool LinkStackEmpty(LinkStack* s) { assert(s); return s->size == 0; }队列
基本概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
队列的存储结构
队列的链式存储，我们可以选⽤单链表结构，也可以选⽤双向链表结构。他们⼊队对应着在表尾插 ⼊，出队对应着在表头删除。当然我们完全没必要选择双向链表，因为单链表就可以⾼效实现，还 省空间⼀些。双向链表没有优势，每个结点还要多存储⼀个前驱指针，使⽤它纯粹浪费了。
typedef int QDataType; typedef struct QueueLinkNode { QDataType data; struct QueueLinkNode* Next; }QNode; typedef struct { QNode* Phead; QNode* Ptail; int size; }LinkQueue;//和上面所说是车厢，不过要多一个Ptail方便尾插这里和上面的链式的栈实现类似，定义两个结构体，一个是节点的结构一个是栈的管理结构，因为队列还要考虑队尾插入，队尾插入记录的时候方便直接找到最后一个。
初始化
void QueueInit(LinkQueue* q) { assert(q); q->Phead = q->Ptail = (QNode*)malloc(sizeof(QNode)); if (q->Phead == NULL) { perror("malloc fail"); return; } q->Phead->Next = NULL; q->size = 0; }这里选择带头结点的链表。
销毁
void QueueDestroy(LinkQueue* q) { assert(q); QNode* cur = q->Phead; while (cur) { QNode* nextNode = cur->Next; free(cur); cur = nextNode; } q->Phead = NULL; q->Ptail = NULL;//都要置为NULL q->size = 0; }判空
bool QueueEmpty(LinkQueue* q) { assert(q); return q->size == 0; }队列长
int QueueSize(LinkQueue* q) { assert(q); return q->size; }获取头的元素
QDataType QueueFront(LinkQueue* q) { assert(q); assert(q->size>0); return q->Phead->Next->data; }入队列
void EnQueue(LinkQueue* q, QDataType x) { assert(q); QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("malloc fail"); return; } newNode->data = x; newNode->Next = NULL; q->Ptail->Next = newNode; q->Ptail = newNode; q->size++; }出队列
QDataType DeQueue(LinkQueue* q) { assert(q); assert(q->size>0); QNode* delNode = q->Phead->Next; QDataType x = delNode->data; q->Phead->Next = delNode->Next; free(delNode); delNode =NULL; q->size--; if (q->size == 0) { q->Ptail = q->Phead; } return x; }这里有一个特殊的情况，删除最后一个节点的时候，Ptail和Phead都要置为NULL，避免野指针。
