在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
在JavaScript中实现堆栈和队列的最佳方法是什么?
我想做调车场算法我需要这些数据结构。
当前回答
Javascript中的常规数组结构是一个堆栈(先入后出),也可以用作队列(先入先出),这取决于你所做的调用。
检查这个链接,看看如何让一个数组像一个队列:
队列
其他回答
下面是一个队列的链表版本,它也包括最后一个节点,这是@perkins建议的,也是最合适的。
// QUEUE Object Definition
var Queue = function() {
this.first = null;
this.last = null;
this.size = 0;
};
var Node = function(data) {
this.data = data;
this.next = null;
};
Queue.prototype.enqueue = function(data) {
var node = new Node(data);
if (!this.first){ // for empty list first and last are the same
this.first = node;
this.last = node;
} else { // otherwise we stick it on the end
this.last.next=node;
this.last=node;
}
this.size += 1;
return node;
};
Queue.prototype.dequeue = function() {
if (!this.first) //check for empty list
return null;
temp = this.first; // grab top of list
if (this.first==this.last) {
this.last=null; // when we need to pop the last one
}
this.first = this.first.next; // move top of list down
this.size -= 1;
return temp;
};
在我看来,内建数组对于堆栈来说是很好的。如果你想在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
下面是我使用链表实现的堆栈和队列:
// Linked List function Node(data) { this.data = data; this.next = null; } // Stack implemented using LinkedList function Stack() { this.top = null; } Stack.prototype.push = function(data) { var newNode = new Node(data); newNode.next = this.top; //Special attention this.top = newNode; } Stack.prototype.pop = function() { if (this.top !== null) { var topItem = this.top.data; this.top = this.top.next; return topItem; } return null; } Stack.prototype.print = function() { var curr = this.top; while (curr) { console.log(curr.data); curr = curr.next; } } // var stack = new Stack(); // stack.push(3); // stack.push(5); // stack.push(7); // stack.print(); // Queue implemented using LinkedList function Queue() { this.head = null; this.tail = null; } Queue.prototype.enqueue = function(data) { var newNode = new Node(data); if (this.head === null) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } } Queue.prototype.dequeue = function() { var newNode; if (this.head !== null) { newNode = this.head.data; this.head = this.head.next; } return newNode; } Queue.prototype.print = function() { var curr = this.head; while (curr) { console.log(curr.data); curr = curr.next; } } var queue = new Queue(); queue.enqueue(3); queue.enqueue(5); queue.enqueue(7); queue.print(); queue.dequeue(); queue.dequeue(); queue.print();
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());
}
}
}