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#.

下面是我使用链表实现的堆栈和队列:

// Linked List function Node(data) { this.data = data; this.next = null; } // Stack implemented using LinkedList function Stack() { this.top = null; } Stack.prototype.push = function(data) { var newNode = new Node(data); newNode.next = this.top; //Special attention this.top = newNode; } Stack.prototype.pop = function() { if (this.top !== null) { var topItem = this.top.data; this.top = this.top.next; return topItem; } return null; } Stack.prototype.print = function() { var curr = this.top; while (curr) { console.log(curr.data); curr = curr.next; } } // var stack = new Stack(); // stack.push(3); // stack.push(5); // stack.push(7); // stack.print(); // Queue implemented using LinkedList function Queue() { this.head = null; this.tail = null; } Queue.prototype.enqueue = function(data) { var newNode = new Node(data); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } } Queue.prototype.dequeue = function() { var newNode; if (this.head !== null) { newNode = this.head.data; this.head = this.head.next; } return newNode; } Queue.prototype.print = function() { var curr = this.head; while (curr) { console.log(curr.data); curr = curr.next; } } var queue = new Queue(); queue.enqueue(3); queue.enqueue(5); queue.enqueue(7); queue.print(); queue.dequeue(); queue.dequeue(); queue.print();

Javascript数组shift()很慢，特别是当包含很多元素时。我知道两种方法来实现平摊O(1)复杂度的队列。

首先是使用循环缓冲区和表加倍。我以前实现过这个。你可以在这里看到我的源代码 https://github.com/kevyuu/rapid-queue

第二种方法是使用两个堆栈。这是带有两个堆栈的队列的代码

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

这是使用jsPerf进行的性能比较

CircularQueue.shift() vs Array.shift()

http://jsperf.com/rapidqueue-shift-vs-array-shift

正如你所看到的，大数据集的速度要快得多

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

/*
*   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有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.

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技巧”