写点什么

LeetCode 题解:622. 设计循环队列,使用双向链表,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 09 月 17 日
LeetCode题解:622. 设计循环队列,使用双向链表,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/design-circular-queue/



解题思路:



  1. 使用双向链表,头指针指向队首元素,尾指针指向下一个要插入值的元素,队尾在尾指针的下一个元素。

  2. 每次插入和移除元素都相应增减节点数量即可。



/**
* Initialize your data structure here. Set the size of the queue to be k.
* @param {number} k
*/
// 创建双向链表节点
function ListNode(val) {
this.val = val;
this.prev = null;
this.next = null;
}
var MyCircularQueue = function (k) {
this.capacity = k; // 队列的长度
this.count = 0; // 队列中的节点个数统计
const node = new ListNode(null); // 初始节点,用于存放第一个入队的元素
this.head = node; // 头指针指向队首的节点
this.tail = node; // 尾指针指向元素入队时存储的节点
};
/**
* Insert an element into the circular queue. Return true if the operation is successful.
* @param {number} value
* @return {boolean}
*/
MyCircularQueue.prototype.enQueue = function (value) {
if (this.isFull()) {
return false;
}
const newNode = new ListNode(null); // 创建一个节点,用于存储下一个入队的值
// 将入队的值,存在尾节点
const currentNode = this.tail;
currentNode.val = value;
// 将当前节点的prev指向新节点,保证删除节点时,头节点可以移动
currentNode.prev = newNode;
// 将新节点与当前节点连接
newNode.next = currentNode;
// 移动尾指针,使其指向新节点。
this.tail = newNode;
// 增加节点计数
this.count++;
return true;
};
/**
* Delete an element from the circular queue. Return true if the operation is successful.
* @return {boolean}
*/
MyCircularQueue.prototype.deQueue = function () {
if (this.isEmpty()) {
return false;
}
// 头指针指向的节点
const currentNode = this.head;
// 头指针的下一个节点
const prevNode = currentNode.prev;
// 移动头指针到下一个节点
this.head = prevNode;
// 将nextNode的指向置为null,移除当前节点
prevNode.next = null;
// 减少节点计数
this.count--;
return true;
};
/**
* Get the front item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Front = function () {
// 队列为空,则返回-1
if (this.isEmpty()) {
return -1;
}
// 头结点的值即为队首
return this.head.val;
};
/**
* Get the last item from the queue.
* @return {number}
*/
MyCircularQueue.prototype.Rear = function () {
// 队列为空,则返回-1
if (this.isEmpty()) {
return -1;
}
// 尾节点的前一个节点即为队尾
return this.tail.next.val;
};
/**
* Checks whether the circular queue is empty or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isEmpty = function () {
return this.count === 0;
};
/**
* Checks whether the circular queue is full or not.
* @return {boolean}
*/
MyCircularQueue.prototype.isFull = function () {
return this.count === this.capacity;
};



发布于: 2020 年 09 月 17 日阅读数: 40
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:622. 设计循环队列,使用双向链表,JavaScript,详细注释