数据结构——栈和队列（详解）

目录

栈

什么是栈

链表实现栈？还是顺序表实现栈？

栈的语法结构

栈的初始化 STInit

栈的销毁 STDestroy

入栈 STPush

出栈 STPop

判空 STEmpty

取栈顶 STTop

有效个数 STSize

栈の总代码

队列

什么是队列

链表实现队列？还是顺序表实现队列？

队列的语法结构

队列的初始化 QueueInit

队列的销毁 QueueDestroy

入队列（尾插） QueuePush

出队列（头删） QueuePop

取队头 QueueFront

取队尾 QueueBack

判空 QueueEmpty

数据个数 QueueSize

队列の总代码

栈和队列の结语

---

栈

什么是栈

栈，一种仅允许在一端进，一端出的结构

如上图所示，进数据和出数据的一端叫做栈顶，而相反的一段则叫做栈底

数据从栈顶入，从栈顶出

我们可以以吃货的视角打开栈：栈就像一个肉串，串肉要从尖的一段串进去，同时也是从尖的一端被吃掉

我们还能发现，先被串进去的肉，会最后被吃掉

栈也是如此，符合FILO原则，FILO就是 first in last out，翻译过来就是先进后出

链表实现栈？还是顺序表实现栈？

首先，我们先来确定一下栈需要实现的几个功能：初始化、销毁、数据插入、删除、找到栈顶、判断空、数据个数

大多数的功能无论是链表还是顺序表都能轻松实现，对于顺序表，插入数据就是尾插，删除就是尾删（ 有效个数-- ）。对于链表来说，也是如此。

但是，我们的顺序表要找栈顶可以直接定位到有效个数个位置，找到栈顶相当轻松（数据是连续开辟的），但是我们的链表要找栈顶可就麻烦了，我们找栈顶还需要遍历一遍，时间复杂度直接变成了 O(N)，效率太低了

或许有人会说，我们可以使用双向链表啊，通过头的上一个就能找到尾节点了。虽然可以，但是就有点大炮打蚊子了，何必这么复杂呢？更何况使用了双向链表，我们维护的成本也会提高，得不偿失

两相比较之下，顺序表实现栈，就成了最优的选择

另外，如果有对顺序表不是很熟悉，或是想更深入了解顺序表的老铁，可以看一看下面这篇关于顺序表的博客

初阶数据结构——顺序表（详解）

栈的语法结构

我们现在是在使用顺序表实现栈，换种方式理解，就是用顺序表实现先进后出（FILO），以这种方式实现了栈

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;//下标
	int capacity;
}ST;

如上：同样的，我们需要将要存进栈内的数据 typedef 一下，试想一下：如果有一天要你将栈内的所有数据从 int 改为 char ，如果没有这个 typedef 的话，那么改起来将会相当麻烦，而且，这种情况是真实存在的且会发生的

我们将顺序表定义为动态顺序表，方便以后的扩容操作

同时，我们还在结构体内定义了有效数据个数 top，和顺序表总大小 capacity

栈的初始化 STInit

//初始化
void STInit(ST* ps)
{
	assert(ps);
 
	ps->a = NULL;
	ps->top = 0;//指向栈顶的下一位
	ps->capacity = 0;
}

对于栈的初始化，我们会将指向顺序表的指针初始化为 NULL，将 capacity 初始化为 0，这都是老生常谈的了

但是这个 top（有效数据个数）就有点意思了，因为我们要让 top 指向的是栈最后插入数据的下一个位置

可能有人会好奇，为什么不能让 top 指向最后一个插入的数据呢？

试想一下，如果我们将 top 指向最后一个插入的数据的话，那么当只有一个数据的时候，top 会指向 0 的位置，那么如果栈为空呢？指向 -1 ？

另外，让其这么指向也没有什么坏处，我们在后面判断空的时候，我们可以直接判断如果 top == 0，则为空。在判断栈是否满了的时候，我们也可以判断如果 top == capacity，则栈满了，扩容

栈的销毁 STDestroy

//销毁
void STDestroy(ST* ps)
{
	assert(ps);
 
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

栈的销毁在本质上和顺序表并没有太大的差别，同样是将动态开辟出来的顺序表空间给 free 掉，同时将指向动态空间的指针给置为空（防止野指针问题），最后将 top（有效数据个数）和 capacity 给置为 0 ，至此，关于栈的销毁就结束了

入栈 STPush

//入栈(尾插)
void STPush(ST* ps, STDataType x)
{
	assert(ps);
	//判断容量满了或为空，扩容
	if (ps->capacity == ps->top)
	{
		//进来代表满了或为空
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (!tmp)
		{
			perror("realloc fail!");
			return;
		}
        //开辟成功
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
    //尾插数据（入栈）
	ps->a[ps->top++] = x;
}

入栈，无非就是尾插一个数据，因为顺序表头部是栈底，是不能插入数据的

而我们也只是入栈这一个地方需要判满扩容，所以我们也不用重新封装一个函数，直接写就行了

1. 判满扩容

判满，什么时候栈满了，就是当我的有效数据个数和我的总容量相同的时候，栈就满了，也就是 top == capacity ，满足这个条件，就代表栈满了，需要扩容

而如果要扩容的话，要使用到 realloc，我们就需要知道扩容后的总大小是多少，但是还有一种情况，就是如果 top 和 capacity 同时为空怎么办？这时我们可以用上三目操作符：如果容量（capacity）为 0，那么就将新栈的大小定为 4（随意定义，4 在这里只是示范，不是说一定得要 4），如果不为 0，我们就将大小定义为原大小的两倍，因为两倍的效率是最高的

int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;

接着就是使用 realloc，对栈进行扩容，随后判断开辟动态空间是否成功，最后尾插数据，有效数据个数++

ps->a[ps->top++] = x;

如上，值得一提的是，此处使用的是后置++，在程序执行结束之后 top 才会++，这种写法会比多写一行看起来更优

出栈 STPop

出栈步骤和顺序表的尾删是一样的，我们不需要动那个数据，只需要将有效数据个数减一即可

因为我们后续无论是遍历还是其他，这个数据在不在都没有影响，如果在这之后要插入数据的话，我们直接插入将其覆盖即可

如下：

但这里我们还需要进行一个操作，就是判断栈是否为空，如果都没有数据了，我们还怎么删？

由于这里是栈，我们解决问题可以分为两步

1. assert 断言

2. 后面需要实现的判空函数 STEmpty

判空就是：如果为空，返回 1，不为空则返回 0，这里我就以判空为例，先用着先，后续我们再来实现

如果为空，assert 触发，终止程序，不为空，我们就正常尾删，即 top-- 即可

当然我们也可以像顺序表一样直接断言 top，这里只是举例，毕竟实现栈是很灵活的

代码如下：

void STPop(ST* ps)
{
	assert(ps);
	//判断是否为空
	assert(!STEmpty(ps));
	ps->top--;
}

判空 STEmpty

看到这个判空，相信很多人都知道要怎么写了：if 判断一下，如果 top 为多少怎么怎么样，else 怎么怎么样

这里教大家一种更精妙的方法，我们直接返回 top == 0 的结果，如下：

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

注：bool 是布尔值，可以简单理解成 返回 0 或 1

如果 top == 0，那么返回的结果就是 1，如果 top != 0，那么就会返回 0

取栈顶 STTop

我们如果要取栈顶的话也很容易，我们只需要取到顺序表里 top-1 的数据就可以了（ top 指向的是最后插入数据的下一个位置）

但是在取栈顶之前，我们也需要判断一下是否为空，因为如果为空，栈里面都没有数据，我还怎么取栈顶？

代码如下：

STDataType STTop(ST* ps)
{
    //判断栈是否存在
	assert(ps);
	//判断是否为空
	assert(!STEmpty(ps));
    //取栈顶
	return ps->a[ps->top - 1];
}

有效个数 STSize

对于有效个数，我们直接返回 top 就可以了，虽然 top 并不指向栈顶，而是栈顶的下一个，但是栈的下标是从 0 开始的，所以 top 的大小刚好就是有效个数的大小

代码如下：

int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

栈の总代码

如果需要如上所有栈的代码的话，可以点击下方链接：

栈的代码 gitee

队列

什么是队列

就像我们日常生活中的排队一样，队列就是从一端进，从另一端出

和栈不一样的是，栈是FILO（先进后出），而队列是FIFO（ 先进先出 first in first out ）

链表实现队列？还是顺序表实现队列？

同样的，我们来看一下二者之间的差别

如果选择顺序表的话，那么要么是头插尾删，要么是头删尾插，因为队列必须是一端进，另一端出。而无论是头插还是头删，都会涉及到数据的挪动，实现起来相当麻烦，效率低下，不是一个好的选择

再来看一看链表，头插头删是能轻松实现的，但是尾插尾删可能就没那么友好了，因为要尾插尾删的话，我们还需要先找到尾节点，而尾删的话还要找到尾节点的前一个节点

那我们能不能换一种思路，既然可以在 头删尾插 和 头插尾删 两个里面选择的话，我另外用一个结构体把两个指针装起来：一个指向头节点，一个指向尾节点

而因为尾删要找尾节点的前一个节点不好找，那我们干脆就不尾删，选择头删尾插，头删有头节点，能轻易完成，尾插也有指向尾部的节点，能轻易完成

或许有人会想到，我们也能将定义多一个指向尾节点的指针的方法，应用在栈上面啊

确实可以，但是链表没顺序表来得更方便，可以说一个是 9 分选手，一个是8.5分选手，其实选哪个都可以，硬要说的话差别也不大

但是，现在要来实现队列了，面对队列的话，就不是一个 8.5 一个 9 了，而是顺序表是 5 分以下，而链表是 9 分选手了，因为要用顺序表实现队列的话，就必然会涉及到数据的挪动，

时间复杂度超级大，效率超级低

综上，我们要实现队列的话，链表，就是不二之选

如果有老铁对链表不太熟悉，或是想更深入地了解一下链表的话，可以看一下下面这两篇博客，将双链表和单链表都进行了详细的讲解：

初阶数据结构——链表专题——单链表详解

初阶数据结构——链表专题——双链表详解

队列的语法结构

typedef int QDataType;
 
//队列
typedef struct QueueNode
{
	int val;
	struct QueueNode* next;
}QNode;
 
//包装两个指针
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

同样是将要存入队列中的数据 typedef 起来，防止要一键修改队列内所有数据类型的情况

接着，由于我们是用链表实现队列，所有我们在定义的时候，也是以链表的方式进行定义

一个结构体内，放着该链表节点存储的数据，和指向下一个节点的地址

接着，我们又定义了一个结构体，里面放着的是指向头节点和尾节点的指针

很多老铁在学习链表的时候对二级指针非常深恶痛绝，因为确实需要一些时间成本去理解，如果我们不将指向头和指向尾的两个指针用结构体封装起来的话，我们要改变二级指针的指向，就需要传指针的地址给函数，然后函数用二级指针接收

但是我们用结构体封装起来之后呢？我们不需要传指针的地址，不需要用二级指针来接收了，我们只需要将结构体的地址传给函数，就能够改变结构体内两个指针的指向

同时我们还需要思考一个问题：

我们如何计算有效个数呢？难道我们是 尾指针 - 头指针？不行，因为链表只是在逻辑结构上连续，但是在物理结构上是不连续的，所有上述的方法行不通

那我们该怎么做呢？

用到了两个指针的时候，就大概率意味着要对成员下手了，那么我们可以在封装指向头和尾的指针里再加一个 size，如果删除或者增加了元素，那么我们的 size 也可以做出相应的改变，而 size，代表的就是有效的数据个数

队列的初始化 QueueInit

我们定义链表的结构体，在 typedef 之后，名字变成了 QNode

由于我们在封装指向头和尾的指针的结构体的时候，我们两个指针都是 QNode*，所以我们初始化就只需要给函数传封装两个指针的结构体作为参数就可以了

void QueueInit(Queue* pq)

而对于这个内涵两个一级指针和一个整形的结构体，其初始化也就显得相当简单，将两个指针置空，将另一个整形变量置为 0 即可

代码如下：

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

队列的销毁 QueueDestroy

队列的销毁，其本质上就是链表的销毁 + 善后（指针置空等）

而我们现在有了一个队列，我们如果要将其销毁的话自然是要一个一个地 free 掉

但如果直接 free 掉的话，我们就没法找到下一个节点了，从而造成了内存泄漏问题

所以，我们需要在删除指针 1 指向的节点之前，将下一个节点的地址先保存到指针 2 中，free 完了之后再让指针 1 的值变为指针 2，指针 2 再指向下一个节点的地址，如此往复

当指针 1 指向空的时候，循环终止，至此，我们的队列就销毁完了，但为了防止野指针问题，我们还需要将指向头和尾的指针都置为空，再让 size 变为 0 

。。。。。。

代码如下：

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;//指针 1
	QNode* next = NULL;//指针 2
	while (cur)
	{
        //销毁队列
		next = cur->next;
		free(cur);
		cur = next;
	}
    //善后
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

入队列（尾插） QueuePush

链表插入数据，我们就需要动态申请一块空间

QNode* newnode = (QNode*)malloc(sizeof(QNode));

随后判断空间是否开辟成功，然后将传过来的值赋给这个新空间的 val（使用函数的时候会将要放进链表的数据作为参数传递过来）

接着，就是尾插环节了，但是这里有一个点需要注意，如果队列内没有数据的话，那么此时我们的头和尾都指向的是 NULL，那么我们在尾插数据的时候，就需要让两个指针都指向新开辟出来的节点，因为第一个节点既是头也是尾

如果队列内有数据，那么我们只需要让当前的尾指向新节点，再让新节点变成新的尾就可以了

由此，我们在进行这一步的时候就需要用到 if ... else ... 语句

在插入完数据之后，我们还需要让 size++ 一下，这个可不能忘了

代码如下：

//入队列
//尾插
void QueuePush(Queue* pq, QDataType x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode)
	{
		perror("malloc fail!");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (!pq->ptail)
		pq->phead = pq->ptail = newnode;
	else
	{
		//让尾节点的下一个节点指向新节点
		pq->ptail->next = newnode;
		//新的尾节点
		pq->ptail = newnode;
	}
	pq->size++;
}

出队列（头删） QueuePop

我们在进行出队列操作的时候，要考虑的就是只有一个节点或者有大于一个节点两种情况，因为如果没有节点的话，那还怎么头删，我们甚至需要 assert 断言一下，防止链表不存在和为空

assert(pq);
assert(pq->phead);

如果只有一个节点，那么就将该节点 free 掉，随后头尾两个指针同时置空

如果有不止一个节点的话，那么我们就正常头删就行

正常头删的核心思路和上面的销毁队列是一样的

在头删结束了之后，不要忘了要让 size--

代码如下：

//出队列
//头删
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
 
	//只有一个节点
	if (!pq->phead->next)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else//多节点
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

取队头 QueueFront

对于取队头，我们肯定是要将存在队列里的内容返回去的，所以返回类型就是存在队列内内容的类型

QDataType QueueFront(Queue* pq)

我们在这里需要断言一下，防止队列不存在与队列为空

最后，直接返回头指针指向的内容即可

代码如下：

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}

取队尾 QueueBack

取队尾和取队头是一样的，只不过返回的内容是尾指针指向的而已

代码如下：

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail!=NULL);
	return pq->ptail->val;
}

判空 QueueEmpty

当队列为空的时候，我们的 size 就为 0，代表的就是 有效数据的个数为 0

所以我们只需要将 size==0 的结果返回就行了，如果 size 不为 0，那么返回 0，如果为 0，那么久返回 1

代码如下：

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

数据个数 QueueSize

这个只需将 size 传过去即可，代码如下：

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

队列の总代码

如果有需要如上队列全部代码的话，可以点击下方的 gitee 链接

队列的代码 gitee

栈和队列の结语

至此，今天我们栈和队列相关知识的讲解就结束啦

如果对你有帮助的话，希望能多多支持呀！！！