1，栈
1.1栈的概念及结构
栈是一种特殊的线性表，只允许在固定的一段进行插入和删除元素操作，这就很类似于我们生活中的羽毛球桶，进行数据插入和删除操作的一端叫栈顶，另一端叫栈底。栈中的元素遵守先进后出，后进先出的原则。
压栈：栈的插入
出栈，栈的删除，这两部操作都在栈顶。
静态栈可以用数组来实现，相对狭义，在实际中我们常用动态栈，本文主要写动态栈。但是是用数组来实现栈的，所以本文的TOP为int类型，指向下标。
以下代码中 typedef int STDataType
1.2栈的结构体
typedef struct Stack{
STDataType *a;
int top;
int capacity;
}ST;
1.3栈的初始化函数
注意top为数组下标，这里top为-1时候，之后入栈才能保证top指向正确。即top指向栈顶元素；
void STinit(ST* pst){
assert(pst);
pst->a=NULL;
pst->top=-1;
pst->capacity=0;
}
1.4栈的销毁
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a=NULL;
pst->top=pst->capacity=0;
}
1.5栈的判空函数
bool STEmpty(ST* pst)
{
assert(pst);
if(pst->top==-1)
return ture;
else
return false;
}
1.6栈的入栈函数
void Push(ST* pst,STDataType x)
{
assert(pst);
if(pst->top==pst->capacity)//扩容
{
int newcapacity=pst->capacity== 0? 4 : pst->capacity*2;//因为初始空间可能为0
STDataType* tmp =(STDataType*)realloc(pst->a,newcapacity * sizeof(STDataType));
if(tmp==NULL)
{
perror("realloc fail");
return;
}
pst->a=tmp;
pst->capacity=newcapacity;
pst->a[pst->top++]=x;
}
1.7栈的出栈函数
只移动下标，这样就访问不到；下一个下标处存在元素不影响栈的容量和其余的操作哦
void Pop(ST* pst)
{
assert(pst);
pst->top--;
}
1.8取栈顶元素函数
STDataType Top(ST* pst)
{
assert(pst);
return pst->a[pst->top];
}
1.9获取栈中元素个数
int STSize(ST* pst){
assert(pst);
return (pst->top)+1;
}
1.10遍历栈的方法
void Print(ST* pst)
{
while(!STEmpty(&s))
{
printf("%d",Top(&s));
Pop(&s);
}
STDestroy(&s);
}
1.11栈的小结
入栈和出栈顺序是一对N的关系。
栈遵循先进先出的原则。即 将栈顶新加入的数据比原先的更先出栈。
此外，做题也能让自己对栈的理解更深刻，以下是我在力扣做过的题，大家可以去做一做。
2，队列
2.1队列的概念和结构：
队列有队头和队尾，在队头处去除元素，在队尾处加入新元素。
队列可以用来保持公平，在生活中理解可以使我们更深刻。比如商场中的抽号，排队小程序等，在过程中，按下按钮后，会显示前面有几个人，后面的人继续排队时，会在队尾处+1，而前面的人刷完自己的号后，后面的人排队号就会-1。队尾的号减去队头的号即为中间有几个人。
2.2队列的结构体
此处的队列实现使用链表较好，可以是单链表，也可以是双链表，因为队列是连续的，在两端进行修改。单链表的第一个有效节点可以记录为队头.
用链表来实现队列，那么就有一个问题，就是如果我们把节点作为形参的时候，
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
2.3入队函数
队尾插入
void QueuePush(Queue*pq,QDataType x)
{
assert(pq);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if(!newNode)
{
printf("malloc fail!");
}
newNode->val=x;
newNode->next=NULL;
if(pq->tail==NULL)
{
pq->phead=pq->ptail=newNode;
}else{
pq->ptail->next=newNode;
pq->ptail=newNode;
}
pq->size++;
return;
}
2.4出队函数
队头出队
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->size);
if(pq->phead->next==NULL)
{
free(pq->phead);
pq->phead=pq->ptail=NULL;
}else{
pq->phead=pq->phead->next;
free(pq->phead);
pq->size--;}
return;
}
2.5队列初始化函数
void QueueInit(Queue *pq)
{
assert(pq);
pq->phead=NULL:
pa->ptail=NULL;
pa->size=0;
}
2.6取队列的队尾元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->phead);
return pq->phead->val;
}
2.7取队列的队头元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->ptail);
return pq->ptail->val;
}
2.8队列的判空函数
bool QueueEmpty(Queue *pq)
{
assert(pq);
if(pq->size==0)
return true;
else
return false;
}
2.9队列的元素个数
QDataType QueueNum(Queue *pq)
{
assert(pq);
return pq->size;
}
2.10队列的销毁函数
void QueueDestroy(Queue *pq)
{
assert(pq);
QNode*cur=pq->phead;
while(cur)
{
QNode* next=cur->next;
free(cur);
cur=next;
}
pq->ptail=pq->phead=NULL;
pq->size=0;
}
2.11队列的遍历函数
void QueuePrint(Queue* pq)
{
assert(pq);
while(!QueueEmpty(pq))
{
printf("%d ",QueueFront(pq));
QueuePop(pq);
}
printf("\n");
return;
}
经典例题
这两题应用范围基本没有，但可以让我们更好的理解栈和队列。