算法14（力扣622）设置循环队列

伤心客  论坛元老 | 2025-4-2 18:44:10 | 显示全部楼层 | 阅读模式
打印 上一主题 下一主题
楼主

主题 1715|帖子 1715|积分 5145

1、题目

设计你的循环队列实现。 循环队列是一种线性数据布局，其操作体现基于 FIFO（先辈先出）原则而且队尾被毗连在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个利益是我们可以利用这个队列之前用过的空间。在一个平常队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：


  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。假如队列为空，返回 -1 。
  • Rear: 获取队尾元素。假如队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。假如乐成插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。假如乐成删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。
2、示例

  1. MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
  2. circularQueue.enQueue(1);  // 返回 true
  3. circularQueue.enQueue(2);  // 返回 true
  4. circularQueue.enQueue(3);  // 返回 true
  5. circularQueue.enQueue(4);  // 返回 false，队列已满
  6. circularQueue.Rear();  // 返回 3
  7. circularQueue.isFull();  // 返回 true
  8. circularQueue.deQueue();  // 返回 true
  9. circularQueue.enQueue(4);  // 返回 true
  10. circularQueue.Rear();  // 返回 4
复制代码
3、理解题意


        题意：利用数组实现循环队列的一下方法
4、具体步调


（1）数组构建循环队列必要哪些元素？数组queue、头指针front、尾指针rear、capacity队列最大容量、size队列中当前元素数目


（2）判断队列是否为空，直接判断当前元素size是否为0


（3）判断队是否满，直接判断当前元素数size是否和队列的最大长度雷同


（4）插入：

        1）判断队满，满则返回。
        2）判断队空？空，头指针前移：非空，尾指针前移，插入，当前元素数+1

（5）删除
        1）判空？空，返回：非空（最后一个元素？是，重置头、尾指针：否，头指针前移，当前元素-1）


（6）从队首获取元素
        1）判空？空，返回-1：非空，返转头指针指向的元素


（7）从队尾获取元素
        1）空？空，返回-1：非空，返回尾指针指向的元素


5、完整代码

  1. <!DOCTYPE html>
  2. <html lang="en">
  3.   <head>
  4.     <meta charset="UTF-8" />
  5.     <meta name="viewport" content="width=device-width, initial-scale=1.0" />
  6.     <title>设计循环队列</title>
  7.   </head>
  8.   <body>
  9.     <p>
  10.       设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于
  11.       FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
  12.     </p>
  13.     <p>
  14.       循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
  15.     </p>
  16.     <p>
  17.         <h4>你的实现应该支持如下操作：</h4>
  18.         MyCircularQueue(k): 构造器，设置队列长度为 k 。<br>
  19.         Front: 从队首获取元素。如果队列为空，返回 -1 。<br>
  20.         Rear: 获取队尾元素。如果队列为空，返回 -1 。<br>
  21.         enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。<br>
  22.         deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。<br>
  23.         isEmpty(): 检查循环队列是否为空。<br>
  24.         isFull(): 检查循环队列是否已满。<br>
  25.     </p>
  26.   </body>
  27.   <script>
  28.         /**
  29.     * @param {number} k
  30.     */
  31.     var MyCircularQueue = function(k) {
  32.         this.queue = new Array(k)
  33.         // 为了区分队列为空和队列中有元素,让头指针和尾指针指向-1
  34.         this.front = -1
  35.         this.rear = -1
  36.         // 当前元素数量
  37.         this.size = 0
  38.         // 队列最大容量
  39.         this.capacity = k
  40.     };
  42.     /**
  43.     * @param {number} value
  44.     * @return {boolean}
  45.     */
  46.     MyCircularQueue.prototype.enQueue = function(value) {
  47.         // 判断队列是否为空，如果为空，头指针需要向前移动
  48.         if (this.isEmpty()) {
  49.             this.front = 0
  50.         }
  51.         if (this.isFull()) {
  52.             console.log(false,this.queue);
  53.             return false
  54.         }
  55.         // 添加
  56.         // 尾指针向前
  57.         this.rear = (this.rear + 1)%this.capacity
  58.         // 添加
  59.         this.queue[this.rear] = value
  60.         this.size++
  61.         console.log(true,this.queue);
  62.         return true
  63.     };
  65.     /**
  66.     * @return {boolean}
  67.     */
  68.     MyCircularQueue.prototype.deQueue = function() {
  69.         //
  70.         if (this.isEmpty()) {
  71.             console.log('false',this.queue);
  72.             return false
  73.         }
  74.         if (this.front===this.rear) {
  75.             // 队列中只有一个元素且该元素即将被删除
  76.             this.front = -1
  77.             this.rear = -1
  78.         }else{
  79.             // 头指针前移，删除元素
  80.             this.front = (this.front+1)%this.capacity
  81.         }
  82.         this.size--;
  83.         console.log(true,this.queue);
  84.         return true
  86.     };
  88.     /**
  89.     * @return {number}
  90.     */
  91.     MyCircularQueue.prototype.Front = function() {
  92.         if (this.isEmpty()) {
  93.              console.log('-1',this.queue);
  94.             return -1
  95.         }
  96.         console.log(this.queue[this.front]);
  97.         return this.queue[this.front]
  98.     };
  100.     /**
  101.     * @return {number}
  102.     */
  103.     MyCircularQueue.prototype.Rear = function() {
  104.            if (this.isEmpty()) {
  105.             return -1
  106.         }
  107.         console.log(this.queue[(this.rear + this.capacity ) % this.capacity],this.queue);
  108.         // this.rear + this.capacity确保当 this.rear 为 0 时，计算出的索引不会是负数
  109.         return this.queue[(this.rear + this.capacity ) % this.capacity]
  110.     };
  112.     /**
  113.     * @return {boolean}
  114.     */
  115.     MyCircularQueue.prototype.isEmpty = function() {
  116.         if (this.size === 0) {
  117.             return true
  118.         }
  119.         return false
  120.     };
  122.     /**
  123.     * @return {boolean}
  124.     */
  125.     MyCircularQueue.prototype.isFull = function() {
  126.         if (this.size === this.capacity) {
  127.             return true
  128.         }
  129.         return false
  130.     };
  131.    
  132.    
  133.     var circularQueue = new MyCircularQueue(3); // 设置长度为 3
  134.     circularQueue.enQueue(1);  // 返回 true
  135.     circularQueue.enQueue(2);  // 返回 true
  136.     circularQueue.enQueue(3);  // 返回 true
  137.     circularQueue.enQueue(4);  // 返回 false，队列
  138.     circularQueue.Rear();  // 返回 3
  139.     circularQueue.isFull();  // 返回 true
  140.     circularQueue.deQueue();  // 返回 true
  141.     circularQueue.enQueue(4);  // 返回 true
  142.     circularQueue.Rear();  // 返回 4
  143.     /**
  144.     * Your MyCircularQueue object will be instantiated and called as such:
  145.     * var obj = new MyCircularQueue(k)
  146.     * var param_1 = obj.enQueue(value)
  147.     * var param_2 = obj.deQueue()
  148.     * var param_3 = obj.Front()
  149.     * var param_4 = obj.Rear()
  150.     * var param_5 = obj.isEmpty()
  151.     * var param_6 = obj.isFull()
  152.     */
  153.   </script>
  154. </html>
复制代码
6、力扣通过代码

  1.     var MyCircularQueue = function(k) {
  2.         this.queue = new Array(k)
  3.         // 为了区分队列为空和队列中有元素,让头指针和尾指针指向-1
  4.         this.front = -1
  5.         this.rear = -1
  6.         // 当前元素数量
  7.         this.size = 0
  8.         // 队列最大容量
  9.         this.capacity = k
  10.     };
  12.     /**
  13.     * @param {number} value
  14.     * @return {boolean}
  15.     */
  16.     MyCircularQueue.prototype.enQueue = function(value) {
  17.         // 判断队列是否为空，如果为空，头指针需要向前移动
  18.         if (this.isEmpty()) {
  19.             this.front = 0
  20.         }
  21.         if (this.isFull()) {
  22.             console.log(false,this.queue);
  23.             return false
  24.         }
  25.         // 添加
  26.         // 尾指针向前
  27.         this.rear = (this.rear + 1)%this.capacity
  28.         // 添加
  29.         this.queue[this.rear] = value
  30.         this.size++
  31.         console.log(true,this.queue);
  32.         return true
  33.     };
  35.     /**
  36.     * @return {boolean}
  37.     */
  38.     MyCircularQueue.prototype.deQueue = function() {
  39.         //
  40.         if (this.isEmpty()) {
  41.             console.log('false',this.queue);
  42.             return false
  43.         }
  44.         if (this.front===this.rear) {
  45.             // 队列中只有一个元素且该元素即将被删除
  46.             this.front = -1
  47.             this.rear = -1
  48.         }else{
  49.             // 头指针前移，删除元素
  50.             this.front = (this.front+1)%this.capacity
  51.         }
  52.         this.size--;
  53.         console.log(true,this.queue);
  54.         return true
  56.     };
  58.     /**
  59.     * @return {number}
  60.     */
  61.     MyCircularQueue.prototype.Front = function() {
  62.         if (this.isEmpty()) {
  63.              console.log('-1',this.queue);
  64.             return -1
  65.         }
  66.         console.log(this.queue[this.front]);
  67.         return this.queue[this.front]
  68.     };
  70.     /**
  71.     * @return {number}
  72.     */
  73.     MyCircularQueue.prototype.Rear = function() {
  74.            if (this.isEmpty()) {
  75.             return -1
  76.         }
  77.         console.log(this.queue[(this.rear + this.capacity ) % this.capacity],this.queue);
  78.         return this.queue[(this.rear + this.capacity) % this.capacity]
  79.     };
  81.     /**
  82.     * @return {boolean}
  83.     */
  84.     MyCircularQueue.prototype.isEmpty = function() {
  85.         if (this.size === 0) {
  86.             return true
  87.         }
  88.         return false
  89.     };
  91.     /**
  92.     * @return {boolean}
  93.     */
  94.     MyCircularQueue.prototype.isFull = function() {
  95.         if (this.size === this.capacity) {
  96.             return true
  97.         }
  98.         return false
  99.     };
  100.    
复制代码





免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

本帖子中包含更多资源

您需要 登录 才可以下载或查看，没有账号？立即注册

x
回复

使用道具 举报

0 个回复

倒序浏览
返回列表

快速回复

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

伤心客

论坛元老
这个人很懒什么都没写!

楼主热帖

标签云

AI 运维 CIO 存储 服务器
微信订阅号
微信服务号
微信客服
小程序
H5
关于我们 商务合作 网站地图
©Copyright 2022-2024 杭州祥升科技有限公司 版权所有 浙ICP备20004199号
快速回复 返回顶部 返回列表