在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
其他回答
有很多方法可以在Javascript中实现堆栈和队列。上面的大多数答案都是非常肤浅的实现，我将尝试实现一些更可读(使用es6的新语法特性)和更健壮的东西。
下面是堆栈实现:
class Stack {
constructor(...items){
this._items = []
if(items.length>0)
items.forEach(item => this._items.push(item) )
}
push(...items){
//push item to the stack
items.forEach(item => this._items.push(item) )
return this._items;
}
pop(count=0){
//pull out the topmost item (last item) from stack
if(count===0)
return this._items.pop()
else
return this._items.splice( -count, count )
}
peek(){
// see what's the last item in stack
return this._items[this._items.length-1]
}
size(){
//no. of items in stack
return this._items.length
}
isEmpty(){
// return whether the stack is empty or not
return this._items.length==0
}
toArray(){
return this._items;
}
}
下面是如何使用堆栈:
let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3
如果您想查看关于此实现的详细描述以及如何进一步改进，请阅读这里:http://jschap.com/data-structures-in-javascript-stack/
下面是es6中队列实现的代码:
class Queue{
constructor(...items){
//initialize the items in queue
this._items = []
// enqueuing the items passed to the constructor
this.enqueue(...items)
}
enqueue(...items){
//push items into the queue
items.forEach( item => this._items.push(item) )
return this._items;
}
dequeue(count=1){
//pull out the first item from the queue
this._items.splice(0,count);
return this._items;
}
peek(){
//peek at the first item from the queue
return this._items[0]
}
size(){
//get the length of queue
return this._items.length
}
isEmpty(){
//find whether the queue is empty or no
return this._items.length===0
}
}
下面是如何使用这个实现:
let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3
要完整地了解如何实现这些数据结构以及如何进一步改进这些数据结构，您可能需要阅读jschap.com上的“在javascript中处理数据结构”系列。这是队列的链接——http://jschap.com/playing-data-structures-javascript-queues/
正如其他答案中解释的那样，堆栈实现是微不足道的。
然而，我在这个线程中没有找到任何满意的答案，所以我自己做了一个队列。
在这个线程中有三种类型的解决方案:
数组——在大型数组上使用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代码。
你可以使用WeakMaps来实现ES6类中的私有属性，以及JavaScript语言中String属性和方法的好处，如下所示:
const _items = new WeakMap();
class Stack {
constructor() {
_items.set(this, []);
}
push(obj) {
_items.get(this).push(obj);
}
pop() {
const L = _items.get(this).length;
if(L===0)
throw new Error('Stack is empty');
return _items.get(this).pop();
}
peek() {
const items = _items.get(this);
if(items.length === 0)
throw new Error ('Stack is empty');
return items[items.length-1];
}
get count() {
return _items.get(this).length;
}
}
const stack = new Stack();
//now in console:
//stack.push('a')
//stack.push(1)
//stack.count => 2
//stack.peek() => 1
//stack.pop() => 1
//stack.pop() => "a"
//stack.count => 0
//stack.pop() => Error Stack is empty
/*------------------------------------------------------------------
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))
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技巧”
