你如何在JavaScript中实现堆栈和队列？
在JavaScript中实现堆栈和队列的最佳方式是什么？
我正在寻找分stream码algorithm，我将需要这些数据结构。
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有push和pop方法，它们在普通的Javascript数组对象上运行。
对于队列，看这里：
http://safalra.com/web-design/javascript/queues/
可以使用push和shift方法或者数组对象的unshift和pop方法在JavaScript中实现队列。 虽然这是实现队列的一种简单方法，但对于大型队列来说效率却非常低 – 因为这些方法在数组上运行，所以在每次调用数组时，shift和unshift方法都会移动数组中的每个元素。
Queue.js是一个简单且高效的JavaScript队列实现，它的出列函数以分期固定的时间运行。 因此，对于更大的队列，它可以比使用数组快得多。
arrays。
堆栈：
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();
如果你想创build自己的数据结构，你可以build立自己的：
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; };
我使用链接列表的堆栈和队列的实现
// 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();
否则你可以使用两个数组来实现队列数据结构。
var temp_stack = new Array(); var stack = new Array(); temp_stack.push(1); temp_stack.push(2); temp_stack.push(3);
如果我现在popup元素，那么输出将是3,2,1。 但是我们想要FIFO结构，所以你可以做到以下几点。
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
/*------------------------------------------------------------------ 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))
Javascript中的常规数组结构是一个堆栈（先进先出），也可以用作队列（先进先出），具体取决于您所做的调用。
查看这个链接，看看如何使一个数组像一个队列：
队列
无arrays
//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; } }
Javascriptarrays转换（）是缓慢，尤其是当持有很多元素。 我知道有两种方法来实现队列的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（）与Array.shift（）
http://jsperf.com/rapidqueue-shift-vs-array-shift
正如你所看到的，大数据集显着快了
这是一个相当简单的队列实现，有两个目的：
- 与array.shift（）不同，你知道这个出列方法需要一个固定的时间（O（1））。
- 为了提高速度，这种方法比链表方法使用更less的分配。
堆栈实现仅与第二个目标共享。
// Queue function Queue() { this.q = new Array(5); this.first = 0; this.size = 0; } Queue.prototype.enqueue = function(a) { var other; if (this.size == this.q.length) { other = new Array(this.size*2); for (var i = 0; i < this.size; i++) { other[i] = this.q[(this.first+i)%this.size]; } this.first = 0; this.q = other; } this.q[(this.first+this.size)%this.q.length] = a; this.size++; }; Queue.prototype.dequeue = function() { if (this.size == 0) return undefined; this.size--; var ret = this.q[this.first]; this.first = (this.first+1)%this.q.length; return ret; }; Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; }; Queue.prototype.isEmpty = function() { return this.size == 0; }; // Stack function Stack() { this.s = new Array(5); this.size = 0; } Stack.prototype.push = function(a) { var other; if (this.size == this.s.length) { other = new Array(this.s.length*2); for (var i = 0; i < this.s.length; i++) other[i] = this.s[i]; this.s = other; } this.s[this.size++] = a; }; Stack.prototype.pop = function() { if (this.size == 0) return undefined; return this.s[--this.size]; }; Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };
这里是链接列表版本的一个队列，也包含最后一个节点，正如@perkins所build议的那样，也是最合适的。
// 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; };
如果你用push（）和pop（）函数理解栈，那么队列只是使其中的一个操作具有相反的意义。 push（）的对象是unshift（），pop（）是es（）。 然后：
//classic stack var stack = []; stack.push("first"); // push inserts at the end stack.push("second"); stack.push("last"); stack.pop(); //pop takes the "last" element //One way to implement queue is to insert elements in the oposite sense than a stack var queue = []; queue.unshift("first"); //unshift inserts at the beginning queue.unshift("second"); queue.unshift("last"); queue.pop(); //"first" //other way to do queues is to take the elements in the oposite sense than stack var queue = []; queue.push("first"); //push, as in the stack inserts at the end queue.push("second"); queue.push("last"); queue.shift(); //but shift takes the "first" element
你可以根据这个概念使用你自己的自定义类，这里是你可以使用的代码片段
/* * 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();
创build一对提供各种数据结构（push，pop，peek等）的各种方法的类。 现在执行这些方法。 如果你熟悉栈/队列背后的概念，这应该是非常简单的。 你可以用一个数组和一个带有链表的队列来实现堆栈，尽pipe肯定还有其他方法可以解决这个问题。 Javascript会让这个变得简单，因为它是弱types的，所以你甚至不用担心genericstypes，如果你用Java或者C＃实现的话，你将不得不这么做。
var x = 10; var y = 11; var Queue = new Array(); Queue.unshift(x); Queue.unshift(y); console.log(Queue) // Output [11, 10] Queue.pop() console.log(Queue) // Output [11]
