假设理解 big o 表示法。 javascript 中有示例。资料参考 gayle laakmann mcdowell 的《cracking the coding interview》
今天，我们将探讨两种基本的数据结构：堆栈和队列。我们将深入研究它们的概念、用例，并使用经典和基于原型的方法在 javascript 中实现它们。
堆栈：后进先出 (lifo)
想象一下一堆煎饼——你最后放在上面的一个是你第一个吃的。这正是堆栈数据结构的工作原理。它遵循后进先出（lifo）原则.
关键操作
push(item): 将一个项目添加到堆栈顶部pop()：从堆栈中删除顶部项目peek()：返回顶部项目而不删除它isempty()：检查栈是否为空
使用案例
堆栈在涉及以下场景时特别有用：
递归算法文本编辑器中的撤消机制
javascript 实现
经典面向对象编程
class stack { constructor() { this.items = []; } push(element) { this.items.push(element); } pop() { if (this.isempty()) { return "stack is empty"; } return this.items.pop(); } peek() { if (this.isempty()) { return "stack is empty"; } return this.items[this.items.length - 1]; } isempty() { return this.items.length === 0; } size() { return this.items.length; } clear() { this.items = []; }}
基于原型
function stack() { this.items = [];}stack.prototype.push = function(element) { this.items.push(element);};stack.prototype.pop = function() { if (this.isempty()) { return "stack is empty"; } return this.items.pop();};stack.prototype.peek = function() { if (this.isempty()) { return "stack is empty"; } return this.items[this.items.length - 1];};stack.prototype.isempty = function() { return this.items.length === 0;};stack.prototype.size = function() { return this.items.length;};stack.prototype.clear = function() { this.items = [];};
队列：先进先出 (fifo)
现在，让我们将注意力转移到队列上。与堆栈不同，队列遵循先进先出（fifo）原则。想象一下音乐会场地的排队——第一个到达的人就是第一个进入的人。
关键操作
enqueue(item): 将一个项目添加到队列末尾dequeue()：从队列中删除第一个项目peek()：返回第一项而不删除它isempty()：检查队列是否为空
使用案例
队列常用于：
广度优先搜索算法任务调度
javascript 实现
经典面向对象编程
class node { constructor(data) { this.data = data; this.next = null; }}class queue { constructor() { this.start = null; this.end = null; this.size = 0; } enqueue(element) { const newnode = new node(element); if (this.isempty()) { this.start = newnode; this.end = newnode; } else { this.end.next = newnode; this.end = newnode; } this.size++; } dequeue() { if (this.isempty()) { return "queue is empty"; } const removeddata = this.start.data; this.start = this.start.next; this.size--; if (this.isempty()) { this.end = null; } return removeddata; } peek() { if (this.isempty()) { return "queue is empty"; } return this.start.data; } isempty() { return this.size === 0; } getsize() { return this.size; } clear() { this.start = null; this.end = null; this.size = 0; }}
基于原型
function Node(data) { this.data = data; this.next = null;}function Queue() { this.start = null; this.end = null; this.size = 0;}Queue.prototype.enqueue = function(element) { const newNode = new Node(element); if (this.isEmpty()) { this.start = newNode; this.end = newNode; } else { this.end.next = newNode; this.end = newNode; } this.size++;};Queue.prototype.dequeue = function() { if (this.isEmpty()) { return "Queue is empty"; } const removedData = this.start.data; this.start = this.start.next; this.size--; if (this.isEmpty()) { this.end = null; } return removedData;};Queue.prototype.peek = function() { if (this.isEmpty()) { return "Queue is empty"; } return this.start.data;};Queue.prototype.isEmpty = function() { return this.size === 0;};Queue.prototype.getSize = function() { return this.size;};Queue.prototype.clear = function() { this.start = null; this.end = null; this.size = 0;};
绩效分析
堆栈和队列都提供 o(1) 有效实现时，其核心操作（堆栈的压入/弹出、队列的入队/出队）的时间复杂度。这使得它们在特定用例中具有高性能。
它们都为许多常见的编程问题提供了优雅的解决方案，并构成了更复杂的数据结构和算法的基础。通过在 javascript 中理解和实现这些结构，您就可以很好地解决各种 leetcode/算法问题 ?.
以上就是后进先出还是先进先出？堆栈/队列指南的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1490630.html
微信扫一扫 
支付宝扫一扫 
