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

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


当前回答

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

单端队列

这是一个使用映射的队列。由于插入顺序得到了保证,所以可以像迭代数组一样迭代它。除此之外,它的思想与Queue.js非常相似。

我做了一些简单的测试,但还没有进行广泛的测试。我还添加了一些我认为很好的功能(通过数组构造)或易于实现(例如last()和first())。

它背后的简单版本/直觉如下:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
    }

    dequeue() {
        if (this.length() > 0) {
            this.data.delete(this.offset)
            this.offset += 1
        }
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }
}

简单版本的问题是,当内存索引超过9千万亿(Number.MAX_SAFE_INTEGER的值)时,需要重新映射内存。此外,我认为它可能很好有数组构造,它很高兴看到值正在进入队列和退出队列返回。可以通过编写以下代码来解释这一点:

class Queue {
    constructor() {
        this.offset = 0
        this.data = new Map()
        if (arguments.length === 1) this._initializeFromArray(arguments[0])
    }

    enqueue(item) {
        const current = this.offset + this.length()
        this.data.set(current, item)
        let result = this.data.get(current)
        this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
        return result
    }

    dequeue() {
        let result = undefined
        if (this.length() > 0) {
            result = this.data.get(this.offset)
            this.data.delete(this.offset)
            this.offset += 1
        }
        if (this.length() === 0) this.offset = 0
        return result
    }

    first() {
        return this.data.get(this.offset)
    }

    last() {
        return this.data.get(this.offset + this.length() - 1)
    }

    length() {
        return this.data.size
    }

    _remapDataIfMaxMemoryViolation(current, threshhold) {
        if (current+1 === threshhold) {
            const length = this.length()
            this.offset = 0
            for (const [key, value] of this.data) {
                this.data.set(this.offset, value)
                this.data.delete(key, value)
                this.offset += 1
                if (this.offset === length) break
            }       
        }
    }

    _initializeFromArray(array) {
        for (const value of array) {
            this.data.set(this.offset, value)
            this.offset += 1
        }
    }
}

我在Chrome开发控制台进行了一些测试,对完整版本进行了以下调用。

l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)

l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)

Javascript有push和pop方法,它们操作在普通的Javascript数组对象上。

关于排队,请看这里:

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

Queues can be implemented in JavaScript using either the push and shift methods or unshift and pop methods of the array object. Although this is a simple way to implement queues, it is very inefficient for large queues — because of the methods operate on arrays, the shift and unshift methods move every element in the array each time they are called. Queue.js is a simple and efficient queue implementation for JavaScript whose dequeue function runs in amortized constant time. As a result, for larger queues, it can be significantly faster than using arrays.

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方法被调用,并设置为队列对象。)

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