在JavaScript中实现堆栈和队列的最佳方法是什么?

我想做调车场算法我需要这些数据结构。


当前回答

你可以基于这个概念使用你自己的自定义类,这里是你可以用来做这些事情的代码片段

/*
*   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();

其他回答

有很多方法可以在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/

没有数组(年代)

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

下面是一个队列的链表版本,它也包括最后一个节点,这是@perkins建议的,也是最合适的。

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = 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){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

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

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};

As many have said: native array using push and pop is fine for a stack, but using shift for taking elements from a queue means that the remaining elements need to move, which is potentially slow. The idea of using two stacks to make a queue in kevinyu's answer is a nice idea to fix it, and of course that can be done with native-array-stacks as well. (Edit: there was actually already an answer by Yuki-Dreamer that does this, albeit less compactly. I didn't notice it until now because it was unfairly downvoted.)

下面是一个使用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

队列实现对长度使用getter语法,使其看起来像一个属性,并对push使用rest参数语法,以允许一次推送多个内容。如果你不想这样做,你可以用push: elt => a.push(elt),替换第4行。(但是请注意,你不能用push: a.push替换它,就像我自己第一次尝试的那样,结果非常奇怪:这是因为它导致本机push方法被调用,并设置为队列对象。)

  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]