谁都不能阻挡你成为更优秀的人。
1. 栈的表示和实现
1.1. 栈的概念及结构
栈 ：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除 操作的一端称为栈顶，另一端称为栈底。 栈中的数据元素遵守后进先出 LIFO （ Last In First Out ） 的原则。
压栈 ：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶 。
出栈 ：栈的删除操作叫做出栈。 出数据也在栈顶 。
1.2. 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小(O(1)),而链表是O(N)。
1.3. 效果展示图
注意：栈和队列是没有打印函数的，只能像图中这样，判断是否为空，然后取栈顶数据（取栈顶数据是不用减数据个数的），再出一个数据（在这里才减数据个数）。
1.3.01 栈要实现的接口
1.4. 栈的源代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" #include"Queue.h" void testStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); //要注意 没有打印这个函数，不像前面的一样 //栈是只能栈顶入和出,所以只能这样写 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDistory(&st); } void testQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 3); QueuePush(&q, 4); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 5); while (!QueueEmpty(&q)) { printf("%d ",QueueFront(&q)); QueuePop(&q); } QueueDestory(&q); } int main() { testStack(); //testQueue(); return 0; }
Stack.h
#pragma once #include<stdio.h> #include<malloc.h> #include<stdbool.h> #include<assert.h> #include<stdlib.h> typedef int STDateType; typedef struct Stack { //动态数组存数据 STDateType* a; //目前数据个数 int top; //总容量 int capacity; }ST; //进栈 出栈 初始化 销毁 取栈顶数据 多少个数据 判断 //初始化 void StackInit(ST* ps); //销毁 void StackDistory(ST* ps); //入栈 void StackPush(ST* ps, STDateType x); //出栈 void StackPop(ST* ps); //取栈顶数据 STDateType StackTop(ST* ps); //求多少个数据 int StackSize(ST* ps); //求是不是为空 bool StackEmpty(ST* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" //初始化 void StackInit(ST* ps) { assert(ps); ps->a = (STDateType*)malloc(sizeof(STDateType)*4); ps->capacity = 4; //这里是初始化的0,也就是说永远指向栈顶的下一个位置 ps->top = 0; } //销毁 void StackDistory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = ps->top = 0; } //入栈 void StackPush(ST* ps, STDateType x) { assert(ps); //满了增容 if (ps->capacity == ps->top) { STDateType* newa = (STDateType*)realloc( ps->a, sizeof(STDateType) * ps->capacity * 2); if (newa == NULL) { printf("realloc fail\n"); exit(-1); } else { ps->capacity *= 2; ps->a = newa; } } ps->a[ps->top] = x; ps->top++; } //出栈 void StackPop(ST* ps) { assert(ps); //栈空了调用直接报错 assert(ps->top > 0); ps->top--; } //取栈顶数据 STDateType StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top-1]; } //求多少个数据 int StackSize(ST* ps) { assert(ps); return ps->top; } //求是不是为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top==0; }
2. 队列的表示和实现
2.1 队列的概念及结构
队列 ： 只 允许在 一端 进行 插入 数据操作，在 另一端 进行 删除 数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为 队尾 出队列：进行删除操作的一端称为队头。
2.2 队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
2.4. 队列的效果示意图
2.6. 队列源代码
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Stack.h" #include"Queue.h" void testStack() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); //要注意 没有打印这个函数，不像前面的一样 //栈是只能栈顶入和出,所以只能这样写 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDistory(&st); } void testQueue() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 3); QueuePush(&q, 4); printf("%d ", QueueFront(&q)); QueuePop(&q); QueuePush(&q, 5); while (!QueueEmpty(&q)) { printf("%d ",QueueFront(&q)); QueuePop(&q); } QueueDestory(&q); } int main() { //testStack(); testQueue(); return 0; }
Queue.c
#pragma once #include<stdio.h> #include<stdbool.h> #include<assert.h> #include<malloc.h> #include<stdlib.h> typedef int QDateType; typedef struct QueueNode { struct QueueNode* next; QDateType date; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue; //初始化 void QueueInit(Queue* pq); //销毁 void QueueDestory(Queue* pq); //插入 void QueuePush(Queue* pq, QDateType x); //删除 void QueuePop(Queue* pq); //得到头部数据 QDateType QueueFront(Queue* pq); //得到尾部数据 QDateType QueueBack(Queue* pq); //得到大小 int QueueSize(Queue* ps); //判空 bool QueueEmpty(Queue* pq);
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } //销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; } //插入 void QueuePush(Queue* pq, QDateType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->date = x; newnode->next = NULL; if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } if (pq->head == NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } } //删除 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); //1个数据 //多个 if (pq->head->next == NULL) { //一个数据如果不分情况 //free后tail是野指针再插入就会有问题 free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } } //得到头部数据 QDateType QueueFront(Queue* pq) { assert(pq->head); return pq->head->date; } //得到尾部数据 QDateType QueueBack(Queue* pq) { assert(pq->head); return pq->tail->date; } //得到大小 int QueueSize(Queue* pq) { assert(pq->head); int sz = 0; QNode* cur=pq->head; while (cur) { sz++; cur = cur->next; } return sz; } //判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
总结
栈和队列其实相对于我们之前实现的单，双链表是更简单的，又或者说也就是之前的简单版，只是要注意打印是不同的，这是我们要根据他们的性质来写。当然，每写一个函数我们还是要注意各种特殊情况，一个数据，没有数据等。再最后提供一个小方法，再代码报错又不知道在哪里的时候，我们可以用一个test函数去把自己写的接口一个一个去测，然后调试。当然作者更喜欢在这之前用另一个，因为这样调试有点慢，就是直接去看之前写的接口的逻辑，跟着思路看每个接口的代码，这样会更简单更快，同时写代码或者调试的时候都可以画图来看，这是我们刚开数据结构的时候就提醒过大家的哈。
今天的内容就到这里了哈！！！
要是认为作者有一点帮助你的话！
就来一个点赞加关注吧！！！当然订阅是更是求之不得！
赠人玫瑰，手有余香=。=！
最后的最后感谢大家的观看！！！
你们的支持是作者写作的最大动力！！！
下期见哈！！！
