队列是只允许在一段进行插入操作,而在另一端进行删除操作的线性表。
队列是一种先进先出的线性表,简称 FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。
队列的顺序存储结构
队列头尾相接的顺序存储结构称为循环队列。
js 实现代码
class Queue {
constructor() {
this.data = [];
this.rear = 0;
this.next = 0;
}
}
function enQueue(queue, e) {
queue.data.push(e);
}
function deQueue(queue) {
if (queue.data.length === 0) {
throw new Error('队列已空');
}
return queue.data.shift();
}
队列的链式存储结构
js 实现代码
class QueueNode {
constructor(data, next) {
this.data = data;
this.next = next;
}
}
class Queue {
constructor() {
this.front = null;
this.rear = null;
}
}
function createQueue() {
let queue = new Queue();
return queue;
}
function enQueue(queue, e) {
let newNode = new QueueNode(e);
if (queue.front === null) {
queue.front = newNode;
}
if (queue.rear === null) {
queue.rear = newNode;
} else {
queue.rear.next = newNode;
queue.rear = newNode;
}
}
function deQueue(queue) {
if (queue.front === null || queue.rear === null) {
throw new Error('队列为空');
}
let q = queue.front;
queue.front = q.next;
return q.data;
}
let queue = new createQueue();
enQueue(queue, 10);
enQueue(queue, 12);
enQueue(queue, 13);
console.log(deQueue(queue));
console.log(deQueue(queue));
console.log(deQueue(queue));
在可以确定队列长度最大值的情况下,建议使用循环队列,无法预估队列的长度,则用链队列。
网友评论