数据结构双子星：用C语言玩转栈的LIFO和队列的FIFO特性

栈和队列的知识点详解（附上C语言代码）

珊瑚里的鱼

1261人浏览 · 2025-02-26 18:35:59

珊瑚里的鱼 · 2025-02-26 18:35:59 发布

栈和队列需要借助前面学习过的顺序表和链表这两种数据结构。

一、栈

1.概念与结构

（1）概念

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

后进先出 / 先进后出的原则可以类比为放碗的过程。一个一个碗堆放起来，最先放入的碗一定是最后拿到的，最后放入的碗一定是最先拿到的。

压栈：栈的插⼊操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作。出数据也在栈顶。

在这里插入图片描述

（2）底层结构

既然说到栈是一种特殊的线性表，既然是线性表，就要从两个维度分析：
栈的逻辑结构：一定是线性的。
栈的物理结构：栈的底层结构决定了栈的物理结构是线性的还是非线性的，前面所学的底层结构有数组结构和链表（由结点组成的）结构两种，可以用它们来实现栈的数据结构。

为了实现栈的数据结构，用数组实现更好一些呢？还是用链表实现更好一些呢？

假定使用数组来实现栈，数组必须符合栈的先进后出/后进先出的特性。接下来定义栈顶，栈顶是出数据/入数据的一端，另一端必须要封死。对于数组结构，仅仅分析数组的话，数组既可以在前面插入、删除数据，也可以在后面插入、删除数据。所以，要想使用数组来实现栈，就要对数组加以限制，使之变成栈的特性。那么栈顶定义在数组的头部还是数组的尾部呢？衡量一个算法的好与坏要从复杂度出发，假设把栈顶定义在数组尾部，出入数据只会在数组尾部进行，根据前面顺序表的知识，入栈/出栈的时间复杂度是O(1)；反之定义在头部，入栈/出栈的时间复杂度是O(n)。下图是个栈，底层结构是个数组：

在这里插入图片描述

结论：使用数组实现栈的数据结构，栈顶必须定义在数组尾部，栈的入栈/出栈的时间复杂度是O(1)。

假定使用链表来实现栈，这里指单链表来实现栈，那么哪一端设置为栈顶呢？若把当前链表的尾部结点看成栈顶，入数据相当于单链表的尾插，时间复杂度是O(n)，这个时间复杂度不是最好的，那么就将栈顶定义在第一个结点，此时栈的出入数据相当于单链表的头插、头删，入栈/出栈的时间复杂度是O(1)。下图是个栈，底层结构是个链表：

结论：使用链表实现栈的数据结构，栈顶必须定义在链表头部（第一个结点上），栈的入栈/出栈的时间复杂度是O(1)。

很明显，选择这两种数据结构实现栈都行，但是二者的效率和占用内存都不一样，最终会选择数组作为栈的底层结构，主要是内存的问题：

数组里面定义栈的结构，数组里每插入一个整型数据，数组里申请4个字节就行：

在这里插入图片描述

单链表中定义栈的结构，根据结构体对齐，每插入一个数据，都要向操作系统申请8个字节的空间，相比数组的消耗空间更大些：

数组底层结构是连续的，链表的物理结构不一定是连续的，所以使用链表还会面临内存碎片的问题。

因此，选择数组底层结构来实现栈，这样一来，栈的物理结构也是线性的，栈的结构的定义和顺序表的结构的定义是一模一样的。

栈顶一端可以出入数据，所以栈顶一端是开口的，画图的时候注意！

2.栈的实现

//Stack.h
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//指向栈顶的位置
	int capacity;//容量
}ST;
//typedef struct Stack ST;

//初始化
void STInit(ST* ps);
//销毁
void STDestroy(ST* ps);
//入栈---栈顶
void StackPush(ST* ps, STDataType x);
//出栈---栈顶
void StackPop(ST* ps);
//栈为空
bool StackEmpty(ST* ps);
//取栈顶元素
STDataType StackTop(ST* ps);
//获取栈中有效数据个数
int STSize(ST* ps);

（1）初始化

初始状态：栈为空，栈顶、栈底都在数组下标为0处，即栈顶 == 栈底。

//初始化
void STInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

栈顶即可以表示栈中已保存的数据个数，也可以表示栈中要插入数据的位置

最后调试检查，形参的改变影响实参：
在这里插入图片描述

（2）销毁

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

在这里插入图片描述

（3）入栈

入栈的函数名StackPush为什么不像前面顺序表和链表的插入删除函数名一样加上Back/Front？因为栈不支持顺序表、链表的插入删除的操作，只在栈顶插入删除数据。

没有必要单独封装成检查栈的空间是否足够的函数，因为栈中所涉及的增加栈中的数据只有入栈函数一种。

在这里插入图片描述

//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//空间满了/初始状态栈为空，扩容
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

在这里插入图片描述

（4）出栈

出栈的函数名与入栈的函数名同理，没有Back / Front。

因为top表示栈中有效数据的个数，所以直接top--或--top即可，这样，栈中的有效数据个数就会减少，实现出栈。

断言需满足两个条件：

传参，栈不为空，即栈为存在的
保证栈中有数据

bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
//出栈---栈顶
void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));
	--ps->top;
}

（5）取栈顶元素

数组下标为top - 1的元素即为栈顶元素。

在这里插入图片描述

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}

在这里插入图片描述

（6）获取栈中有效数据个数

top即为栈中有效数据个数。

//获取栈中有效数据个数
int STSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

在这里插入图片描述

二、队列

1.概念与结构

（1）概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

先进先出的原则可以类比学生在食堂排队打饭的过程。最先排好队的最先打到饭，就可以最先从队伍中离开。

入队列：进行插入的操作
出队列：进行删除的操作
队尾：进行插入操作的⼀端
队头：进行删除操作的⼀端

在这里插入图片描述

（2）底层结构

同样的，队列也是一种特殊的线性表，也是要从两个维度分析，那么队列选取数组还是链表作为它的底层结构呢？

既然栈最后选取数组作为它的底层结构，那么我们可以有个大胆的猜想：链表就是队列的底层结构！

那就来看看链表到底能不能实现队列吧！

如下图所示，链表（以单链表为例）的第一个结点和最后一个结点分别作为对头/队尾分析：
在这里插入图片描述
可以得出：

当单链表的第一个结点作为对头，最后一个结点作为队尾时，入队列的时间复杂度：O(n)，出队列的时间复杂度：O(1)。
当单链表的第一个结点作为队尾，最后一个结点作为对头时，入队列的时间复杂度：O(1)，出队列的时间复杂度：O(n)。

这两种情况中都有出现时间复杂度：O(n)，很明显都不是最好的复杂度。问题出现在都需要一个指针遍历到尾结点，这里遍历就会出现循环。那么不如直接建立一个指针指向队尾，这样就避免出现了循环！（数组就不能直接建立一个指向队尾的指针）

为了更符合单链表的使用，用第一种写法，第一个结点为对头phead、尾结点为队尾ptail：
在这里插入图片描述

入队列后，改变指针的指向即可：

在这里插入图片描述

队头队尾指针指向的结点会随着入队出队的变换而变换的。

结论：队列的底层结构是链表，因此，队列的物理结构不一定是线性的。

双向链表的各种实现方法的时间复杂度都是O(1)，那么为什么不直接用双向链表实现呢？
如果是双向链表的话，每申请一个结点，就会比单链表中申请的一个结点多一个前驱指针，在32位操作系统之下，会额外申请4个字节的空间。一个双向链表结点的构成：一个整形数据（假设是整形数据），两个指针。那么一个结点就是12个字节，若最大对齐数为8，则每个结点的大小是16字节，而单链表的每个结点大小是8个字节。因此，选择单链表实现队列不会占用太多的空间。

队列的底层结构是链表，链表是由结点构成的，因此可以写出结点（链表）的结构；在队列中，只关注队头、队尾结点，也就是队列由两个分别指向对头、队尾的指针构成的，队列中的有效数据个数也是队列的一部分，每次入队/出队，有效数据个数也会跟着增/减，所以可以写出队列的结构：

//Queue.h
//定义结点的结构
typedef int QDataType;
struct QueueNode {
	QDataType data;
	struct QueueNode* next;
};
typedef struct QueueNode QueueNode;
//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//对头
	QueueNode* ptail;//队尾
	int size;//有效的数据个数
}Queue;

其实数组也可以作为队列的底层结构，但是在数组头部插入、删除元素时间复杂度都为O(n)，复杂度不是最好的。

2.栈的实现

//Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//定义结点的结构
typedef int QDataType;
struct QueueNode {
	QDataType data;
	struct QueueNode* next;
};
typedef struct QueueNode QueueNode;
//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//对头
	QueueNode* ptail;//队尾
	int size;//有效的数据个数--稍后讲解
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队---队尾
void QueuePush(Queue* pq, QDataType x);
//出队---队头
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空。为空，返回true；不为空，返回false
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

（1）初始化

//Queue.c
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

（2）销毁

别忘了最后把phead、ptail置为NULL，不然phead、ptail就是野指针！

在这里插入图片描述

//Queue.c
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

（3）入队列

有两种可能：

队列为空，也就是指向队头的指针为空。phead、ptail都指向新结点。
队列不为空，新结点作为队尾的后继结点。

每次入队，队列中的有效数据个数就会增加一个。

在这里插入图片描述

//入队列
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->size++;
}

错误写法：

在这里插入图片描述

当队列为空时，还会接着执行这段代码，这会导致最后一个结点的next指向newnode，但是newnode已经是最后一个结点了，会形成一个环。

（4）出队列

有两种可能：

队列中不止有一个结点
队列中只有一个结点

每次出队，队列中的有效数据个数就会减少一个。

在这里插入图片描述

//Queue.c
//出队---队头
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;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

（5）取队头/队尾数据

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

（6）队列有效元素个数

//Queue.c
//队列有效元素个数
int QueueSize(Queue* pq)
{
	return pq->size;
}

在队列结构中加上成员size可以减少不必要的麻烦，就比如实现“队列有效元素个数”，没有成员size代码就会很繁琐：

int QueueSize(Queue* pq)
{
	int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		size++;
		pcur = pcur->next;
	}
	return size;
}

魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

量化挑战赛冠军专访：4小时啃下W4A8量化，我靠的是这些经验

魔乐社区

替你试过了，消费级显卡可以跑的开源文生图SOTA模型，顶级渲染、高密度文本绘图

魔乐社区

「极限压缩量化未来」Modelers GeekDay上海站圆满落幕

魔乐社区

所有评论(0)

查看更多评论

珊瑚里的鱼

@2401_87255690

已为社区贡献1条内容

数据结构双子星：用C语言玩转栈的LIFO和队列的FIFO特性

珊瑚里的鱼

栈和队列

一、栈

1.概念与结构

（1）概念

（2）底层结构

2.栈的实现

（1）初始化

（2）销毁

（3）入栈

（4）出栈

（5）取栈顶元素

（6）获取栈中有效数据个数

二、队列

1.概念与结构

（1）概念

（2）底层结构

2.栈的实现

（1）初始化

（2）销毁

（3）入队列

（4）出队列

（5）取队头/队尾数据

（6）队列有效元素个数

所有评论(0)

温馨提示：您尚未绑定手机号

珊瑚里的鱼