如何在JavaScript中实现栈(Stack)和队列(Queue)?
我想要使用逆波兰表达式算法,因此需要这些数据结构。
如何在JavaScript中实现栈(Stack)和队列(Queue)?
我想要使用逆波兰表达式算法,因此需要这些数据结构。
class QueueObject {
constructor () {
this.data = {}
this.head = 0
this.tail = 0
this.length = 0
}
enqueue (value) {
this.data[this.tail++] = value
this.length++
}
dequeue () {
let value
if (this.length > 0) {
this.length--
value = this.data[this.head]
delete this.data[this.head++]
} else {
this.head = 0
this.tail = 0
value = null
}
return value
}
refactor () {
if (this.head > 0) {
for (let i = this.head; i < this.tail; i++) {
this.data[i - this.head] = this.data[i]
delete this.data[i]
}
this.tail = this.length
this.head = 0
}
}
}
在我看来,内置数组对于堆栈来说是可以的。如果你想在TypeScript中使用队列,这里有一个实现
/**
* 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);
}
}
这里是一个关于 Jest
的测试
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();
});
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]
数组在Javascript中是一个栈。只需使用arr.push(x)
和y = arr.pop()
即可。
这里是在Javascript中实现队列的最简单方法,具有O(1)
的平均时间复杂度,用于enqueue(x)
和y = dequeue()
。它使用从插入索引到元素的映射。
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
};
}
在实现BFS时,我遇到了这个线程。在想为什么性能如此差的情况下,我进行了一些研究。array.shift()通常以O(n)的速度运行,这将使我的BFS运行时间从O(V+E)增加到O(V^2+E)。
与其从头开始实现队列,不如使用npm包double-ended-queue,它与先前使用的数组方法兼容,并且运行良好。deque可以用作堆栈或队列。
//import package
import Deque from 'double-ended-queue';
//create queue
let queue = new Deque();
//append
queue.push(item);
//dequeue (get first item inserted)
let firstItem = queue.shift();
//pop (get last item inserted)
let lastItem = queue.pop();
单向队列
这里使用了一个 map 来实现队列。由于插入顺序是 保证的,所以可以像数组一样迭代它。除此之外,这个想法与 Queue.js 非常相似。
我进行了一些简单的测试,但没有进行全面测试。我还添加了一些我认为不错的功能(通过数组构造)或易于实现的功能(例如 last()
和 first()
)。
下面是其简化版本/直观解释:
class Queue {
constructor() {
this.offset = 0
this.data = new Map()
}
enqueue(item) {
const current = this.offset + this.length()
this.data.set(current, item)
}
dequeue() {
if (this.length() > 0) {
this.data.delete(this.offset)
this.offset += 1
}
}
first() {
return this.data.get(this.offset)
}
last() {
return this.data.get(this.offset + this.length() - 1)
}
length() {
return this.data.size
}
}
Number.MAX_SAFE_INTEGER
的值)时,需要重新映射内存。此外,我认为添加数组构造很好,并且很好地看到了被入列和出列的值被返回。可以通过编写以下代码来解决这个问题:class Queue {
constructor() {
this.offset = 0
this.data = new Map()
if (arguments.length === 1) this._initializeFromArray(arguments[0])
}
enqueue(item) {
const current = this.offset + this.length()
this.data.set(current, item)
let result = this.data.get(current)
this._remapDataIfMaxMemoryViolation(current, Number.MAX_SAFE_INTEGER)
return result
}
dequeue() {
let result = undefined
if (this.length() > 0) {
result = this.data.get(this.offset)
this.data.delete(this.offset)
this.offset += 1
}
if (this.length() === 0) this.offset = 0
return result
}
first() {
return this.data.get(this.offset)
}
last() {
return this.data.get(this.offset + this.length() - 1)
}
length() {
return this.data.size
}
_remapDataIfMaxMemoryViolation(current, threshhold) {
if (current+1 === threshhold) {
const length = this.length()
this.offset = 0
for (const [key, value] of this.data) {
this.data.set(this.offset, value)
this.data.delete(key, value)
this.offset += 1
if (this.offset === length) break
}
}
}
_initializeFromArray(array) {
for (const value of array) {
this.data.set(this.offset, value)
this.offset += 1
}
}
}
l = console.log // I'm lazy with typing
q = new Queue()
l('enqueue', q.enqueue(1))
l('enqueue', q.enqueue(2))
l('enqueue', q.enqueue(3))
l('enqueue', q.enqueue("hello"))
l('enqueue', q.enqueue("monkey"))
l('show 5 elements: ', q.data)
l('length', q.length())
l('first', q.first())
l('last', q.last())
l('dequeue', q.dequeue())
l('dequeue', q.dequeue())
l('show 3 elements', q.data)
q._remapDataIfMaxMemoryViolation(q.length()+q.offset-1, 5)
l('show 3 remapped elements', q.data)
l(queue = new Queue([3,4,5,6,7,8,9]))
l(queue.data)
入队和出队操作都是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());
}
}
}
push
也是摊销O(1)时间:它偶尔需要将后备存储的大小加倍,这需要线性时间(但成本可以分摊到总操作次数上)。因此,如果您认为这不是O(1),那么push
也不是。 - njlarsson这是我实现的栈。
function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());
敬礼,
Javascript中堆栈和队列的实现如下:
堆栈:堆栈是一个对象容器,按照后进先出(LIFO)原则插入和删除对象。
队列:队列是一个对象容器(线性集合),按照先进先出(FIFO)原则插入和删除对象。
Unshift:该方法将一个或多个元素添加到数组的开头。
Shift:该方法从数组中删除第一个元素。
let stack = [];
stack.push(1);//[1]
stack.push(2);//[1,2]
stack.push(3);//[1,2,3]
console.log('It was inserted 1,2,3 in stack:', ...stack);
stack.pop(); //[1,2]
console.log('Item 3 was removed:', ...stack);
stack.pop(); //[1]
console.log('Item 2 was removed:', ...stack);
let queue = [];
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]
console.log('It was inserted 1,2,3 in queue:', ...queue);
queue.shift();// [2,3]
console.log('Item 1 was removed:', ...queue);
queue.shift();// [3]
console.log('Item 2 was removed:', ...queue);
如果有人需要的话,你可以使用这个NPM包https://www.npmjs.com/package/data-structures-typescript。它有一个队列和一个栈,支持JavaScript和TypeScript,而且是通用的,所以你可以用它来处理自己的值类型;)