LeetCode 题解:622. 设计循环队列,使用双向链表,JavaScript,详细注释
发布于: 2020 年 09 月 17 日
原题链接:https://leetcode-cn.com/problems/design-circular-queue/
解题思路:
使用双向链表,头指针指向队首元素,尾指针指向下一个要插入值的元素,队尾在尾指针的下一个元素。
每次插入和移除元素都相应增减节点数量即可。
/** * 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
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/fc65a8e8262956f88909d2020】。文章转载请联系作者。
Lee Chen
关注
还未添加个人签名 2018.08.29 加入
还未添加个人简介
评论