数组。

栈:

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

正如其他答案中解释的那样，堆栈实现是微不足道的。

然而，我在这个线程中没有找到任何满意的答案，所以我自己做了一个队列。

在这个线程中有三种类型的解决方案:

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

在我看来，延迟移位数组是最令人满意的解决方案，但它们仍然将所有内容存储在一个大的连续数组中，这可能会有问题，并且当数组被切片时，应用程序将错开。

我使用小数组的链表(每个最多1000个元素)实现。这些数组的行为类似于延迟移位数组，只是它们从未被切片:当数组中的每个元素都被移除时，该数组将被简单地丢弃。

这个包在npm上，具有基本的FIFO功能，我最近刚刚推送了它。代码分为两部分。

这是第一部分

/** 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代码。

如果你想创建自己的数据结构，你可以创建自己的:

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

没有数组(年代)

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

}

Create a pair of classes that provide the various methods that each of these data structures has (push, pop, peek, etc). Now implement the methods. If you're familiar with the concepts behind stack/queue, this should be pretty straightforward. You can implement the stack with an array, and a queue with a linked list, although there are certainly other ways to go about it. Javascript will make this easy, because it is weakly typed, so you don't even have to worry about generic types, which you'd have to do if you were implementing it in Java or C#.

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