在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
/*------------------------------------------------------------------
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))
其他回答
如果你正在寻找带有一些基本操作(基于链表)的堆栈和队列数据结构的ES6 OOP实现,那么它可能是这样的:
Queue.js
import LinkedList from '../linked-list/LinkedList';
export default class Queue {
constructor() {
this.linkedList = new LinkedList();
}
isEmpty() {
return !this.linkedList.tail;
}
peek() {
if (!this.linkedList.head) {
return null;
}
return this.linkedList.head.value;
}
enqueue(value) {
this.linkedList.append(value);
}
dequeue() {
const removedHead = this.linkedList.deleteHead();
return removedHead ? removedHead.value : null;
}
toString(callback) {
return this.linkedList.toString(callback);
}
}
Stack.js
import LinkedList from '../linked-list/LinkedList';
export default class Stack {
constructor() {
this.linkedList = new LinkedList();
}
/**
* @return {boolean}
*/
isEmpty() {
return !this.linkedList.tail;
}
/**
* @return {*}
*/
peek() {
if (!this.linkedList.tail) {
return null;
}
return this.linkedList.tail.value;
}
/**
* @param {*} value
*/
push(value) {
this.linkedList.append(value);
}
/**
* @return {*}
*/
pop() {
const removedTail = this.linkedList.deleteTail();
return removedTail ? removedTail.value : null;
}
/**
* @return {*[]}
*/
toArray() {
return this.linkedList
.toArray()
.map(linkedListNode => linkedListNode.value)
.reverse();
}
/**
* @param {function} [callback]
* @return {string}
*/
toString(callback) {
return this.linkedList.toString(callback);
}
}
上面例子中用于堆栈和队列的LinkedList实现可以在GitHub上找到。
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技巧”
使用两个堆栈构造一个队列。
O(1)用于入队和出队操作。
class Queue {
constructor() {
this.s1 = []; // in
this.s2 = []; // out
}
enqueue(val) {
this.s1.push(val);
}
dequeue() {
if (this.s2.length === 0) {
this._move();
}
return this.s2.pop(); // return undefined if empty
}
_move() {
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
}
}
/*------------------------------------------------------------------
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 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