• 数据结构初阶之栈和队列--C语言实现

    系列文章目录

    第一章 顺序表、链表
    第二章 栈和队列
    第三章 二叉树
    第四章 八大排序

    文章目录

    前言

    学习栈和队列之前，首先我们要知道，如果说顺序表和链表只是一种数据在内存中不同的存储结构，那么栈和队列就是对内存空间的不同的管理结构。所以栈和队列都可以用顺序表或者链表实现，不同的存储结构并不影响栈和队列对内存空间的管理，只是在代码实现上会有所不同。下面让我们一起来看看吧。

    一、栈

    什么是栈呢？大家都知道，我们的内存空间大致有不同的几个区域，分别是栈区、堆区及静态区。栈区中一般存储的是我们程序中的局部变量、函数栈帧等，堆区一般存储的是动态开辟的空间，而静态区一般存储的是static修饰的静态变量。那这里的栈和我们要学习的栈有什么关联吗？其实是没有关联的，如果说什么相关的话，那么也就是名字一样而已。

    1.1 栈的概念和结构

    什么是栈？
    栈：是一种特殊的线性表，只允许在固定的一端进行插入和删除数据。插入和删除数据的一端叫做栈顶，另一端叫做栈底。 栈有一个原则，叫做后进先出LIFO(Last In First Out)。栈就像我们坐电梯，最先进去的最后出来。

    后进先出原则是学习栈非常重要的内容。理解了这个你才能更好的学习栈。

    栈的两个基本操作：

    1. 压栈：栈的插入操作叫做压栈/入栈/进栈。在栈顶入数据
    2. 出栈：栈的删除操作叫做出栈。在栈顶出数据

    在这里插入图片描述
    在这里插入图片描述
    栈的结构：
    栈的底层逻辑存储结构可以用两种方式，顺序表和链表。无论用那种方式都可以，只是在实现上会有区别。当然，不同的存储结构也有不同的好处，而栈的底层存储结构一般建议用数组(也就是顺序表)实现。因为相对于链表，数组更能适应栈的结构——数组的尾插代价更小。

    1.2 栈的实现

    我们用数组来实现栈。数组的首部我们当做栈底，尾部当做栈顶。
    在这里插入图片描述
    这里就体现出了数组实现的好处，数组对尾部的访问可以直接访问，而链表则不可以直接访问。当然也不是说链表就不好，如果用链表实现，我们可以将链表的头当做栈顶，尾当做栈底，在链表的头部插入/删除数据，代价也比较低。只是数组的结构更符合栈的特性，所以我们建议用数组来实现栈。

    在这里插入图片描述
    栈的实现

    // 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
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; //用top表示栈顶
	int capacity;
}Stack;

//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestory(Stack* ps);

//入栈
void StackPush(Stack* ps,STDataType x);
//出栈
void StackPop(Stack* ps);
//显示栈顶数据
STDataType StackTop(Stack* ps);
//获取栈中元素个数
int StackSize(Stack* ps);
//检查栈是否为空
bool StackEmpty(Stack* ps);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    1.2.1 初始化栈

    栈的初始化没什么好说的，和顺序表的初始化基本没什么区别。

    void StackInit(Stack* ps)
{
	assert(ps);
	ps->capacity = 4;
	ps->a = (STDataType*)malloc(sizeof(STDataType) * ps->capacity);
	if (ps->a == NULL)
	{
		perror("StackInit fail");
		exit(-1);
	}
	ps->top = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    1.2.2 销毁栈

    栈的销毁和初始化这两个接口都没什么好说的，代码也很简单。

    void StackDestory(Stack* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    1.2.3 入栈

    入栈接口的实现要符合栈的特性：只在栈顶入数据。用数组实现就很简单，数组尾部当做栈顶，头部当做栈底。然后插入数据（入栈）即可。

    注意也要判断栈是否满了。

    void StackPush(Stack* ps, STDataType x)
{
	assert(ps);
	//满了进行扩容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (tmp == NULL)
		{
			perror("Expansion fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
	//栈顶入数据
	ps->a[ps->top] = x;
	ps->top++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    1.2.4 出栈

    出栈的逻辑就不用说了，直接让top自减就可以。

    void StackPop(Stack* ps)
{
	assert(ps);
	ps->top--;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    但是这里就有一个问题，直接出栈后我们就拿不到栈顶的数据了，所以在出栈前我们要将栈顶的元素存起来，这就是下一个接口。

    1.2.5 获取栈顶元素

    直接返回栈顶元素就可以。

    STDataType StackTop(Stack* ps)
{
	assert(ps);
	return ps->a[ps->top - 1];
}

    • 1
    • 2
    • 3
    • 4
    • 5

    1.2.6 获取栈中的元素个数

    top就是栈中的元素个数。

    int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    1.2.7 检查栈是否为空

    top为0栈就为空。

    bool StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    以上就是栈的实现，我们可以发现，栈的结构其实是很简单的，实现也非常简单。队列其实也差不多，下面我们来看看队列吧。

    二、队列

    2.1 队列的概念和结构

    什么是队列？
    队列就像我们现实中排队一样，假如我们要去银行办理业务，就需要排队，先排队的先处理业务，后排队的后处理业务。而队列也是如此。

    队列：只允许在一端进行插入数据，在另一端进行删除数据的特殊线性表。队列的原则是先进先出FIFO（First In First Out）。进行插入操作的一端叫做队头，进行删除操作的一端叫做队尾

    在这里插入图片描述
    队列的结构：
    队列的底层逻辑存储结构也一样，顺序表或者链表都可以。但由于队列的特性，一般建议用链表实现队列。因为队列需要在队头出数据，而顺序表在头部出代价较大，要挪动整个数组，因此建议用链表。

    那么用链表实现队列的话，结构就稍微复杂一点，因为会有许多细节需要注意，下面我们来看看队列的实现吧。

    2.2 队列的实现

    typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size; //给一个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);
//检测队列是否为空
bool QueueEmpty(Queue* pq);

int QueueSize(Queue* pq);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    这就是队列我们要实现的所有接口。关于这个size的具体作用在接口的实现上会讲到。

    2.2.1 初始化队列

    初始化队列很简单，将head和tail指针置为空即可，size初始为0。

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    有了初始化，一般来说我们会再写销毁，那么队列这里我们将销毁放到后面在写，因为队列的销毁会有一些要注意的点在我们写完了其他接口，对队列的结构有了更深的理解后，才会有更好的认识。

    2.2.2 入队列

    入队列是我们要第一个学习的接口，要写好入队列这个接口，首先要我们对队列的结构有一定的理解。

    我们的队列是用链表写的，当队列中没有数据时，队列为空，链表也为空，而我们插入第一个数据时，就需要注意，链表一个结点存储我们的数据，让队列的头和尾指向这个结点。在这里插入图片描述
    之后的插入数据，就是让我们的链表链接起来，用tail指向最后一个结点。
    在这里插入图片描述这就是我们的入队列。其实入队列的逻辑很简单，我们理解这一块最主要的就是要将队列和链表分离开来，链表是我们的存储结构，而队列是我们用来管理链表的。无论你是用什么方式进行存储，我们的管理方式都不变，用数组存储是这样，链表也同样如此。

    void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请结点存储数据
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->next = NULL;
	newnode->data = x;
	//判断是不是第一个数据
	if (pq->tail == NULL)
	{
		//让head和tail都指向第一个结点
		pq->tail = pq->head = newnode;
	}
	else
	{
		//让结点链接起来
		pq->tail->next = newnode;
		//让tail指向队尾
		pq->tail = newnode;
	}
	pq->size++;	//用来统计队列中的元素个数
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    2.2.3 出队列

    队尾入数据，队头出数据，出队列就是类似于链表的头删。这里要注意当队列只剩一个数据的时候，也就是链表只有一个结点，需要另外的处理。

    void QueuePop(Queue* pq)
{
	assert(pq);
	//这里出队列的时候要注意判空，队列为空不能删除
	assert(!QueueEmpty(pq));
	//我们用size来统计队列中的元素个数，当size==1，就只有一个元素。
	if (pq->size == 1)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		//链表头删的逻辑，head指向队头（也就是链表的头部）。
		QNode* cur = pq->head;
		pq->head = pq->head->next;
		free(cur);
	}
	pq->size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    2.2.4 检测链表是否为空

    这里就体现了我们额外定义一个size变量的好处，当size为0时，队列就为空。

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

    • 1
    • 2
    • 3
    • 4
    • 5

    2.2.5 显示队列头元素

    head就指向我们的队头结点。

    QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2.2.6 显示队列尾元素

    tail就指向我们的队尾结点

    QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    2.2.7 获取队列中的元素个数

    size就是队列中的元素个数

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

    • 1
    • 2
    • 3
    • 4
    • 5

    2.2.8 销毁队列

    现在我们再来看看队列的销毁，其实队列的销毁就像链表的销毁一样，只是这里我们有了队头和队尾两个指针管理。队列销毁的是链表中的结点

    void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = cur->next;
	}
	pq->head = pq->tail = NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    以上就是队列的实现，队列的结构相比栈更复杂是因为我们用了链表来实现，但本质上无论用顺序表还是链表实现都是一样的，只要我们将管理结构和存储结构分离开来，就很好理解。

    总结

    关于栈和队列的概念和结构以及实现部分我们就学习到这里，要想对栈和队列有更深的认识，还需要我们来做一些相关的题目，这里我给大家推荐几道相关的题，大家可以下来自己做一做。

    1. 括号匹配问题 OJ链接 ps：用栈来完成。
    2. 用队列实现栈 OJ链接
    3. 用栈实现队列 OJ链接
    4. 设计循环队列 OJ链接

    以上就是我们所有的内容，希望对大家有所帮助，谢谢！

  • 相关阅读:
    归并排序与非比较排序详解
    【freeRTOS】操作系统之五.-内存管理
    第3章业务功能开发（线索关联市场活动，动态搜索）
    含文档+PPT+源码等]基于ssm maven健身房俱乐部管理系统[包运行成功]Java毕业设计SSM项目源码
    【深度学习】 Python 和 NumPy 系列教程（十六）：Matplotlib详解：2、3d绘图类型（2）3D散点图（3D Scatter Plot）
    使用vite + vue3 + ant-design-vue + vue-router + vuex 创建一个管理应用
    element源码（五）radio 单选框组件
    Re 爬取数据
    2024超好看的404单页HTML源码
    docker 实战命令集合
  • 原文地址：https://blog.csdn.net/qq_40005416/article/details/126655314