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

jiezi

5 年前

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

在 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 的范围内；
请不要使用内置的队列库。

一般高级程序设计语言都会内置队列库，稍微参考一下即可。在循环队列中，我们使用一个 数组 和两个指针（head 和 tail）。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;
    }
}

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

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

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

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

题目：设计循环队列：

解题思路：

Python3：