资讯专栏INFORMATION COLUMN

LeetCode 622:设计循环队列 Design Circular Queue

Joyven / 2496人阅读

摘要:删除操作也被称为出队。如上所述,队列应支持两种操作入队和出队。循环队列此前,我们提供了一种简单但低效的队列实现。更有效的方法是使用循环队列。它也被称为环形缓冲器。检查循环队列是否已满。表示队列的起始位置,表示队列的结束位置。

LeetCode 622:设计循环队列 Design Circular Queue

首先来看看队列这种数据结构:

队列:先入先出的数据结构

在 FIFO 数据结构中,将首先处理添加到队列中的第一个元素

如上图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素

队列 - 实现

为了实现队列,我们可以使用动态数组和指向队列头部的索引。

如上所述,队列应支持两种操作:入队和出队。入队会向队列追加一个新元素,而出队会删除第一个元素。 所以我们需要一个索引来指出起点。

循环队列

此前,我们提供了一种简单但低效的队列实现。

更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储

让我们通过一个示例来查看循环队列的工作原理。 你应该注意我们入队出队元素时使用的策略。

[外链图片转存失败(img-ScULOtla-1564547660610)(queue.gif)]

仔细检查动画,找出我们用来检查队列是还是的策略。

以上内容来自力扣中国,内容有改变

题目:设计循环队列:

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

MyCircularQueue(k): 构造器,设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空,返回 -1 。

Rear: 获取队尾元素。如果队列为空,返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

示例:

MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false,队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示:

所有的值都在 0 至 1000 的范围内;

操作数将在 1 至 1000 的范围内;

请不要使用内置的队列库。

解题思路:

一般高级程序设计语言都会内置队列库,稍微参考一下即可。在循环队列中,我们使用一个数组和两个指针(headtail)。 head 表示队列的起始位置,tail 表示队列的结束位置。

class MyCircularQueue {
    
    private int[] data;
    private int head;
    private int tail;
    private int size;

    /** 初始化数据结构,并规定队列大小k */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** 在队列插入一项,并返回插入是否成功 */
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    /** 从队列删除一项,并返回删除是否成功 */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    /** 获取队列第一项 */
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }
    
    /** 获取队列最后一项 */
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }
    
    /** 检查队列是否为空 */
    public boolean isEmpty() {
        return head == -1;
    }
    
    /** 检查队列是否已满 */
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}
Python3:
class MyCircularQueue():

    def __init__(self, k: int):
        """
        初始化数据结构,并规定队列大小k
        """
        self.size = k
        self.queue = [""]*k
        self.head = -1
        self.tail = -1
        
    def enQueue(self, value: int) -> bool:
        """
        在队列插入一项,并返回插入是否成功
        """
        if not self.isFull():
            if self.head == -1:
                self.head = 0
            self.tail = (self.tail+1)%self.size
            self.queue[self.tail] = value
            return True
        else:
            return False
        
    def deQueue(self) -> bool:
        """
        从队列删除一项,并返回删除是否成功
        """
        if not self.isEmpty():
            if self.head ==self.tail:
                self.head,self.tail = -1,-1
            else:
                self.head = (self.head+1)%self.size
            return True
        else:
            return False

    def Front(self) -> int:
        """
        获取队列第一项
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.head]

    def Rear(self) -> int:
        """
        获取队列最后一项
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.tail]

    def isEmpty(self) -> bool:
        """
        检查队列是否为空
        """
        return self.head == -1 and self.tail == -1

    def isFull(self) -> bool:
        """
        检查队列是否已满
        """
        return (self.tail+1)%self.size ==self.head

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/75706.html

相关文章

  • [Leetcode 622]设计循环队列

    摘要:循环队列是一种线性数据结构,其操作表现基于先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器。但是使用循环队列,我们能使用这些空间去存储新的值。检查循环队列是否已满。 设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为环形缓冲器。循环队列的一个好处是我们可以利用这个队列之前...

    canopus4u 评论0 收藏0
  • LeetCode 之 JavaScript 解答第641题 —— 设计双端队列Design Cir

    摘要:小鹿题目设计实现双端队列。你的实现需要支持以下操作构造函数双端队列的大小为。获得双端队列的最后一个元素。检查双端队列是否为空。数组头部删除第一个数据。以上数组提供的使得更方便的对数组进行操作和模拟其他数据结构的操作,栈队列等。 Time:2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿 题目:Desi...

    Freeman 评论0 收藏0
  • leetcode355. Design Twitter

    摘要:思路和代码这道题目本质上是考察是否能将数据结构的知识灵活的运用于现实生活中。这题等价于我们每次都会比较当前所有被关注者发布的最新未读,选出结果后将其插入结果集。 题目要求 Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able...

    superPershing 评论0 收藏0
  • 从Vue.js源码看异步更新DOM策略及nextTick

    摘要:我们发现默认是使用异步执行更新。优先使用,在不存在的情况下使用,这两个方法的回调函数都会在中执行,它们会比更早执行,所以优先使用。是最后的一种备选方案,它会将回调函数加入中,等到执行。 写在前面 因为对Vue.js很感兴趣,而且平时工作的技术栈也是Vue.js,这几个月花了些时间研究学习了一下Vue.js源码,并做了总结与输出。文章的原地址:https://github.com/ans...

    leo108 评论0 收藏0
  • leetcode】3. 无重复字符的最长子串

    摘要:示例输入输出解释因为无重复字符的最长子串是,所以其长度为。请注意,你的答案必须是子串的长度,是一个子序列,不是子串。完成循环后取队列中出现的最大长度即可。 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc,所以其长度为 3。 示例 2: 输入: bbbbb 输出: 1 解释:...

    qc1iu 评论0 收藏0

发表评论

0条评论

Joyven

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<