内容简介:原计划是把《你不知道的Javascript》三部全部看完的,偶然间朋友推荐了数据结构与算法的一套入门视频,学之。发现数据结构并没有想象中那么遥不可及,反而发觉挺有意思的。手头上恰好有《学习Javascript数据结构与算法》的书籍,便转而先把数据结构与算法学习。什么是数据结构?下面是维基百科的解释我们每天的编码中都会用到数据结构,因为
写在前面
原计划是把《你不知道的Javascript》三部全部看完的,偶然间朋友推荐了数据结构与算法的一套入门视频,学之。发现数据结构并没有想象中那么遥不可及,反而发觉挺有意思的。手头上恰好有《学习Javascript数据结构与算法》的书籍,便转而先把数据结构与算法学习。
一、认识数据结构
什么是数据结构?下面是维基百科的解释
数据结构意味着接口或封装: 一个数据结构可被视为两个函数之间的接口 ,或者是 由数据类型联合组成的存储内容的访问方法封装
我们每天的编码中都会用到数据结构,因为 数组是最简单的内存数据结构 ,下面是常见的数据结构
- 数组(Array)
- 栈(Stack)
- 队列(Queue)
- 链表(Linked List)
- 树(Tree)
- 图(Graph)
- 堆(Heap)
- 散列表(Hash)
下面来学习学习栈和队列..
二、栈
2.1 栈数据结构
栈是一种遵循 后进先出(LIFO) 原则的有序集合。新添加的或待删除的元素都保存在栈的同一端,称作 栈顶 ,另一端就叫 栈底 。在栈里,新元素都接近栈顶,旧元素都接近栈底。
类比生活中的物件:一摞书:books:或者推放在一起的盘子
2.2 栈的实现
普通的栈常用的有以下几个方法:
-
push
添加一个(或几个)新元素到栈顶 -
pop
溢出栈顶元素,同时返回被移除的元素 -
peek
返回栈顶元素,不对栈做修改 -
isEmpty
栈内无元素返回true
,否则返回false
-
size
返回栈内元素个数 -
clear
清空栈
class Stack { constructor() { this._items = []; // 储存数据 } // 向栈内压入一个元素 push(item) { this._items.push(item); } // 把栈顶元素弹出 pop() { return this._items.pop(); } // 返回栈顶元素 peek() { return this._items[this._items.length - 1]; } // 判断栈是否为空 isEmpty() { return !this._items.length; } // 栈元素个数 size() { return this._items.length; } // 清空栈 clear() { this._items = []; } }
现在再回头想想数据结构里面的栈是什么。
突然发现并没有那么神奇,仅仅只是对原有数据进行了一次封装而已。而封装的结果是: 并不去关心其内部的元素是什么,只是去操作栈顶元素 ,这样的话,在编码中会更可控一些。
2.3 栈的应用
(1)十进制转任意进制
要求:给定一个函数,输入目标数值和进制基数,输出对应的进制数(最大为16进制)
baseConverter(10, 2) ==> 1010 baseConverter(30, 16) ==> 1E
分析:进制转换的本质:将目标值一次一次除以进制基数,得到的取整值为新目标值,记录下余数,直到目标值小于0,最后将余数逆序组合即可。利用栈,记录余数入栈,组合时出栈
// 进制转换 function baseConverter(delNumber, base) { const stack = new Stack(); let rem = null; let ret = []; // 十六进制中需要依次对应A~F const digits = '0123456789ABCDEF'; while (delNumber > 0) { rem = Math.floor(delNumber % base); stack.push(rem); delNumber = Math.floor(delNumber / base); } while (!stack.isEmpty()) { ret.push(digits[stack.pop()]); } return ret.join(''); } console.log(baseConverter(100345, 2)); //输出11000011111111001 console.log(baseConverter(100345, 8)); //输出303771 console.log(baseConverter(100345, 16)); //输出187F9
(2)逆波兰表达式计算
要求:逆波兰表达式,也叫后缀表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式,例如 (a+b)*(c+d)
转换为 a b + c d + *
["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6 ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] ==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
分析:以符号为触发节点,一旦遇到符号,就将符号前两个元素按照该符号运算,并将新的结果入栈,直到栈内仅一个元素
function isOperator(str) { return ['+', '-', '*', '/'].includes(str); } // 逆波兰表达式计算 function clacExp(exp) { const stack = new Stack(); for (let i = 0; i < exp.length; i++) { const one = exp[i]; if (isOperator(one)) { const operatNum1 = stack.pop(); const operatNum2 = stack.pop(); const expStr = `${operatNum2}${one}${operatNum1}`; const res = eval(expStr); stack.push(res); } else { stack.push(one); } } return stack.peek(); } console.log(clacExp(["4", "13", "5", "/", "+"])); // 6.6
(3)利用普通栈实现一个有 min
方法的栈
思路:使用两个栈来存储数据,其中一个命名为 dataStack
,专门用来存储数据,另一个命名为 minStack
,专门用来存储栈里最小的数据。始终保持两个栈中的元素个数相同,压栈时判别压入的元素与 minStack
栈顶元素比较大小,如果比栈顶元素小,则直接入栈,否则复制栈顶元素入栈;弹出栈顶时,两者均弹出即可。这样 minStack
的栈顶元素始终为最小值。
class MinStack { constructor() { this._dataStack = new Stack(); this._minStack = new Stack(); } push(item) { this._dataStack.push(item); // 为空或入栈元素小于栈顶元素,直接压入该元素 if (this._minStack.isEmpty() || this._minStack.peek() > item) { this._minStack.push(item); } else { this._minStack.push(this._minStack.peek()); } } pop() { this._dataStack.pop(); return this._minStack.pop(); } min() { return this._minStack.peek(); } } const minstack = new MinStack(); minstack.push(3); minstack.push(4); minstack.push(8); console.log(minstack.min()); // 3 minstack.push(2); console.log(minstack.min()); // 2
三、队列
3.1 队列数据结构
队列是遵循 先进先出(FIFO,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素 。最新添加的元素必须排在队列的末尾
类比:日常生活中的购物排队
3.2 队列的实现
普通的队列常用的有以下几个方法:
-
enqueue
向队列尾部添加一个(或多个)新的项 -
dequeue
移除队列的第一(即排在队列最前面的)项,并返回被移除的元素 -
head
返回队列第一个元素,队列不做任何变动 -
tail
返回队列最后一个元素,队列不做任何变动 -
isEmpty
队列内无元素返回true
,否则返回false
-
size
返回队列内元素个数 -
clear
清空队列
class Queue { constructor() { this._items = []; } enqueue(item) { this._items.push(item); } dequeue() { return this._items.shift(); } head() { return this._items[0]; } tail() { return this._items[this._items.length - 1]; } isEmpty() { return !this._items.length; } size() { return this._items.length; } clear() { this._items = []; } }
与栈类比,栈仅能操作其头部,队列则首尾均能操作,但仅能在头部出尾部进。当然,也印证了上面的话:栈和队列并不关心其内部元素细节,也无法直接操作非首尾元素。
3.3 队列的应用
(1)约瑟夫环(普通模式)
要求:有一个数组 a[100]
存放0~99;要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删掉的数。
分析:按数组创建队列,依次判断元素是否满足为指定位置的数,如果不是则 enqueue
到尾部,否则忽略,当仅有一个元素时便输出
// 创建一个长度为100的数组 const arr_100 = Array.from({ length: 100 }, (_, i) => i*i); function delRing(list) { const queue = new Queue(); list.forEach(e => { queue.enqueue(e); }); let index = 0; while (queue.size() !== 1) { const item = queue.dequeue(); index += 1; if (index % 3 !== 0) { queue.enqueue(item); } } return queue.tail(); } console.log(delRing(arr_100)); // 8100 此时index=297
(2)菲波那切数列(普通模式)
要求:使用队列计算斐波那契数列的第n项
分析:斐波那契数列的前两项固定为1,后面的项为前两项之和,依次向后,这便是斐波那契数列。
function fibonacci(n) { const queue = new Queue(); queue.enqueue(1); queue.enqueue(1); let index = 0; while(index < n - 2) { index += 1; // 出队列一个元素 const delItem = queue.dequeue(); // 获取头部值 const headItem = queue.head(); const nextItem = delItem + headItem; queue.enqueue(nextItem); } return queue.tail(); } console.log(fibonacci(9)); // 34
(3)用队列实现一个栈
要求:用两个队列实现一个栈
分析:使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下:
- 两个队列,一个备份队列
emptyQueue
,一个是数据队列dataQueue
; - 在确认栈顶时,依次
dequeue
至备份队列,置换备份队列和数据队列的引用即可
class QueueStack { constructor() { this.queue_1 = new Queue(); this.queue_2 = new Queue(); this._dataQueue = null; // 放数据的队列 this._emptyQueue = null; // 空队列,备份使用 } // 确认哪个队列放数据,哪个队列做备份空队列 _initQueue() { if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } else if (this.queue_1.isEmpty()) { this._dataQueue = this.queue_2; this._emptyQueue = this.queue_1; } else { this._dataQueue = this.queue_1; this._emptyQueue = this.queue_2; } }; push(item) { this.init_queue(); this._dataQueue.enqueue(item); }; peek() { this.init_queue(); return this._dataQueue.tail(); } pop() { this.init_queue(); while (this._dataQueue.size() > 1) { this._emptyQueue.enqueue(this._dataQueue.dequeue()); } return this._dataQueue.dequeue(); }; };
学习了栈和队列这类简单的数据结构,我们会发现。 数据结构并没有之前想象中那么神秘,它们只是规定了这类数据结构的操作方式:栈只能对栈顶进行操作,队列只能在尾部添加在头部弹出;且它们不关心内部的元素状态。
个人认为,学习数据结构是为了提高我们通过代码建模的能力,这也是任何一门编程语言都通用的知识体系,优秀编码者必学之。
以上所述就是小编给大家介绍的《JS数据结构与算法_栈&队列》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。