【数据结构】--- 探索栈和队列的奥秘
关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა
💡个人主页：9ilk
💡专栏：数据结构之旅
上回我们学习了顺序表和链表，今天博主来讲解两个新的数据结构 — 栈和队列 ， 请放心食用
文章目录
- 🏠 栈
- 📒 何为栈
- 👿 栈后进先出是相对的
- 📒 栈的实现
- 🏠 队列
- 📒 何为队列
- 📒 队列的实现
🏠 栈
对于这么坨书，我们要拿到最下面的书是不是要最后才能拿到；而对于最上面的书它是最晚放上去的却能最先拿到，这样的一个场景就跟我们接下来要介绍的栈类似 — Last in First out(后进先出)
📒 何为栈
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈数据的插入操作叫做压栈/入栈/进栈，入数据在栈顶。
出栈：栈数据的删除操作叫做出栈，出数据也在栈顶。
👿 栈后进先出是相对的
由图中我们可知，栈的后进先出是对于同时在栈里的数据而言的
📒 栈的实现
通过前面的分析我们知道，我们需要一个栈顶来表示数据，这跟我们链表的头结点有点相似，但是对于单链表来说实现栈，尾部插入数据并不方便，因此我们选择数组实现栈
- 动态栈
typedef int Datatype; typedef struct Stack { Datatype* arr; int top; int capacity; }ST;- 栈的初始化与销毁
//初始化 void StackInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; }关于top的初始化：1.top表示栈顶元素的下一个位置时，让top初始化为0，插入数据时先top后++ ；2.top表示栈顶元素 时，top初始化为-1，此时先++后再用top
// 销毁栈 void StackDestroy(ST* ps) { assert(ps); free(ps->arr); ps->arr = NULL; ps->capacity = ps->top = 0; }- 栈的插入数据和删除数据
这里有了前面顺序表的基础就很简单了，不过要注意压栈和出栈都是在栈顶
//入栈 void StackPush(ST* ps, Datatype data) { assert(ps); if (ps->capacity == ps->top) {//扩容 int newcapacity = 0; newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype)); if (temp == NULL) { perror("malloc failed"); return; } ps->arr = temp; ps->capacity = newcapacity; } //入栈 ps->arr[ps->top++] = data; } //出栈 void StackPop(ST* ps) { assert(ps); //栈不能为空 assert(ps->top != 0); ps->top--; }- 获取栈顶元素
// 获取栈顶元素 Datatype StackTop(ST* ps) { assert(ps); //栈不能为空 assert(ps->top != 0); return ps->arr[ps->top - 1]; }- 判断是否为空
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(ST* ps) { assert(ps); return ps->top == 0 ? 1 : 0; }- 获取栈中有效数据个数
// 获取栈中有效元素个数 int StackSize(ST* ps) { assert(ps); return ps->top; }🏠 队列
栈是后进先出，那有我们的先进先出（First in First out）吗 ? 当然有，跟现实中我们排队买票一样，这样数据结构叫做队列
📒 何为队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
📒 队列的实现
由于我们是先进先出，出在队头出，进在队尾进，所以我们需要两个“指针”front 和 rear 来标识位置有效率些。
那用数组来实现好还是链表呢？
用数组的话不好出数据，所以我们这里推荐用链表实现；同时我们可以将front和rear封装进一个结构体这样比较省事
- 队列结构
typedef int Datatype; typedef struct QNode { Datatype data; struct QNode* next; }QNode; typedef struct Quque { QNode* head; QNode* tail; int size; }Quque;注：我们可以定义一个size表示数据个数，弥补链表需要循环遍历确定数据个数的缺陷
- 队列的初始化和销毁
//队列的初始化和摧毁 void QuqueInit(Quque* pq) { assert(pq); pq->size = 0; pq->head = pq->tail = NULL; } void QuqueDestroy(Quque* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->head = pq->tail = NULL; pq->size = 0; }- 入队和出队
出队就是链表的头删 入队就是尾插
//队列的入队列和出队列 void QuquePop(Quque* pq) { assert(pq); assert(pq->head != NULL);//对嘞不能为空 //0个结点 //1个结点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } pq->size--; } void QuquePush(Quque* pq, Datatype x) { assert(pq); //申请新结点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc failed"); return; } newnode->data = x; newnode->next = NULL; if (pq->head == NULL) {//0个结点 pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; }- 获取头元素和尾元素
//队列的头元素和尾巴元素 Datatype QuqueFront(Quque* pq) { assert(pq); assert(pq->head != NULL); return pq->head->data;//设置两个指针进结构体的好处 } Datatype QuqueBack(Quque* pq) { assert(pq); assert(pq->head != NULL); return pq->tail->data;//设置两个指针进结构体的好处 }- 队列是否为空
//队列是否为空 bool QuqueEmpty(Quque* pq) { assert(pq); if (pq->size == 0) { return true; } else { return false; } }- 队列有效数据个数
//队列数据个数 int QuqueSize(Quque* pq) { assert(pq); return pq->size; }本次分享到这就结束咯，下次我们将讲解链表，栈和队列的OJ题，敬请期待 ~
- 队列有效数据个数
- 队列是否为空
- 获取头元素和尾元素
- 入队和出队
- 队列的初始化和销毁
- 队列结构
- 获取栈中有效数据个数
- 判断是否为空
- 获取栈顶元素
- 栈的插入数据和删除数据
- 栈的初始化与销毁
- 动态栈
