IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构初阶之栈和队列--C语言实现 -> 正文阅读

[数据结构与算法]数据结构初阶之栈和队列--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.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.2 销毁栈

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

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

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.4 出栈

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

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

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

1.2.5 获取栈顶元素

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

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

1.2.6 获取栈中的元素个数

top就是栈中的元素个数。

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

1.2.7 检查栈是否为空

top为0栈就为空。

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

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

二、队列

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);

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

2.2.1 初始化队列

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

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

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

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++;	//用来统计队列中的元素个数
}

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--;
}

2.2.4 检测链表是否为空

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

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

2.2.5 显示队列头元素

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

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

2.2.6 显示队列尾元素

tail就指向我们的队尾结点

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

2.2.7 获取队列中的元素个数

size就是队列中的元素个数

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

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. 括号匹配问题 OJ链接 ps:用栈来完成。
  2. 用队列实现栈 OJ链接
  3. 用栈实现队列 OJ链接
  4. 设计循环队列 OJ链接

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

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-13 11:43:26  更:2022-09-13 11:47:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 18:51:18-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计