在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
数组是Javascript中的堆栈。只需使用arr.push(x)和y = arr.pop()。
下面是用Javascript实现队列的最简单方法，对于enqueue(x)和y = dequeue()，它的平摊时间都是O(1)。它使用从插入索引到元素的映射。
function newQueue() {
return {
headIdx: 0,
tailIdx: 0,
elts: {},
enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,
dequeue: () => {
if (queue.headIdx == queue.tailIdx) {
throw new Error("Queue is empty");
}
return queue.elts[queue.headIdx++];
},
size: () => queue.tailIdx - queue.headIdx,
isEmpty: () => queue.tailIdx == queue.headIdx
};
}
使用链表实现的队列比这种基于映射的方法更有效，使用循环缓冲区实现的队列比这种基于映射的方法更有效，但这两种数据结构的实现更复杂(特别是循环缓冲区数据结构)。
其他回答
在我看来，内建数组对于堆栈来说是很好的。如果你想在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
数组是Javascript中的堆栈。只需使用arr.push(x)和y = arr.pop()。
下面是用Javascript实现队列的最简单方法，对于enqueue(x)和y = dequeue()，它的平摊时间都是O(1)。它使用从插入索引到元素的映射。
function newQueue() {
return {
headIdx: 0,
tailIdx: 0,
elts: {},
enqueue: (elt) => queue.elts[queue.tailIdx++] = elt,
dequeue: () => {
if (queue.headIdx == queue.tailIdx) {
throw new Error("Queue is empty");
}
return queue.elts[queue.headIdx++];
},
size: () => queue.tailIdx - queue.headIdx,
isEmpty: () => queue.tailIdx == queue.headIdx
};
}
使用链表实现的队列比这种基于映射的方法更有效，使用循环缓冲区实现的队列比这种基于映射的方法更有效，但这两种数据结构的实现更复杂(特别是循环缓冲区数据结构)。
/*------------------------------------------------------------------
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))
正如其他答案中解释的那样，堆栈实现是微不足道的。
然而，我在这个线程中没有找到任何满意的答案，所以我自己做了一个队列。
在这个线程中有三种类型的解决方案:
数组——在大型数组上使用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代码。
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技巧”
推荐文章
- 使用jQuery改变输入字段的类型
- 在JavaScript中，什么相当于Java的Thread.sleep() ?
- 使用jQuery以像素为整数填充或边距值
- 检查是否选择了jQuery选项，如果没有选择默认值
- Next.js React应用中没有定义Window
- 如何重置笑话模拟函数调用计数之前，每次测试
- 如何强制一个功能React组件渲染?
- 在javascript中从平面数组构建树数组
- 将Dropzone.js与其他字段集成到现有的HTML表单中
- 如何在AngularJS中观察路由变化?
- JavaScript DOM删除元素
- 将dd-mm-yyyy字符串转换为日期
- Javascript复选框onChange
- Javascript函数前导bang !语法
- 如何在页面上遍历所有DOM元素?
