W...Y的主页 😊
代码仓库分享 💕
目录
1.栈
1.1栈的概念及结构
1.2栈的结构特征图
编辑 1.3栈的实现
1.3.1栈的初始化
1.3.2进栈
1.3.3出栈
1.3.4销毁内存
1.3.5判断栈是否为空
1.3.5栈底元素的读取
1.3.6栈中大小
1.4栈实现所有接口
2.队列
2.1队列的概念
2.2队列的结构
2.3队列的实现
2.3.1队列的接口总览
2.3.2队列的初始化
2.3.3入队
2.3.4出队
2.3.5获取对头元素
2.3.6获取对尾元素
2.3.7判断是否为空
2.3.8队列销毁
3.拓展内容
在前几期的学习中，我们学习了顺序表与链表，今天我们将学习一种新的数据结构——栈与队列。而栈与队列实际上就是链表的一种变形产物，但肯定会有许多结构上的不同。
现在就让我们进入栈和队列，看看它们的特点！！！
1.栈
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的结构特征图
文字力量有时太过渺小，我们通过图解更清楚的了解栈的特点。
1.3栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
1.3.1栈的初始化
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}这里我们使用数组作为结构，更好的适用于栈的特征。但是这又与顺序表中的不同，顺序表在刚进入就进行了开辟空间，而我们栈的初始化先全部设为0。
1.3.2进栈
在进栈时，我们会遇到栈内存满的情况，所以我们必须进行判断(top 有效内容与 capacity容量是否相等)，如果相等我们就进行realloc进行扩容即可。然后将需要放入栈的内容存入堆区，有效内容top++即可完成。如果内容开始为0，我们使用三元表达式直接扩容为4。
void STPush(ST* ps, STDataType x)
{
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)
{
perror("realloc");
exit(-1);
}
ps->a[ps->top] = x;
ps->top++;
}
}注意：malloc与realloc都可以使用，当给予realloc一个指针时，功能完全相同。
1.3.3出栈
出栈非常简单，只需要将top--，不去访问其内容即可。
void STPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}1.3.4销毁内存
销毁堆上内存也非常简单，只需free掉即可
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}但是我们一定要用assert进行断言，防止传入空指针。
1.3.5判断栈是否为空
栈中是否插入内容，我们可以创建一个函数进行判断一下。返回值为bool类型，我们需要在头文件中加入#include<stdbool.h>才可以使用。
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}1.3.5栈底元素的读取
在读取栈底元素时，我们需要检查传入栈的指针是否正确以及栈中是否为空，两个必须都为真即可进行下面操作。
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}栈底元素就是top-1的内容，我们直接返回即可。
1.3.6栈中大小
当我们一直添加数据，需要了解栈中有多少个有效数据时，我们却束手无策，所以我们还需要一个能测出栈中大小函数。
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}1.4栈实现所有接口
我们需要了解的所有接口，可以放在头文件中：
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
STDataType _a[N];
int _top; // 栈顶
}Stack;
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
2.队列
2.1队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.2队列的结构
2.3队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数 组头上出数据，效率会比较低。
2.3.1队列的接口总览
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int QDataType;
typedef struct QueueNode
{
struct QueueNode* next;
QDataType data;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq, QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* pq);
在这里使用单链表，作为队列结构。队列特点就是先进先出，但是单链表比较适合头插头删，并不适合尾删，所以我们创建另一个结构体记录尾结点和头节点，这样也可以避免使用二级指针增加难度。
2.3.2队列的初始化
初始化我们先把所有内容设置成NULL或0即可
void QueueInit(Que* pq)
{
pq->head = pq->tail = NULL;
pq->size = 0;
}2.3.3入队
入队其实就是链表中的尾插！！！
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}我们一定要记得将记录首尾的结构体进行赋值，分情况进行，不要忘记更新哦！！！
2.3.4出队
出队就是链表中的头删
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
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--;
}我们一定要注意当删到只有一个内容节点时，要处理尾指针指向NULL。
2.3.5获取对头元素
只需要判断队列存指针正确且不为空，直接返回head指向的data即可。 QueueEmpty函数就是判断队列是否为空的函数，在后面有代码展示！！！
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return ps->head->data;
}2.3.6获取对尾元素
尾元素获取与首元素基本相同。
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return ps->tail->data;
}2.3.7判断是否为空
bool QueueEmpty(Que* pq)
{
assert(pq);
return ps->tail == NULL;
}2.3.8队列销毁
一定不要忘记创建的存放头尾节点的指针结构体，也要将它们置空
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = ps->tail = NULL;
pq->size = 0;
}3.拓展内容
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。 
栈、队列、顺序表、链表都是相似但不同的数据结构，我们在学习时一定要了解其中的差异，这样才能在以后更好的应用！！！文章来源：https://www.toymoban.com/news/detail-667740.html
以上就是本节全部内容，感谢大家耐心观看，你们的三连支持是博主最大创作动力。文章来源地址https://www.toymoban.com/news/detail-667740.html
到了这里，关于深入浅出带你玩转栈与队列——【数据结构】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
