我使用链接列表实现了一个队列。我添加了一个enqueue和dequeue函数。根据数据结构,如果使用dequeue后,'front'项之后的项应该成为front,但我的代码是将队列中的第三项设置为front。请看看我的代码,告诉我我做错了什么。
class Node {
constructor(value) {
this.value = value;
this.prev = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.length = 0;
}
enqueue(value) {
const newNode = new Node(value);
if (this.length === 0) {
this.front = newNode;
this.rear = newNode;
} else {
this.front.prev = this.rear;
this.rear = newNode;
}
this.length++;
return newNode;
}
dequeue() {
if (!this.front) {
return null;
}
if (this.front === this.rear) {
this.rear = null;
} else {
this.front = this.front.prev;
this.length--;
}
return this.front;
}
}
const myQueue = new Queue();
console.log('myQueue.enqueue(5) : ', myQueue.enqueue(5));
console.log('myQueue : ', myQueue);
console.log('myQueue.enqueue(6) : ', myQueue.enqueue(6));
console.log('myQueue : ', myQueue);
console.log('myQueue.enqueue(7) : ', myQueue.enqueue(7));
console.log('myQueue : ', myQueue);
console.log('myQueue.dequeue() : ', myQueue.dequeue());
console.log('myQueue : ', myQueue);
console.log('myQueue.dequeue() : ', myQueue.dequeue());
console.log('myQueue : ', myQueue);
.as-console-wrapper { max-height: 100%!important; top: 0; }
有两个答案部分...
有一个增量错误 this.length-
而不是 this.length--;
.
而如何使用一个 Queue
的方法,封装了一个列表结构,像一个 Array
?..
class Node {
constructor(value) {
this.value = value;
this.prev = null;
}
}
class Queue {
constructor() {
const queue = [];
this.front = null;
this.rear = null;
this.length = queue.length;
Object.defineProperty(this, 'enqueue', {
value: function (value) {
const node = new Node(value);
const itemCount = queue.push(node);
node.prev = queue[itemCount - 2] || null;
this.front = queue[0];
this.rear = queue[itemCount - 1];
this.length = itemCount;
return node;
}
});
Object.defineProperty(this, 'dequeue', {
value: function () {
const node = queue.shift() || null;
const itemCount = queue.length;
this.front = queue[0] || null;
this.rear = queue[itemCount - 1] || null;
this.length = itemCount;
return node;
}
});
}
}
const queue = new Queue();
console.log('queue.enqueue(5) : ', queue.enqueue(5));
console.log('queue.enqueue(6) : ', queue.enqueue(6));
console.log('queue.enqueue(7) : ', queue.enqueue(7));
console.log('queue.dequeue() : ', queue.dequeue());
console.log('queue.dequeue() : ', queue.dequeue());
console.log(queue);
.as-console-wrapper { max-height: 100%!important; top: 0; }
一个正确的排队过程更多的是依赖于正确的维护。next
链接。该 prev
链接只是 好看 功能在上面......概念验证......。
class Node {
constructor(value) {
this.value = value;
this.prev = null;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.length = 0;
}
enqueue(value) {
const enqueuedNode = new Node(value);
if (this.rear !== null) {
this.rear.next = enqueuedNode;
}
enqueuedNode.prev = this.rear;
const itemCount = ++this.length;
if (itemCount === 1) {
this.front = enqueuedNode;
}
this.rear = enqueuedNode;
return enqueuedNode;
}
dequeue() {
const dequeuedNode = this.front;
if (dequeuedNode !== null) {
dequeuedNode.prev = null;
// dequeuedNode.next = null;
}
this.front = dequeuedNode && dequeuedNode.next;
const itemCount = --this.length;
if (itemCount === 0) {
this.rear = null;
} else if (itemCount <= -1) {
this.length = 0;
}
return dequeuedNode;
}
}
const queue = new Queue();
console.log('queue.enqueue(5) : ', queue.enqueue(5));
console.log('queue : ', queue);
console.log('queue.enqueue(6) : ', queue.enqueue(6));
console.log('queue : ', queue);
console.log('queue.enqueue(7) : ', queue.enqueue(7));
console.log('queue : ', queue);
console.log('queue.dequeue() : ', queue.dequeue());
console.log('queue : ', queue);
console.log('queue.dequeue() : ', queue.dequeue());
console.log('queue : ', queue);
.as-console-wrapper { max-height: 100%!important; top: 0; }