进行插入和删除的一端称作栈顶，另一端称为栈底。栈中的元素遵循先进后出的原则。链表的特性是先进先出。插入操作就是对链表的尾插，删除操作就是链表的头删队列的C语言实现1：队列的结构定义队列使用单链表存储的，单链表的每个结点定义为QNode，然后使用两个指针front，rear指向QNode的头结点和尾节点2：初始化和销毁3：入队4：出队正常情况出栈很简单，但是要注意一个非常特殊的情况那
如果需要获取工程文件，优秀算法书籍，算法刷题攻略及算法刷题视频，请关注公众号【0与1】，并在后台回复【数据结构】
一：栈（1）栈的概念栈：栈是一种特殊的线性表，元素只能在一端插入和删除。进行插入和删除的一端称作栈顶，另一端称为栈底。栈中的元素遵循先进后出的原则。
（2）压栈与出栈压栈：栈的插入操作称为压栈，栈顶入数据出栈：栈的删除操作称为出栈，栈顶也出数据如下：栈顶固定，栈顶随元素插入和删除动态变化
上面的栈使用数组实现的，栈也可以用链表保存，如果是双向链表，哪一边作头或作尾都是可以的，但如果是单链表，为了操作的便利性，要注意方向
实现栈建议使用数组
（3）栈的C语言实现1：栈的结构定义和顺序表一样，栈也有静态和动态的，但是静态的不使用，所以使用动态栈
2：栈的初始化（注意修改一下ps->_top=-1）
3：增容4：进栈入栈时有一个放元素和移动指针的顺序问题，这一点要看你初始化时top的值是多少，如果初始化top=-1，那么就要先移动指针，再放元素。如果top=0，那么就要先放元素然后移动指针。
5：出栈6：清空栈7：取栈顶元素8：打印
（4）总结- 栈的先进后出规则是相对于栈中的元素而言的，并不是绝对的
- 栈经常用于有先进后出的需求场景中，如迷宫问题，括号匹配问题，表达式转换问题，还有递归转非递归等问题
Stack.h
#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef int SLDatatype;//typedef struct Stack//静态栈，实际中不使用//{//int top;//SLDatatype* _arr;//}Stack;typedef struct Stack{SLDatatype* _arr;int _top;//栈顶int _capacity;//容量}Stack;void StackInit(Stack* ps);//栈的初始化void StackDestory(Stack* ps);//销毁栈void StackAddCapacity(Stack* ps);//打印栈void StackPrint(Stack* ps);//打印栈void StackPush(Stack* ps,SLDatatype x);//进栈void StackPop(Stack* ps);//出栈int StackEmpty(Stack* ps);//清空栈（1表示成功）SLDatatype StackTop(Stack* ps);//获取栈顶元素123456789101112131415161718192021222324252627282930
//Stack.c
#include "stack.h"void StackInit(Stack* ps){assert(ps);ps->_arr = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);ps->_top = -1;ps->_capacity = 4;}void StackDestory(Stack* ps){assert(ps);free(ps->_arr);ps->_arr = NULL;ps->_top = -1;ps->_capacity = 0;}void StackPrint(Stack* ps){assert(ps);int k = ps->_top 1;while (k--){printf("%d ", ps->_arr[k]);}}void StackAddCapacity(Stack* ps){assert(ps);ps->_capacity *= 2;SLDatatype* temp = (SLDatatype)realloc(ps->_arr,sizeof(SLDatatype)*ps->_capacity);ps->_arr = temp;}void StackPush(Stack* ps,SLDatatype x){assert(ps);if (ps->_top == ps->_capacity-1)StackAddCapacity(ps);ps->_top;ps->_arr[ps->_top] = x;}void StackPop(Stack* ps){assert(ps);if (ps->_top == -1){printf("栈为空\n");exit(-1);}ps->_top--;}int StackEmpty(Stack* ps){assert(ps);if (ps->_top == -1){printf("栈已经清空\n");return 1;}return 0;}SLDatatype StackTop(Stack* ps){assert(ps);if (StackEmpty){printf("栈空\n");exit(-1);}return ps->_arr[ps->_top];}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
test.c
#include "stack.h"void test(){Stack stack;StackInit(&stack);StackPush(&stack, 1);StackPush(&stack, 2);StackPush(&stack, 3);StackPush(&stack, 4);StackPush(&stack, 5);StackPush(&stack, 5);StackPush(&stack, 5);StackPush(&stack, 5);StackPush(&stack, 5);StackPrint(&stack);//StackDestory(&stack);}int main(){test();}123456789101112131415161718192021222324
队列：是一种特殊的线性表，只允许在一端插入数据，在另一端删除数据。链表的特性是先进先出。进行插入操作的一端称之为队尾，进行删除操作的一端称之为队头。
（2）入队与出队入队：队列的插入操作，在队尾插入元素出队：队列的删除操作，在队尾删除元素
和栈一样，队列同样可以用数组和链表实现，但是如果使用数组实现队列，插入操作可以很好的实现，但是删除操作势必会移动元素，效率不高。所以使用单链表来实现链表，而且单链表的结构很好的满足了链表。插入操作就是对链表的尾插，删除操作就是链表的头删
（3）队列的C语言实现1：队列的结构定义队列使用单链表存储的，单链表的每个结点定义为QNode，然后使用两个指针front，rear指向QNode的头结点和尾节点
2：初始化和销毁3：入队4：出队正常情况出栈很简单，但是要注意一个非常特殊的情况那就是队列中只有一个结点，也即pq->front==pq->rear，此时要特殊处理，将front和rear都置为空（同时注意打印函数也要相应做处理），否则将发生NULL错误
5：取队头和队尾6：判断链表是否为空7：调用接口进行出队操作（4）总结- 队列常用于有先进先出的需求场景中，比如要保持序列公平（排队抽号机 ），生产消费者模， 广度优先遍历
头条号有字数限制，只能用图片代替，如需要代码，可移步 https://blog.csdn.net/qq_39183034/article/details/113179959
