如何在JavaScript中实现堆栈和队列？

Question

在JavaScript中实现Stack和Queue的最佳方法是什么？

我正在寻找分流码算法,我将需要这些数据结构.

Answer 1

var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

取自" 你可能不知道的9个javascript提示 "

Answer 2

Javascript具有push和pop方法,它们在普通的Javascript数组对象上运行.

对于队列,请看这里:

http://safalra.com/web-design/javascript/queues/

可以使用push和shift方法或者数组对象的unshift和pop方法在JavaScript中实现队列.虽然这是实现队列的一种简单方法,但对于大型队列来说效率非常低 - 因为方法在数组上运行,shift和unshift方法每次调用时都会移动数组中的每个元素.

Queue.js是一个简单而有效的JavaScript队列实现,其出队函数以分摊的常量时间运行.因此,对于较大的队列,它可能比使用数组快得多.

Answer 3

阵列.

堆:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

队列:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();

Answer 4

如果您想创建自己的数据结构,可以构建自己的数据结构:

var Stack = function(){
  this.top = null;
  this.size = 0;
};

var Node = function(data){
  this.data = data;
  this.previous = null;
};

Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.previous = this.top;
  this.top = node;
  this.size += 1;
  return this.top;
};

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

对于队列:

var Queue = function() {
  this.first = null;
  this.size = 0;
};

var Node = function(data) {
  this.data = data;
  this.next = null;
};

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};

Answer 5

我的实施Stack和Queue使用Linked List

// Linked List
function Node(data) {
  this.data = data;
  this.next = null;
}

// Stack implemented using LinkedList
function Stack() {
  this.top = null;
}

Stack.prototype.push = function(data) {
  var newNode = new Node(data);

  newNode.next = this.top; //Special attention
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null;
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Queue implemented using LinkedList
function Queue() {
  this.head = null;
  this.tail = null;
}

Queue.prototype.enqueue = function(data) {
  var newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode;
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();

Answer 6

Javascript数组shift()特别是在持有许多元素时很慢.我知道两种方法来实现具有摊销的O(1)复杂性的队列.

首先是使用循环缓冲和表加倍.我以前实现过这个.你可以在这里看到我的源代码 https://github.com/kevyuu/rapid-queue

第二种方法是使用两个堆栈.这是具有两个堆栈的队列的代码

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

这是使用jsPerf进行性能比较

CircularQueue.shift()vs Array.shift()

http://jsperf.com/rapidqueue-shift-vs-array-shift

正如您所看到的,使用大型数据集会明显加快速度

Answer 7

如其他答案中所述，堆栈实现是微不足道的。

但是，我在这个线程中没有找到任何令人满意的答案来在 javascript 中实现队列，所以我自己做了一个。

此线程中有三种类型的解决方案：

• 数组 - 最糟糕的解决方案，array.shift()在大型数组上使用效率非常低。
• 链表 - 它是 O(1) 但为每个元素使用一个对象有点过分，特别是如果它们很多并且它们很小，比如存储数字。
• 延迟移位数组 - 它包括将索引与数组相关联。当元素出队时，索引向前移动。当索引到达数组的中间时，数组被一分为二以去除前半部分。

延迟移位数组是我心目中最满意的解决方案，但它们仍将所有内容存储在一个大的连续数组中，这可能会出现问题，并且在对数组进行切片时应用程序会错开。

我使用小数组的链表（每个最多 1000 个元素）做了一个实现。数组的行为类似于延迟移位数组，只是它们从不切片：当数组中的每个元素都被删除时，数组会被简单地丢弃。

该软件包位于具有基本 FIFO 功能的npm上，我最近才推送它。代码分为两部分。

这是第一部分

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

这是主Queue类：

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

: X可以轻松删除类型注释 ( ) 以获取 ES6 javascript 代码。

Answer 8

我认为实现堆栈和队列的最干净的方法应该是使用一个允许从两端添加和删除的容器，然后限制其一端的功能，这可以通过 JavaScript 中的一个简单数组来完成。

//封装时在堆栈容器中使用的语句

// Allow push and pop from the same end
array.push(element);
array.pop();

//封装时在队列容器中使用的语句

// Allow push and pop from different ends
array.push(element);
array.shift();

Answer 9

您可以通过多种方式在Javascript中实现堆栈和队列.上面的大多数答案是非常浅的实现,我会尝试实现更可读的东西(使用es6的新语法功能)和健壮.

这是堆栈实现:

class Stack {
  constructor(...items){
    this._items = []

    if(items.length>0)
      items.forEach(item => this._items.push(item) )

  }

  push(...items){
    //push item to the stack
     items.forEach(item => this._items.push(item) )
     return this._items;

  }

  pop(count=0){
    //pull out the topmost item (last item) from stack
    if(count===0)
      return this._items.pop()
     else
       return this._items.splice( -count, count )
  }

  peek(){
    // see what's the last item in stack
    return this._items[this._items.length-1]
  }

  size(){
    //no. of items in stack
    return this._items.length
  }

  isEmpty(){
    // return whether the stack is empty or not
    return this._items.length==0
  }

  toArray(){
    return this._items;
  }
}

这就是你如何使用堆栈:

let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3

如果您想查看有关此实现的详细说明以及如何进一步改进,可以在此处阅读:http://jschap.com/data-structures-in-javascript-stack/

这是es6中队列实现的代码:

class Queue{
 constructor(...items){
   //initialize the items in queue
   this._items = []
   // enqueuing the items passed to the constructor
   this.enqueue(...items)
 }

  enqueue(...items){
    //push items into the queue
    items.forEach( item => this._items.push(item) )
    return this._items;
  }

  dequeue(count=1){
    //pull out the first item from the queue
    this._items.splice(0,count);
    return this._items;
  }

  peek(){
    //peek at the first item from the queue
    return this._items[0]
  }

  size(){
    //get the length of queue
    return this._items.length
  }

  isEmpty(){
    //find whether the queue is empty or no
    return this._items.length===0
  }
}

以下是如何使用此实现:

let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3

要了解如何实现这些数据结构以及如何进一步改进这些数据结构的完整教程,您可能需要浏览jschap.com上的"在javascript中使用数据结构"系列.这是队列的链接 - http://jschap.com/playing-data-structures-javascript-queues/

Answer 10

您可以根据此概念使用自己的自定义类，这里是您可以用来完成工作的代码段

/*
*   Stack implementation in JavaScript
*/



function Stack() {
  this.top = null;
  this.count = 0;

  this.getCount = function() {
    return this.count;
  }

  this.getTop = function() {
    return this.top;
  }

  this.push = function(data) {
    var node = {
      data: data,
      next: null
    }

    node.next = this.top;
    this.top = node;

    this.count++;
  }

  this.peek = function() {
    if (this.top === null) {
      return null;
    } else {
      return this.top.data;
    }
  }

  this.pop = function() {
    if (this.top === null) {
      return null;
    } else {
      var out = this.top;
      this.top = this.top.next;
      if (this.count > 0) {
        this.count--;
      }

      return out.data;
    }
  }

  this.displayAll = function() {
    if (this.top === null) {
      return null;
    } else {
      var arr = new Array();

      var current = this.top;
      //console.log(current);
      for (var i = 0; i < this.count; i++) {
        arr[i] = current.data;
        current = current.next;
      }

      return arr;
    }
  }
}

并使用您的控制台进行检查，然后逐行尝试这些方法。

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();

Answer 11

/*------------------------------------------------------------------ 
 Defining Stack Operations using Closures in Javascript, privacy and
 state of stack operations are maintained

 @author:Arijt Basu
 Log: Sun Dec 27, 2015, 3:25PM
 ------------------------------------------------------------------- 
 */
var stackControl = true;
var stack = (function(array) {
        array = [];
        //--Define the max size of the stack
        var MAX_SIZE = 5;

        function isEmpty() {
            if (array.length < 1) console.log("Stack is empty");
        };
        isEmpty();

        return {

            push: function(ele) {
                if (array.length < MAX_SIZE) {
                    array.push(ele)
                    return array;
                } else {
                    console.log("Stack Overflow")
                }
            },
            pop: function() {
                if (array.length > 1) {
                    array.pop();
                    return array;
                } else {
                    console.log("Stack Underflow");
                }
            }

        }
    })()
    // var list = 5;
    // console.log(stack(list))
if (stackControl) {
    console.log(stack.pop());
    console.log(stack.push(3));
    console.log(stack.push(2));
    console.log(stack.pop());
    console.log(stack.push(1));
    console.log(stack.pop());
    console.log(stack.push(38));
    console.log(stack.push(22));
    console.log(stack.pop());
    console.log(stack.pop());
    console.log(stack.push(6));
    console.log(stack.pop());
}
//End of STACK Logic

/* Defining Queue operations*/

var queue = (function(array) {
    array = [];
    var reversearray;
    //--Define the max size of the stack
    var MAX_SIZE = 5;

    function isEmpty() {
        if (array.length < 1) console.log("Queue is empty");
    };
    isEmpty();

    return {
        insert: function(ele) {
            if (array.length < MAX_SIZE) {
                array.push(ele)
                reversearray = array.reverse();
                return reversearray;
            } else {
                console.log("Queue Overflow")
            }
        },
        delete: function() {
            if (array.length > 1) {
                //reversearray = array.reverse();
                array.pop();
                return array;
            } else {
                console.log("Queue Underflow");
            }
        }
    }



})()

console.log(queue.insert(5))
console.log(queue.insert(3))
console.log(queue.delete(3))

Answer 12

正如许多人所说：原生数组push和pop作为堆栈操作很好，但用作shift队列提取操作意味着数组中剩余的元素需要移动，这可能会很慢。在kevinyu 的答案中使用两个堆栈来创建队列的想法是修复它的好主意，当然这也可以使用本机数组堆栈来完成。（注意：实际上Yuki-Dreamer 已经有一个答案可以做到这一点，尽管比我的版本不那么紧凑。）

这是一个使用一些 ES5/ES6 功能的紧凑实现，它使队列对象的行为尽可能接近本机push/shift变体，除了每个操作需要摊销 O(1) 时间：

const queue = () => {
    const a = [], b = [];
    return {
        push: (...elts) => a.push(...elts),
        shift: () => {
            if (b.length === 0) {
                while (a.length > 0) { b.push(a.pop()) }
            }
            return b.pop();
        },
        get length() { return a.length + b.length }
    }
}

现在你可以这样做：

const q = queue();
q.push(8);
q.push(9);
q.push(10);
console.log(q.length);          // outputs 3
console.log(q.shift());         // outputs 8
q.push(11);
console.log(q.shift());         // outputs 9
console.log(q.shift());         // outputs 10
console.log(q.shift());         // outputs 11
console.log(q.shift());         // outputs undefined

该queue实现使用 的getter语法length，使其看起来像一个属性，并使用 Push的剩余参数语法，以允许一次推送多个内容。如果您不想这样做，可以将第 4 行替换为push: elt => a.push(elt),。（但是请注意，您不能像我自己首先尝试的那样将其替换为push: a.push,非常奇怪的结果：这是因为它会导致调用本机推送方法并将其设置this为队列对象。）

优化：这是代码速度的微小改进。将该while行替换为以下两行，以便在每次从ato传输时保存一次推送+弹出操作b：

                while (a.length > 1) { b.push(a.pop()) }
                return a.pop();

Answer 13

否则,您可以使用两个数组来实现队列数据结构.

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

如果我现在弹出元素,那么输出将是3,2,1.但我们需要FIFO结构,因此您可以执行以下操作.

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3

Answer 14

这是一个相当简单的队列实现,有两个目的:

• 与array.shift()不同,您知道此dequeue方法需要恒定时间(O(1)).
• 为了提高速度,此方法使用的链接比链接列表方法少得多.

堆栈实现仅共享第二个目标.

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };

Answer 15

答案有点晚了，但我认为这个答案应该在这里。这是使用稀疏数组幂的 O(1)enqueue和 O(1)队列实现。dequeue

JS 中的稀疏数组大多被忽视，但它们实际上是一个宝石，我们应该在一些关键任务中使用它们的力量。

所以这里是一个框架Queue实现，它扩展了Array类型并一直在 O(1) 中完成它的事情。

class Queue extends Array {
  constructor(){
    super()
    Object.defineProperty(this,"head",{ value   : 0
                                      , writable: true
                                      });
  }
  enqueue(x) {
    this.push(x);
    return this;
  }
  dequeue() {
    var first;
    return this.head < this.length ? ( first = this[this.head]
                                     , delete this[this.head++]
                                     , first
                                     )
                                   : void 0; // perfect undefined
  }
  peek() {
    return this[this.head];
  }
}

var q = new Queue();
console.log(q.dequeue());      // doesn't break
console.log(q.enqueue(10));    // add 10
console.log(q.enqueue("DIO")); // add "DIO" (Last In Line cCc R.J.DIO reis cCc)
console.log(q);                // display q
console.log(q.dequeue());      // lets get the first one in the line
console.log(q.dequeue());      // lets get DIO out from the line

.as-console-wrapper {
  max-height: 100% !important;
}

那么这里是否存在潜在的内存泄漏？不，我不这么认为。JS 稀疏数组是不连续的。因此，删除的项目不应成为数组内存占用的一部分。让 GC 为您完成它的工作。它是免费的。

一个潜在的问题是，length当您不断将项目放入队列时，该属性会无限增长。然而，仍然可以实现自动刷新（压缩）机制，以在长度达到某一值时启动。

编辑：

上面的代码虽然很好delete，但运算符虽然仍然是 O(1)，但速度很慢。此外，现代 JS 引擎经过如此优化，对于 <~25000 个项目来说，.shift()无论如何，工作时间复杂度为 O(1)。所以我们需要更好的东西。

在这种特殊情况下，随着发动机的发展，我们必须利用它们的新动力。下面的代码使用了链表，我相信它是截至 2021 年最快、最安全的现代 JS 队列结构。

class Queue {
  #head;
  #last;
  constructor(){
    this.#head;
    this.#last;
  };
  enqueue(value){
    var link = {value, next: void 0};
    this.#last = this.#head ? this.#last.next = link
                            : this.#head      = link;
  }
  dequeue(){
    var first;
    return this.#head && ( first = this.#head.value
                         , this.#head = this.#head.next
                         , first
                         );
  }
  peek(){
    return this.#head && this.#head.value;
  }
};

这是一个非常快的队列结构，并使用私有类字段来隐藏关键变量以防止窥探。