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

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


当前回答

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

其他回答

下面是一个队列的链表版本,它也包括最后一个节点,这是@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;
};

数组。

栈:

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();
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技巧”

或者可以使用两个数组来实现队列数据结构。

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

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

如果我现在弹出元素,那么输出将是3 2 1。 但我们想先进先出结构,所以你可以做以下。

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

使用两个堆栈构造一个队列。

O(1)用于入队和出队操作。

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}