后进先出还是先进先出？

百变鹏仔 3天前 #JavaScript

文章标签后进

假设理解 big o 表示法。 javascript 中有示例。资料参考 gayle laakmann mcdowell 的《cracking the coding interview》

今天，我们将探讨两种基本的数据结构：堆栈和队列。我们将深入研究它们的概念、用例，并使用经典和基于原型的方法在 javascript 中实现它们。

堆栈：后进先出 (lifo)

想象一下一堆煎饼——你最后放在上面的一个是你第一个吃的。这正是堆栈数据结构的工作原理。它遵循后进先出（lifo）原则.

关键操作

使用案例

堆栈在涉及以下场景时特别有用：

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）原则。想象一下音乐会场地的排队——第一个到达的人就是第一个进入的人。

关键操作

使用案例

队列常用于：

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;};

绩效分析

堆栈和队列都提供css"> o(1)o(1)o(1) 有效实现时，其核心操作（堆栈的压入/弹出、队列的入队/出队）的时间复杂度。这使得它们在特定用例中具有高性能。

它们都为许多常见的编程问题提供了优雅的解决方案，并构成了更复杂的数据结构和算法的基础。通过在 javascript 中理解和实现这些结构，您就可以很好地解决各种 leetcode/算法问题 ?.

文章推荐

后进先出还是先进先出？

堆栈：后进先出 (lifo)

关键操作

使用案例

javascript 实现

经典面向对象编程

基于原型

队列：先进先出 (fifo)

关键操作

使用案例

javascript 实现

经典面向对象编程

基于原型

绩效分析

JavaScript如何获取宏控件数据？

JavaScript怎样读取宏控件数据？

JavaScript获取宏控件数据的技巧

探究JavaScript与Java的联系和区别

javascript:void(o)如何解决？