【数据结构】--- 探索栈和队列的奥秘

这篇具有很好参考价值的文章主要介绍了【数据结构】--- 探索栈和队列的奥秘。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言
关注小庄 顿顿解馋૮(˶ᵔ ᵕ ᵔ˶)ა
💡个人主页:9ilk
💡专栏:数据结构之旅


上回我们学习了顺序表和链表,今天博主来讲解两个新的数据结构 — 栈和队列 , 请放心食用

🏠 栈

【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言

对于这么坨书,我们要拿到最下面的书是不是要最后才能拿到;而对于最上面的书它是最晚放上去的却能最先拿到,这样的一个场景就跟我们接下来要介绍的栈类似 — Last in First out(后进先出)

📒 何为栈

【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言

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

压栈:栈数据的插入操作叫做压栈/入栈/进栈,入数据在栈顶。
出栈:栈数据的删除操作叫做出栈,出数据也在栈顶。

👿 栈后进先出是相对的

【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言
由图中我们可知,栈的后进先出是对于同时在栈里的数据而言的

📒 栈的实现

通过前面的分析我们知道,我们需要一个栈顶来表示数据,这跟我们链表的头结点有点相似,但是对于单链表来说实现栈,尾部插入数据并不方便,因此我们选择数组实现栈
【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言

  • 动态栈
typedef int Datatype;
typedef struct Stack
{
	Datatype* arr;
	int top;
	int capacity;
}ST;
  • 栈的初始化与销毁
//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

关于top的初始化:1.top表示栈顶元素的下一个位置时,让top初始化为0,插入数据时先top后++ ;2.top表示栈顶元素 时,top初始化为-1,此时先++后再用top

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

  • 栈的插入数据和删除数据
    这里有了前面顺序表的基础就很简单了,不过要注意压栈和出栈都是在栈顶
//入栈
void StackPush(ST* ps, Datatype data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{//扩容
		int newcapacity = 0;
		newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		Datatype* temp = (Datatype*)malloc(newcapacity * sizeof(Datatype));
		if (temp == NULL)
		{
			perror("malloc failed");
			return;
		}
		ps->arr = temp;
		ps->capacity = newcapacity;
	}
	//入栈
	ps->arr[ps->top++] = data;

}
//出栈
void StackPop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	ps->top--;
}
  • 获取栈顶元素
// 获取栈顶元素 
Datatype StackTop(ST* ps)
{
	assert(ps);
	//栈不能为空
	assert(ps->top != 0);
	return ps->arr[ps->top - 1];
}
  • 判断是否为空
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0 ? 1 : 0;

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

🏠 队列

栈是后进先出,那有我们的先进先出(First in First out)吗 ? 当然有,跟现实中我们排队买票一样,这样数据结构叫做队列

📒 何为队列

【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言

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

📒 队列的实现

由于我们是先进先出,出在队头出,进在队尾进,所以我们需要两个“指针”front 和 rear 来标识位置有效率些。

那用数组来实现好还是链表呢?
【数据结构】--- 探索栈和队列的奥秘,数据结构,数据结构,c语言
用数组的话不好出数据,所以我们这里推荐用链表实现;同时我们可以将front和rear封装进一个结构体这样比较省事

  • 队列结构
typedef int Datatype;
typedef struct QNode
{
	Datatype data;
	struct QNode* next;
}QNode;


typedef struct Quque
{
	QNode* head;
	QNode* tail;
	int size;
}Quque;

注:我们可以定义一个size表示数据个数,弥补链表需要循环遍历确定数据个数的缺陷

  • 队列的初始化和销毁
//队列的初始化和摧毁
void QuqueInit(Quque* pq)
{
	assert(pq);
	pq->size = 0;
	pq->head = pq->tail = NULL;
}
void QuqueDestroy(Quque* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;

}
  • 入队和出队

出队就是链表的头删 入队就是尾插

//队列的入队列和出队列
void QuquePop(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);//对嘞不能为空
	//0个结点

	//1个结点
	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
void QuquePush(Quque* pq, Datatype x)
{
	assert(pq);
	//申请新结点
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL)
	{//0个结点
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
  • 获取头元素和尾元素
//队列的头元素和尾巴元素
Datatype QuqueFront(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);
	return pq->head->data;//设置两个指针进结构体的好处
}
Datatype QuqueBack(Quque* pq)
{
	assert(pq);
	assert(pq->head != NULL);
	return pq->tail->data;//设置两个指针进结构体的好处
}
  • 队列是否为空
//队列是否为空
bool QuqueEmpty(Quque* pq)
{
	assert(pq);
	if (pq->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}

}
  • 队列有效数据个数
//队列数据个数
int QuqueSize(Quque* pq)
{
	assert(pq);
	return pq->size;

}

本次分享到这就结束咯,下次我们将讲解链表,栈和队列的OJ题,敬请期待 ~文章来源地址https://www.toymoban.com/news/detail-849550.html

到了这里,关于【数据结构】--- 探索栈和队列的奥秘的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】—手把手带你用C语言实现栈和队列(超详细!)

                                       食用指南:本文在有C基础的情况下食用更佳                                     🔥 这就不得不推荐此专栏了:C语言                                   ♈️ 今日夜电波:Tell me —milet                    

    2024年02月14日
    浏览(119)
  • 数据结构(C语言实现)——栈和队列的介绍及基本操作的实现(动态顺序栈+链队)

    今天我们来学习另外两个线性结构——栈和队列,栈和队列是操作受限的线性表,因此,可称为限定性的数据结构。 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守

    2023年04月19日
    浏览(44)
  • 【数据结构】栈和队列(队列篇)

    上期我们已经学习了数据结构中的栈,这期我们开始学习队列。 目录 1.队列的概念及结构 2.队列的实现 队列结构体定义 常用接口函数 初始化队列 队尾入队列 队头出队列 获取队列头部元素、 获取队列队尾元素 获取队列中有效元素个数 检测队列是否为空 销毁队列 3.循环队

    2024年02月13日
    浏览(42)
  • 数据结构---栈和队列

    栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作,进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。 出栈:栈的删除操作

    2024年01月18日
    浏览(42)
  • 数据结构--栈和队列

    栈是一种常见的数据结构,它遵循 后进先出LIFO (Last In First Out)的原则。 进行数据插入和操作的一端称为栈顶,另一端称为栈底 。 压栈 :栈的插入操作被称为压栈/进栈/入栈,入数据在栈顶。 出栈 :栈的删除操作。出数据也在栈顶; 栈可以用 数组 或者是 链表 来实现;

    2024年02月09日
    浏览(42)
  • 数据结构 | 栈和队列

    … 📘📖📃本文已收录至:数据结构 | C语言 更多知识尽在此专栏中! 栈(Stack) 又名堆栈,它是一种运算受限的线性表,限定仅在表尾进行插入和删除操作的线性表。 队列(Queue) 也是一种特殊的线性表,特殊之处在于它只允许在表的前端(Front)进行删除操作,而在表的

    2024年01月23日
    浏览(44)
  • 数据结构——栈和队列

    目录  一.前言 二.前文回顾 三.栈 3.1 栈的概念及结构 3.2 栈的实现 3.2.1 初始化函数 3.2.2 销毁函数 3.2.3 入栈函数 3.2.4 出栈函数 3.2.5 计算大小函数 3.2.6 空栈函数 3.2.7 获取栈顶函数  3.2.8 小测试 3.3 全部代码 四.栈的练习 4.1 有效的括号 五.队列 5.1队列的概念及结构 5.2 队列的实

    2024年01月25日
    浏览(48)
  • [数据结构】栈和队列

    目录 1.栈 1.1概念 1.2 栈的使用 1.3.栈的模拟实现 2.队列 2.1概念 2.2队列的使用 2.3队列的模拟实现 2.4 循环队列 2.5双端队列   栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素

    2024年02月07日
    浏览(43)
  • 数据结构:栈和队列

    朋友们、伙计们,我们又见面了,本期来给大家解读一下栈和队列方面的相关知识点,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏:C语言:从入门到精通 数据结构专栏:数据结构 个 人 主 页 :  stackY、 目录 前言:  1.栈 1.1栈的

    2024年02月06日
    浏览(44)
  • 栈和队列【数据结构】

    2024年02月16日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包