数据结构-js实现栈和队列 Dear 丶 2022-01-19 02:55 228阅读 0赞 我们都知道数据结构对我们非常重要,我在几场笔试题中遇到了非常多的有关数据结构的问题。因为我学习数据结构在一年多以前了,有点忘了,所以今天想好好温习一下数据结构的知识,先从简单的数据结构说起吧。 1. 栈 ### 我们都知道栈是一个坟场重要的数据的一种结构,它在我们的计算机很多方面都用到了,也包括我们的调用栈之类的,都有有关栈的知识。我们先说一下栈。网上有好多有数组的方法实现的,那样太简单了,但是我不想那样,因为我想自己实现一个,不想用数组的API。 ### * 栈的特点 * 后进先出(LIFO)(先进后出) * 只允许操作栈顶,不能操作栈底 * 栈示例 偷偷地到了一张图,如有侵权马上撤回。我就不多介绍栈了,相信大家都很清楚。 我们就来说一下栈的操作吧。 1. 初始化栈(init、构造函数) 2. 获取栈顶元素(Top) 3. 出栈 (Pop) 4. 入栈 (Push) 5. 获取栈的长度 (Length) 6. 判断栈是否为空 (isEmpty) 7. 清空栈 (Clear) 8. 输出栈内元素 (List) 我罗列的可能不清楚或者是不专业,请大家多多指正。(这只是我个人理解的栈的实现) class Stack { constructor(){ this.stacks = []; this.length = 0; } Top(){ return this.stacks[this.length - 1]; } Pop(){ return this.stacks.splice(-- this.length, 1)[0]; } Push(val){ this.stacks[this.length ++] = val; } Length(){ return this.length; } isEmpty(){ return this.length === 0; } Clear(){ this.stacks = []; this.length = 0; } List(){ for (var i = this.length - 1; i >= 0; i --) { console.log(this.stacks[i]); } } } 复制代码 我们来验证一下 console.log('-------------栈-----------------'); let stack = new Stack(); console.log("为空" + stack.isEmpty()); console.log("长度" + stack.Length()); stack.Push(0); stack.Push(1); stack.Push(2); console.log("长度" + stack.Length()); stack.List(); console.log("栈顶元素" + stack.Top()); console.log("出栈" + stack.Pop()); console.log("出栈" + stack.Pop()); console.log("栈顶元素" + stack.Top()); stack.Clear(); console.log("清栈"); console.log("长度" + stack.Length()); stack.List(); 复制代码 我觉得栈是一种思想,对数据的管理或者是操作的方式,我觉得每一个人都有每一个人实现的方式和对栈的理解,所以我觉得不必非得按照什么样的格式,只要实现了这样一个操作就行。 * 栈的应用 * 进制转换 * 括号或者是成对的匹配问题 * 等等 前面聊完了栈,那么就一定有一个跟它思想类似的队列要说一下。下面我们来聊一聊队列。 1. 队列 * 队列在我们的计算机中也是大量的应用,比如我们的消息队列之类的。 * 特点 * 先进先出(FIFO) * 队尾插入,队头删除 * 实例 就像是我们平常的排队一样。 * 基本操作 1. 初始化(构造函数、init) 2. 入队(EnQueue) 3. 出队(DeQueue) 4. 队头元素(Top) 5. 长度(Length) 6. 判断队是否为空(QueueEmpty) 7. 输出队内元素(List) 8. 清空队列(ClearQueue) * 代码 class Queue{ constructor(){ this.queue = []; this.length = 0; } EnQueue(val){ this.queue[this.length ++] = val; } DeQueue(){ this.length --; return this.queue.splice(0, 1)[0]; } List(){ for (var i = 0; i < this.length; i++) { console.log( this.queue[i] ); } } Top(){ return this.queue[0]; } Length(){ return this.length; } QueueEmpty(){ return this.length === 0; } ClearQueue(){ this.queue = []; this.length = 0; } } 复制代码 * 操作示例 let queue = new Queue(); console.log("长度" + queue.Length()); console.log("为空" + queue.QueueEmpty()); queue.EnQueue(0); queue.EnQueue(1); queue.EnQueue(2); console.log("长度" + queue.Length()); console.log("队头" + queue.Top()); console.log("出队" + queue.DeQueue()); console.log("出队" + queue.DeQueue()); console.log("队头" + queue.Top()); queue.List(); queue.ClearQueue(); console.log('清空队列'); console.log("长度" + queue.Length()); console.log("为空" + queue.QueueEmpty()); 复制代码 * 输出 * 遗憾 队列还有好几种,比如说循环队列,就是队头、队尾两个指针,用能力的人可以实现以下。 * 总结 1. 这次算是自己的温习,也想让大神们监督和指出错误。好久没有写过栈和队列的实现了,记得一年以前在上大二的时候,我们用C语言实现栈和队列,现在想起来还意犹未尽。记得那时候用队列和栈实现一个停车场进出车的功能。 2. 写这篇文章的时候心里很不踏实,总感觉哪里写的不对,希望不要误人子弟,也希望大神们能指出我的错误,能让我更加的认识数据结构与栈和队列。 转载于:https://juejin.im/post/5ce557f8e51d45777621badf
还没有评论,来说两句吧...