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

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


当前回答

数组。

栈:

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

其他回答

/*------------------------------------------------------------------ 
 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))
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技巧”

没有数组(年代)

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

}

如果有人需要它,你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript,它有一个队列和堆栈,它支持javascript和typescript,它是通用的,所以你可以用你自己的值类型;)

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