🌸栈
🌼栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈，出数据也在栈顶。
🌸一.栈的的实现
🛫准备工作
为了简明扼要的分清楚栈和队列的作用，各部分代码分在以下三个不同的项中👇🏻
Queue.h ---------➡️函数功能的说明
Queue.c ---------➡️函数功能的实现
test.c ---------➡️调用函数功能
我们用数组还是链表去实现栈呢？
答案是都可以，但是用数组是更好的
插入数据，基本上只有尾插尾删，而顺序表的尾插尾删效率很高
唯一的缺点：扩容
那么问题又来了：数组是定义静态的还是动态的呢？
答案肯定是：动态 静态的还要定义数组的大小什么的，麻烦！
//静态 #define N 10 typedef int STDataType; typedef struct Stack { STDataType a[N]; int top; }ST; //动态 typedef int STDataType; typedef struct Stack { STDataType *a; int top;//栈顶 int capacity;//容量 }ST;
🌼1.栈的初始化
➡️思路实现： 把栈的栈顶、容量等全部置为0，栈的指针置NULL
这个简单，就不多说了上代码
💫代码实现：
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
❗特别注意：这里我们设置的top为0，所以top是栈顶元素的下一个
🌼2.入栈
➡️思路实现： 从栈尾插入一个元素，要注意判断空间是否足够
❗注意事项：
注意空间大小的问题：空间不够就扩容
✨动图解析：
💫代码实现：
// 入栈 void StackPush(ST* ps, STDataType data) { assert(ps); if (ps->top == ps->capacity) { //满了就扩容 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newCapacity; } ps->a[ps->top] = data; ps->top++; }
🌼3.出栈
➡️思路实现： 即删除栈顶元素，把top - -
✨动图解析：
💫代码实现：
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//防止堆顶为空 ps->top--; }
🌼4.获取栈顶元素
➡️思路实现： top是栈顶，那么top-1就是栈顶元素
❗注意事项：
要注意判断栈是否为空
ps是指向栈结构的指针，结构里有数组a和栈顶的下标top，top不是已有栈顶元素的下标，而是待入栈的一个位置，所以栈顶的下标是top-1，数组名加下标获取数组元素
💫代码实现：
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps));//防止栈顶为空 return ps->a[ps->top-1]; }
🌼5.判断栈是否为空
➡️思路实现： 判断top等不等于0，等于0就是就空，不等则相反
❗注意事项：
除了常规的if else判断，还有一种较为简单的方法，看下面
💫代码实现：
int StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
🌼6.获取栈中元素个数
❗注意事项：
top就是size，再数组里top是最后元素的下一个，也是元素的个数，从数组下标的角度看
💫代码实现：
int StackSize(ST* ps) { assert(ps); return ps->top;//top就是size个数，看下标 }
🌼7.销毁栈
没啥说的直接上代码
💫代码实现：
// 销毁栈 void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
🌸队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
🌸二.队列的实现
🛫准备工作
同理，为了简明扼要的分清楚队列的作用，各部分代码分在以下三个不同的项中：Queue.h
Queue.c test.c
这里部分比较帅的读者会问：我们还是用数组去实现队列？
答案：链表，队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，出队列只能覆盖数据，效率会比较低。
这里我们要使用带头双向链表吗？
答案：小题大做了，带头双向循环链表的优势是在任意位置上插入删除，我们队列只在队尾插入、队头删除，所以可以定义head、tail两个指针
// 链式结构：表示队列 typedef int QDataType; typedef struct SListNode { QDataType data; struct SListNode* next; }QNode; // 队列的结构 typedef struct Queue { QNode* head; QNode* tail; }Queue;
🌼1.初始化队列
➡️思路实现：把head、tail指针置为空
💫代码实现：
// 初始化队列 void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL;//不带哨兵位，哨兵位意义不大 }
🌼2.队尾入队列
➡️思路实现： 从队尾插入数据，要注意极端情况
❗注意事项： （两种情况）
当队列为空时，一个数据都没有，这时候的head和tail都是指向NULL;
队列不为空的时候，入队列一个一个 的插入
✨动图解析：
情况2：
💫代码实现：
// 队尾入队列 void QueuePush(Queue* q, QDataType data) { assert(q); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc failed\n"); exit(-1); } newnode->data = data; newnode->next = NULL; if (q->tail == NULL) { q->head = q->tail = newnode; } else { q->tail->next = newnode; q->tail = newnode; } }
🌼3.队头出队列
➡️思路实现： 从队头出数据，相当于头删，也有极端情况
❗注意事项：
保存head的下一个next，释放head，然后next赋值给head
极端情况：当只剩下一个节点了，如下图的tail就变成野指针了
✨动图解析：
极端情况：
💫代码实现：
// 队头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(&q)); //1.一个节点 //2.多个节点 if (q->head->next == NULL) { free(q->head); q->head = q->tail = NULL;//避免野指针 } else { QNode* next = q->head->next; free(q->head); q->head = next; } }
🌼4.获取队列头部元素
这个很简单，先判空，然后直接取就行
💫代码实现：
QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(&q)); return q->head->data; }
🌼5.获取队列队尾元素
同理，取队尾数据
💫代码实现：
QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(&q)); return q->tail->data; }
🌼6.检测队列是否为空
❗注意事项： 按理来说，head和tail为空，都是一起为空的，所以任选一个
💫代码实现：
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 int QueueEmpty(Queue* q) { assert(q); return q->head == NULL; }
🌼7.获取队列中有效元素个数
❗注意事项：
高效的方法：可以在队列里定义一个Size，插入数据的时候++，删除数据的时候--
不在乎效率的方法：现场计数，遍历一遍链表，算出元素个数
💫代码实现：
// 获取队列中有效元素个数 int QueueSize(Queue* q) { assert(q); QNode* cur = q->head; int Size = 0; while (cur) { Size++; cur = cur->next; } return Size; }
🌼8.销毁队列
❗注意事项：
同样也是遍历链表，先定义一个next，为cur的下一个，防止找不到下一个，遍历完把head、tail都置空
💫代码实现：
void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->head = q->tail = NULL; }
🌸三.栈和队列的区别
void TestQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); } void TestQueue2() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); printf("%d ", QueueFront(&q)); QueuePop(&q); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); while (!QueueEmpty(&q)) { printf("%d ", QueueFront(&q)); QueuePop(&q); } printf("\n"); }
可以知道，在队列里，无论我们以什么方法去出队列，输出的结果都不会变。简单来说：只要入的顺序是12345，不管咋样出，运行结果永远是12345，这才符合先进先出
🌼队列的应用
排队，保持决定的公平性
广度优先遍历
举个例子：
栈是死胡同，队列是活胡同
队列就好像是医院的排队：先到的先拿号，先看病。
栈 就好比一排车开进了死胡同，那是不是只能后来进的车先出去
📢写在最后
能看到这里的都是棒棒哒🙌！
如果认真看完以上部分，肯定有所收获。
接下来我还会继续写关于📚《排序算法》等…
💯如有错误可以尽管指出💯
🥇想学吗？我教你啊🥇
🎉🎉觉得博主写的还不错的可以一键三连撒🎉🎉
