【数据结构】栈和队列详解

前言：前两篇文章我们从顺序表讲到链表，着重讲了顺序表链表的概念以及实现，这期我们将进入栈和队列的学习。

一，栈

1，栈的概念

栈：⼀种特殊的线性表，其只允许在固定的⼀端进行插入和删除元素操作。进⾏数据插⼊和删除操作 的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

先来看看栈的第一个操作：压栈/进栈/日入栈 即栈插入数据的操作，数据在栈顶。

接着看第二个操作：出栈 即栈删除元素的操作 删除的是栈顶的数据。

从上面的两个操作我们就可以发现一个规律，就是先入的数据后出去，后面进来的数据先出去 即先进后出的规则。

在初阶数据结构中，每个数据结构都会有他的底层实现要么是链表、要么是数组、要么是其他，那么栈的底层用什么来实现呢？

2，栈的底层使用什么来实现？

我们目前只学习了链表和顺序表，不妨假设一下使用链表的顺序表来实现看看他们有什么优劣之分。

第一种假设底层使用的是链表：

使用链表来实现可以看到入栈和出栈的时间复杂度均为O(1)，那是否就是使用链表作为底层的实现呢？我们再来看看使用数组的情况再做定论。

第二种 假设底层使用数组：

我们可以看到底层使用数组的情况下入栈和出栈的时间复杂度也均为O(1)，既然时间复杂度比较不出来我们就来比空间复杂度：

首先：在存储相同数量元素时，链表每个结点需要额外存储指针信息，且动态分配可能产生内存碎片。数组扩容虽然需要整体搬迁，但内存连续性更好。
其次：对于小规模数据，链表结点的固定开销（如2个指针）可能显著增加存储负担；存储大型对象时，指针开销占比会相对降低。同时需考虑不同语言的内存管理机制对实际空间利用率的影响。

通过上面的分析比较以后还是数组作为底层比较合适，接下来我们就使用数组来实现链表。

3，栈的实现

要实现栈的各种功能我们就要先定义一个栈：

//定义一个栈  底层使用数组实现
typedef int STDataType;
typedef struct stack
{STDataType* arr;int top;//栈顶 也是有效的数据个数int capacity;//栈的容量
}ST;

定义好后就将他初始化：

//初始化
void StackInit(ST* ps);

//初始化
void StackInit(ST* ps)
{assert(ps);ps->arr = NULL;//一开始指针先初始化为NULL空指针ps->top = ps->capacity = 0;
}

定义好栈后接下来我们就可以来实现栈的方法了：

1，入栈

//入栈---栈顶
void StackPush(ST* ps, STDataType x);

//入栈——栈顶
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top)//有效数据等于容量大小时 说明栈满了{//增容STDataType newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//前面那个4是默认给的大小STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * (sizeof(STDataType)));if (tmp == NULL){perror("realloc fail!");exit(1);}//到这说明开辟成功了//更新容量和地址ps->arr = tmp;//将新开辟空间的地址给arrps->capacity = newcapacity;}ps->arr[ps->top++] = x;
}

2，出栈

出栈之前我们去判断栈是否为空，栈为空我们才去出数据不然没有意义：

//栈是否为空
bool StackEmpty(ST* ps);

//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top==0;//返回栈顶就知道是否为空了}

判断完后确定栈不为空我们就删除栈里面的元素：

//出栈——栈顶
void StackPop(ST* ps);

//出栈——栈顶 相当于删除元素
void StackPop(ST* ps)
{assert(ps);//判断是否为空if (!StackEmpty(ps)){//跟顺序表一样减少有效数据个数(栈顶)即可--ps->top;}
}

3，取栈顶元素

//取栈顶元素
STDataType StackTop(ST* ps);

//取栈顶元素
STDataType StackTop(ST* ps)//返回值是元素的类型
{//判断是否为空assert(!StackEmpty(ps));//每次取完 有效数据个数减减 栈顶减减return ps->arr[ps->top-1];//下标减一才能取得对应的元素
}

4，获取栈中有效元素个数

在我们定义的栈这个结构体中size就是专门用来记录有效数据个数的直接将他返回就可以了。

//获取栈中有效元素个数
int StackSize(ST* ps);

//获取栈中有效元素个数
int StackSize(ST* ps)
{return ps->top;//有效的元素个数 即栈顶
}

5，栈的销毁

由于我们在给数组扩容的时候是在堆区向操作系统申请的空间，所以如果不使用就即使的将他销毁避免空间的浪费。

//销毁
void StackDestroy(ST* ps);

//销毁
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

以上就是栈的实现了，是不是感觉很简单。因为栈的底层使用的是数组不是链表，不会设计指针相关的操作也不用维护指针所以相对比较简单。接下来我们继续学下一个数据结构——队列。

二，队列

1，队列的概念

概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先 出FIFO(First In First Out)
队列也是一个线性表，从逻辑结构上看它是线性的，但在物理结构上看不一定是线性的。
队列也有两种重要的操作：

1. 入队列：进行插入操作的⼀端称为队尾。
2. 出队列：进⾏删除操作的⼀端称为队头。
   
   所以总结队列的特点就是先进先出，后进后出。

接下来就是选底层的问题了，队列的底层是否还是使用数组呢？我们紧接着来分析：

2，对列的底层是什么？

我们继续假设两种方法，然后再比较优劣得出结果。

第一种假设 使用数组来实现：

第二种假设 使用链表来实现：

相比之下还是使用链表作为队列的底层更好，使用链表的的时间复杂度更小效率更高。

不使用数组是因为 数组不具备链式结构(动态内存)的优势即： 动态扩容：无需预先分配固定空间。
避免移动数据：数组实现出队时需要移动元素，链式只需修改指针。

3，队列的实现

与栈的实现一样，我们要实现队列的各种方法就要先定义出一个队列：

//定义结点的结构
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QueueNode;

//定义队列 实际上就是定义两个指针 头指针 尾指针
typedef struct Queue
{QueueNode* phead;                    //两个指针指向头结点和尾结点QueueNode* ptail;//int size;
}Queue;

队列的定义稍微有些复杂，只要知道一个指针就是一个结点就好了，队列就是操控两个指针即头指针phead和尾指针ptail，头指针和尾指针都分别为一个结点。

为什么要这样设计呢？

1， 队列结构 Queue 包含两个关键指针：
phead：指向队列的第一个结点（队头），用于出队操作。
ptail：指向队列的最后一个结点（队尾），用于入队操作。

2， 避免遍历： 如果没有 ptail，每次入队都需要从 phead 遍历到尾部，时间复杂度为 O(n)。保留 ptail
显著提升性能。这就是解决我们前面提到的将O(N)变为O(1)的方法。

//初始化
void QueueInit(Queue* pq);

//初始化
void QueueInit(Queue* pq)
{assert(pq);//给队列中的两个指针都初始化为空pq->phead = pq->ptail = NULL;
}

定义好了队列接着我们就可以来实现它了：

1，入队列

在插入数据与删除数据时我们会去判断队列是否为空，所以直接封装成一个函数：

//队列判空
bool QueueEmpty(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == pq->ptail;}

入队列：

//入队——队尾  再尾部插入数据
void QueuePush(Queue* pq, QDataType x)

//入队——队尾  再尾部插入数据
void QueuePush(Queue* pq, QDataType x)
{assert(pq);//要插入数据就要开辟一个结点大小的空间 因为队列底层是用单链表实现 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}//到这说明空间开辟成功//给新节点初始化newnode->data = x;newnode->next = NULL;//如果链表空间为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else//空间不为空{pq->ptail->next = newnode;pq->ptail = newnode;//或pq->ptail=pq->ptail->next}//pq->size++;}

2，出队列

//出队——队头
void QueuePop(Queue* pq);

//出队——队头
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//单个结点的情况if (pq->phead = pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多个结点的情况{QueueNode* next = pq->phead->next;//这里创建next指针要用QueueNode来创建 因为使用的是结点free(pq->phead);pq->phead = next;}//pq->size--;
}

3，取队头队尾数据

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq)

//取队头数据
QDataType QueueFront(Queue* pq)
{//判空assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{//判空assert(!QueueEmpty(pq));return pq->ptail->data;
}

由于我们定义了两个指针始终都指向头和尾，所以只需要返回头和尾的数据就行。在取队头队尾数据之前记得判空！

4，队列有效数据个数

//队列有效元素个数
int QueueSize(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq)
{assert(pq);//方法一：遍历链表——适用于不会频繁调用队列有效数据个数的场景QueueNode* pcur = pq->phead;int size = 0;while (pcur != NULL){size++;pcur = pcur->next;}return size;//方法二：初始时创建一个记录有效数据的变量——适用于频繁调用队列有效数据个数的场景//return pq->size;
}

个人觉得还是使用第二种方法更好，在刚开始创建队列时就定义一个size来记录有效数据个数，每当有数据入队列就++，出队列就- - 。需要时就可以直接返回size即有效数据个数。

5，队列的销毁

//销毁队列
void QueueDestroy(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq)
{assert(pq);//队列底层是链表 链表的销毁要循环销毁QueueNode* pcur = pq->phead;while (pcur != NULL){QueueNode* next = pcur->next;free(pcur);pcur = next;}//走到这所有的结点都已经被释放了 此时队列的两个指针要置空pq->phead = pq->ptail = NULL;//将队列有效数据个数归零//pq->size = 0;
}

以上就是队列的所有实现了！队列的定义可能比栈稍微复杂一丢丢，但只要仔细理解其实就会发现也就那么回事。

以上就是本章的全部内容啦！
最后感谢能够看到这里的读者，如果我的文章能够帮到你那我甚是荣幸，文章有任何问题都欢迎指出！制作不易还望给一个免费的三连，你们的支持就是我最大的动力！