• 队列与堆栈：原理、区别、算法效率和应用场景的探究

    队列与堆栈：原理、区别、算法效率和应用场景的探究

    前言

    本文主要讲解数据结构中队列和堆栈的原理、区别以及相关的应用方向。从图文和代码的角度进行解析。

    原理与应用场景

    队列

    原理

    先进先出的数据结构，元素从队尾入队，从队头出队。

    应用场景：

    任务调度：任务一般都是按序执行，基于先来先服务的概念，先放进去的任务先执行。如：操作系统进程调度、
    排队系统：排队中，每个角色都是相同优先级情况下，比如说：餐厅点餐、银行办理业务、车票购买等系统，所有人都按先来先服务的概念执行。
    消息传递：按照时间顺序进行消息的发送与接收，基于队列也就是先来先服务的概念。如：QQ、微信、QQ邮件。

    堆栈

    原理

    后进先出的数据结构，元素从栈顶进入插入和删除操作。

    应用场景

    由于堆栈式后进先出，所以它能解决一种问题：也就是回退。如解决递归、回溯算法等。这里简单介绍其中递归算法与堆栈的关系。

    递归原理和堆栈在其中的作用
    递归原理

    递归是一种通过在函数内部调用自身来解决问题的技术。把一个大问题拆解成有数个小问题，并逐一解决。通过不断调用自己（函数）把大问题拆解成小问题并把所有小问题的答案组合到一起最终解决大问题。

    堆栈作用

    递归每次调用自身时，都有一个新的地址用于存放它当前解决自身小问题的解，这个地址叫栈帧，栈帧用于存储函数的局部变量、参数、返回地址等信息。函数在不断调用自身时也就不断创造
    新的栈帧，并将这些栈帧压入到堆栈中。满足条件后返回这些栈帧。

    • 存储函数调用的上下文信息，包括局部变量、参数和返回地址等。
    • 跟踪函数调用和返回的顺序，确保递归函数能够按照正确的顺序执行，并避免混乱或重复执行。
    • 限制递归的深度，防止无限递归导致程序崩溃或栈溢出。
    • 提供回退操作，使得递归函数可以从当前状态回到上一层状态，实现问题的逐步解决。

    队列与堆栈区别

    队列为先进先出，堆栈为先进后出。具体的我以代码和运行图形式讲解。

    队列

    <!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title></title>
		<style>
			#dataInput{
				width:100px;
				border:none;
				padding:5px 10px;
				border-bottom:1px solid lightgray;
			}
			#dataInput :active{
				border:none;
			}
			#dataInput :visited{
				border:none;
			}
			button{
				background-color: white;
				padding:5px 10px;
				border:1px solid lightgray;
			}
			.father {
				width: 100px;
				height: auto;
				margin: 0 auto 0 auto;
			}

			.son {
				width: 100px;
				height: 20px;
				border: 1px solid black;
				margin-right: 10px;
				margin: 0 auto 0 auto;
				text-align: center;
				justify-items: center;
				line-height: 20px;
				animation-duration: 3s;
				animation-name: slidein;
			}
		</style>
	</head>
	<body>
		<div style="position: absolute;left:40%;">
			<input id="dataInput" type="number" aria-valuemax="10" placeholder="请输入数据" value="">
			<button onclick="pushs()">入队</button>
			<button onclick="pops()">出队</button>
		</div>
		<div style="height:50px;"></div>
		<div id="father" class="father">
		</div>
		<script>
			function pushs() {
				let doc = document.getElementById('father')
				let data = document.getElementById('dataInput').value
				if (data != '') {
					doc.insertAdjacentHTML('beforebegin', '
    ' + data + '
    '    )
					document.getElementById('dataInput').value = ''
				}
			}

			function pops() {
				document.getElementById('son').remove()
			}
		</script>
	</body>
</html>

    • 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
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    我们首先新增了一个5，这个5被压到最底下了，又点击出队，发现最开始新增的1出队了，这就叫先进先出。

    堆栈

    <!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title></title>
		<style>
			#dataInput{
				width:100px;
				border:none;
				padding:5px 10px;
				border-bottom:1px solid lightgray;
			}
			#dataInput :active{
				border:none;
			}
			#dataInput :visited{
				border:none;
			}
			button{
				background-color: white;
				padding:5px 10px;
				border:1px solid lightgray;
			}
			.father {
				width: 100px;
				height: auto;
				margin: 0 auto 0 auto;
			}

			.son {
				width: 100px;
				height: 20px;
				border: 1px solid black;
				border-top: none;
				margin-right: 10px;
				margin: 0 auto 0 auto;
				text-align: center;
				justify-items: center;
				line-height: 20px;
				animation-duration: 3s;
				animation-name: slidein;
			}
		</style>
	</head>
	<body>
		<div style="position: absolute;left:40%;">
			<input id="dataInput" type="number" aria-valuemax="10" placeholder="请输入数据" value="">
			<button onclick="pushs()">push(入栈)</button>
			<button onclick="pops()">pop(出栈)</button>
		</div>
		<div style="height:50px;"></div>
		<div id="father" class="father">
		</div>
		<script>
			function pushs() {
				let doc = document.getElementById('father')
				let data = document.getElementById('dataInput').value
				if (data != '') {
					doc.insertAdjacentHTML('afterbegin', '
    ' + data + '
    '    )
					document.getElementById('dataInput').value = ''
				}
			}

			function pops() {
				document.getElementById('son').remove()
			}
		</script>
	</body>
</html>

    • 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
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    首先我们，新添加了一个5入栈，到栈顶，然后又点击出栈，会发现最后入栈的5，没有了。这就是先进后出算法。

    算法效率

    正常情况下都是常数时间复杂度也就是O(1),队列的查找操作的时间复杂度为O(n)，而堆栈没有查找操作。

  • 相关阅读:
    【生物信息学】使用谱聚类（Spectral Clustering）算法进行聚类分析
    管理会计习题集及答案 5-7章
    【代码精读】ATF启动bl33程序
    深度解析linux内核模块编译makefile
    FPGA实现UDP传输视频，提供2套verilog工程源码和接收显示上位机程序
    3.16 总线与信号分支线之间应该如何进行连接？OrCAD中使用Bus总线有哪些注意事项？
    洛谷 P1148 拱猪计分
    问题：react函数中的state是上一次的值
    stm32cubemx hal学习记录：RNG
    Mysql进阶-详解InnoDB引擎
  • 原文地址：https://blog.csdn.net/lplovewjm/article/details/134391012