目录
前言：
在学习C语言的时候我们可以了解到，局部变量是在栈中创建的，动态开辟的空间是在堆上开辟的，用了static关键字的变量是在静态区创建的，我们在学习数据结构的时候同样会涉及到栈和堆的概念，但是此栈非彼栈，堆也是，因为这是两门不同的学科。
局部变量在栈中创建等是隶属于操作系统的知识，而今天介绍的栈和队列，是隶属于数据结构的内容，他们是一种结构，比如栈，是后进先出的结构(Last in first out)，即LIFO，队列是相反的，是先进先出的结构(First in First out)，即FIFO。
现在就进入到数据结构中的栈和队列吧！
1 栈的概念和结构
栈，是一种后进先出的结构，存入数据读取数据都是在一端进行的，就像串肉一样，先串进去的，总是最后吃到。进行数据插入的数据和删除操作的一端叫做栈顶，另一端就是栈底。
栈分为动态栈和静态栈，是不是感觉和顺序表挺像的，顺序表的章节我们同样考虑了是动态顺序表还是静态顺序表的问题，这里一样，那么同理，静态栈实际生活中很少用到，所以我们实现的是动态栈。
压栈操作，就是栈的插入操作，比如插入数据，也可以叫做进栈/入栈
出栈操作，就是栈的删除操作，比如删除数据。
栈是基于数组或者链表实现的，那么我们是选择数组还是链表呢？
这里用数组实现或者是链表实现都可以的，链表实现的话压栈操作就是尾插，出栈操作就是尾删，
数组实现的话也不会涉及到数据移动，所以两种实现方式均可，那么我们这里采用数组实现，
2 栈的实现
需要的头文件有：stdio stdlib stdbool assert
实现的时候一般实现如下接口：
void StackInit(stack* ps);//初始化栈
void StackPush(stack* ps, DataType x);//入栈
void StackPop(stack* ps);//出栈
DataType StackTop(stack* ps);//获取栈顶元素
int StackSize(stack* ps);//获取栈的空间大小
bool StackEmpty(stack* ps);//判断栈是否为空
void StackDestroy(stack* ps);//销毁栈同样需要结构体，三个成员变量，一个用来开辟空间，一个用来计算容量，一个用来专门指向栈顶元素。
typedef int DataType;
typedef struct Stack
{
DataType* arr;
int top;//栈顶
int capacity;//容量
}stack;初始化：
初始化同顺序表一样，赋值即可
void StackInit(stack* ps)//初始化栈
{
assert(ps);
ps->arr = NULL;
ps->capacity = ps->top = 0;
}销毁：
销毁需要释放空间，所以差别和初始化不太大
void StackDestroy(stack* ps)//销毁栈
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->capacity = ps->capacity = 0;
}
入栈操作：
入栈之前，因为是初始化了，所以capacity size都是0，并且在后面入栈的时候都应该判断一下是否需要扩容，所以这里的写法和顺序表那里是很像的，但是这里没有必要单独写一个类似于获取结点的函数，因为只有入栈会用到开辟空间
void StackPush(stack* ps, DataType x)//入栈
{
assert(ps);
if (ps->capacity == ps->top)
{
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
DataType* tem = (DataType*)realloc(ps->arr, sizeof(newcapacity));
assert(tem);
ps->arr = tem;
ps->capacity = newcapacity;
}
ps->arr[ps->top++] = x;
}
这里唯一稍微麻烦一点的就是扩容的操作，如果栈顶和容量一样了就扩容，扩容我们可以使用三目操作符，随即进行赋值就行了，入栈之后top自增一下，整个入栈操作就完成了。
判断栈是否为空：
判断栈是否为空靠的是top的数值，如果top为0那么栈就是空，返回false就行
bool StackEmpty(stack* ps)//判断栈是否为空
{
assert(ps);
return ps->top == 0;
}如果top为0，返回的是true，即为空
出栈操作：
出栈同顺序表，top自减一下就行了，访问不到=数据删除，但是出栈操作需要栈不为空，那么函数StackEmpty就有用了
void StackPop(stack* ps)//出栈
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}返回栈顶元素：
判断一下，返回值，完成了，因为我们使用的是数组，下标访问，那么top就应该减一个1才能得到我们想要的元素，并且返回栈顶元素需要栈有值才行
DataType StackTop(stack* ps)//获取栈顶元素
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top-1];
}返回栈的大小：
判断一下，返回就ok了
int StackSize(stack* ps)//获取栈的空间大小
{
assert(ps);
return ps->capacity;
}以上就是栈的功能实现
Tips 出栈操作和入栈操作顺序不对的话，可能影响你的预期结构哦
3 队列的概念和结构
队列，就像是排队一样，和栈是完全相反的一种结果，栈是出数据和进数据都是在一端，队列不一样，队列是一端进数据，另一端出数据，所以队列是First in first out ，即FIFO
那么我们用什么来实现队列呢？数组还是链表？
假如我们使用数组的话，每次出队的时候就会涉及到移动数据，这个弊端有点类似于顺序表，一旦数据多了起来的话，那么时间浪费是比较严重的，降低了程序运行效率，所以实现队列我们使用链表来实现。
那么我们使用单链表还是双向链表呢？
其实我们在使用链表的时候，能使用单链表就使用单链表，双向链表固然方便，但是双向链表使用在这里犹如杀鸡用牛刀，使用双向链表的时候我们要单独加一个指针进去，会降低空间利用，而且队列使用单链表实现足矣，没必要为一点点的时间去使用双向链表。
我们使用单链表实现队列的时候，先进先出，所以入队的时候就是一直尾插即可，出队的时候就是一直头删就行，那么结构体我们怎么定义呢？
基于单链表实现，所以结点的定义是和单链表定义是一样的。
typedef int DataType;
typedef struct QNode//对结点定义
{
DataType val;
struct QNode* next;
}QNode;一个值和一个指向下一个结点的地址。
那么实现队列涉及队头队尾，所以对尾结点就比较需要，那我们指定不能每写一个函数就用循环找一下尾结点吧？所以这里我们再定义一个结构体，里面的成员变量是头结点，尾结点，队列大小。
typedef struct QueueNode//对队列定义
{
QNode* phead;
QNode* ptail;
int size;
}Queue;单独用一个结构体存储队列的头尾变量实现起来会方便很多。
那么实现队列的基本接口如下：
void QueueInit(Queue* pq);//初始化队列
void QueuePush(Queue* pq,DataType x);//入队
void QueuePop(Queue* pq);//出队
DataType QueueHead(Queue* pq);//获取队头元素
DataType QueueBack(Queue* pq);//获取队尾元素
bool QueueEmpty(Queue* pq);//判断队列是否为空
int QueueSize(Queue* pq);//获取队列中的有效元素个数
void QueueDestroy(Queue* pq);//销毁队列
4 队列的实现
队列的初始化：
初始化即把指针置为空，防止变为野指针，存储的变量一般置为0：
void QueueInit(Queue* pq)//初始化队列
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}队列的销毁：
我们是对每个结点进行销毁，while循环是必要的，释放完指针置为空，变量置为0即可
void QueueDestroy(Queue* pq)//销毁队列
{
assert(pq);
QNode* pcur = pq->phead;
while (pcur)
{
QNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
pq->size = 0;
}判断队列是否为空：
判断队列是否为空很多种方法，一是直接用size进行判断，即是( 1 == pq->size)，或者判断phead是否为空，ptail判断为空也可以，最后返回的是布尔类型：
bool QueueEmpty(Queue* pq)//判断队列是否为空
{
assert(pq);
return pq->size == 0;
}入队：
入队的时候不用考虑空间是否足够，每入队一个元素就开辟一个空间，不存在空间浪费的问题，入队是在队尾入队，即一直尾插即可，但是有个特殊情况需要考虑一下，就是队列是否为空，如果队列为空，那么头结点和尾结点都置为新节点就行，记得size自增一下：
void QueuePush(Queue* pq,DataType x)//入队
{
//判断队列是否为空
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->val = x;
newnode->next = NULL;
//队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
//队列不为空
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}出队：
出队就是头删，队头的元素出去，那么头结点就网下一个结点后移，出队之前也要判断队列是否为空，除了队列为空的情况，队列中只有一个元素的情况下，出队之后我们就要关心两个元素，一个是头结点，一个是尾节点，一个元素出队，头尾结点都要置为空，并且出队指针都要free出队的结点，最后size自减一下就完成了。
void QueuePop(Queue* pq)//出队
{
assert(pq);
assert(!QueueEmpty(pq));
//一个结点
if (1 == pq->size)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
//多个结点
else
{
QNode* newphead = pq->phead->next;
free(pq->phead);
pq->phead = newphead;
}
pq->size--;
}获取队头/尾元素以及队列的大小：
获取元素和队列大小是最简单的，都是判断一下队列是不是为空，返回对应的值就行了。
队头：
DataType QueueHead(Queue* pq)//获取队头元素
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->val;
}队尾：
DataType QueueBack(Queue* pq)//获取队尾元素
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->val;
}队列大小：
int QueueSize(Queue* pq)//获取队列中的有效元素个数
{
assert(pq);
return pq->size;
}以上就是栈和队列的基本实现。
感谢阅读！
