在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
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方法被调用，并设置为队列对象。)
其他回答
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方法被调用，并设置为队列对象。)
下面是一个相当简单的队列实现，有两个目标:
与array.shift()不同，您知道这个出队列方法需要常数时间(O(1))。 为了提高速度，这种方法使用的分配比链表方法少得多。
堆栈实现只共享第二个目标。
// 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; };
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技巧”
在我看来，内建数组对于堆栈来说是很好的。如果你想在TypeScript中使用Queue，这里有一个实现
/**
* A Typescript implementation of a queue.
*/
export default class Queue {
private queue = [];
private offset = 0;
constructor(array = []) {
// Init the queue using the contents of the array
for (const item of array) {
this.enqueue(item);
}
}
/**
* @returns {number} the length of the queue.
*/
public getLength(): number {
return (this.queue.length - this.offset);
}
/**
* @returns {boolean} true if the queue is empty, and false otherwise.
*/
public isEmpty(): boolean {
return (this.queue.length === 0);
}
/**
* Enqueues the specified item.
*
* @param item - the item to enqueue
*/
public enqueue(item) {
this.queue.push(item);
}
/**
* Dequeues an item and returns it. If the queue is empty, the value
* {@code null} is returned.
*
* @returns {any}
*/
public dequeue(): any {
// if the queue is empty, return immediately
if (this.queue.length === 0) {
return null;
}
// store the item at the front of the queue
const item = this.queue[this.offset];
// increment the offset and remove the free space if necessary
if (++this.offset * 2 >= this.queue.length) {
this.queue = this.queue.slice(this.offset);
this.offset = 0;
}
// return the dequeued item
return item;
};
/**
* Returns the item at the front of the queue (without dequeuing it).
* If the queue is empty then {@code null} is returned.
*
* @returns {any}
*/
public peek(): any {
return (this.queue.length > 0 ? this.queue[this.offset] : null);
}
}
这里有一个笑话测试
it('Queue', () => {
const queue = new Queue();
expect(queue.getLength()).toBe(0);
expect(queue.peek()).toBeNull();
expect(queue.dequeue()).toBeNull();
queue.enqueue(1);
expect(queue.getLength()).toBe(1);
queue.enqueue(2);
expect(queue.getLength()).toBe(2);
queue.enqueue(3);
expect(queue.getLength()).toBe(3);
expect(queue.peek()).toBe(1);
expect(queue.getLength()).toBe(3);
expect(queue.dequeue()).toBe(1);
expect(queue.getLength()).toBe(2);
expect(queue.peek()).toBe(2);
expect(queue.getLength()).toBe(2);
expect(queue.dequeue()).toBe(2);
expect(queue.getLength()).toBe(1);
expect(queue.peek()).toBe(3);
expect(queue.getLength()).toBe(1);
expect(queue.dequeue()).toBe(3);
expect(queue.getLength()).toBe(0);
expect(queue.peek()).toBeNull();
expect(queue.dequeue()).toBeNull();
});
希望有人觉得这有用，
欢呼,
Stu
/*------------------------------------------------------------------
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))
推荐文章
- 我如何使用Jest模拟JavaScript的“窗口”对象?
- 我如何等待一个承诺完成之前返回一个函数的变量?
- 在JavaScript中根据键值查找和删除数组中的对象
- 使嵌套JavaScript对象平放/不平放的最快方法
- 如何以及为什么'a'['toUpperCase']()在JavaScript工作?
- 有Grunt生成index.html不同的设置
- 文档之间的区别。addEventListener和window。addEventListener?
- 如何检查动态附加的事件监听器是否存在?
- 如何写setTimeout与参数Coffeescript
- 将JavaScript字符串中的多个空格替换为单个空格
- 多维数组如何在内存中格式化?
- JavaScript: override alert()
- 重置setTimeout
- 如何确保<select>表单字段被禁用时提交?
- jQuery有不聚焦的方法吗?
