数据结构与算法笔记——了解真像，掌控全局（1）

Z时代
2024-01-10
分类：技术分享

前言——什么是数据结构？

经常听到别人讨论数据结构和算法，但对于它具体是什么，可能大部分初学阶段的人还是会云里雾里

虽然大家在大学时期上过一门叫数据结构的课程，但是大学老师一般都是只讲思想，并没有实际操作，而且在学习时也感觉比较难，考完试就忘得差不多了，所以，自己打算使用JavaScript再重温一遍

那么，回到小标题，数据结构是什么？这里引用百度百科的一句话：

数据结构就是在计算机中，存储和组织数据的方式

那么话不多说，直接开始进行学习吧！

栈

我们知到数组是一种线性结构，并且可以在任意位置进行插入和删除数据

但是有的时候，为了实现某些功能，需要对这种任意性加以限制

而栈和队列，就是比较常见的受限的线性结构

栈是一种很常见的数据结构，不管实在生活中还是在计算机应用中都非常的广泛

栈结构示意图

进栈操作

出栈操作

栈的特点

只允许在一端进行插入和删除运算，这端被称为栈顶，另一端称为栈底

向栈插入新的元素称为进栈、入栈或压栈，他是把新元素放到栈顶元素的上面，使之称为新的栈顶元素

从一个栈删除元素又称为出栈、退栈或弹栈，它是把栈顶元素删除，并是相邻的元素成为新的栈顶元素

一句话就可以描述栈的特性：后进先出

栈结构的实现

实现栈结构有两种比较常见的方式

基于数组的实现

基于链表的实现

栈的部分常见操作

push(element):为栈顶添加一个新元素

pop():移除并返回栈顶元素

peek()查看栈顶元素，不对栈做任何修改

isEmpty():判断栈是否为空，为空返回true，不为空则返回false

size():返回栈的元素个数，和length很像

toString():将栈的内容以字符串返回

在这里，我使用数组结构来实现

// 封装栈
functionStack() {
// 栈的属性
this.item = [];
//栈的操作
// 1.将元素压入栈
Stack.prototype.push = function(element) {
this.item.push(element)
}
// 2.从栈中取出元素
Stack.prototype.pop = function() {
if (this.isEmpty()) { // 先判断栈是否为空
console.log('栈为空');
return null;
}
return this.item.pop();
}
// 3.查看栈顶元素
Stack.prototype.peek = function() {
if (this.isEmpty()) { // 先判断栈是否为空
console.log('栈为空');
return null;
}
return this.item[this.item.length - 1]
}
// 4.判断栈是否为空
Stack.prototype.isEmpty = function() {
if (this.item.length <= 0) {
returntrue;
}
returnfalse;
}
// 5. 获取栈中元素的个数
Stack.prototype.size = function() {
return this.item.length;
}
// 6.toString方法
Stack.prototype.toString = function() {
var resultString = '';
for (var i of this.item) {
resultString += i;
}
return resultString;
}
}
//栈的使用
var s = new Stack()
s.push(2);
s.push(4);
s.push(6);
console.log(s.size()); //输出3
console.log(s.toString()); //输出246
s.pop();
console.log(s.peek()); //输出4
console.log(s.toString()); //输出24

实际问题应用

正十进制整数转二进制

采用除2反向取余的方法，相信大家也不陌生

这里以十进制数28转换过程为例，而反向取余的过程，就可以使用栈来实现

//函数：将十进制正整数转换成二进制
function dec2bin(num) {
//定义栈对象
var s = new Stack();
while (num > 0) { //当num大于0时，则还可以继续做运算
s.push(num % 2); //将num除2的余数存入栈中
num = Math.floor(num / 2); //注意，这里除2要向下取整
}
console.log(s.toString());
//从栈中取出0、1
var binaryString = '';
while (!s.isEmpty()) {
binaryString += s.pop();
}
return binaryString;
}
var binary = dec2bin(28);
console.log(binary); //输出11100