摘要：刪除操作也被稱為出隊。如上所述，隊列應(yīng)支持兩種操作入隊和出隊。循環(huán)隊列此前，我們提供了一種簡單但低效的隊列實現(xiàn)。更有效的方法是使用循環(huán)隊列。它也被稱為環(huán)形緩沖器。檢查循環(huán)隊列是否已滿。表示隊列的起始位置，表示隊列的結(jié)束位置。

首先來看看隊列這種數(shù)據(jù)結(jié)構(gòu)：

在 FIFO 數(shù)據(jù)結(jié)構(gòu)中，將首先處理添加到隊列中的第一個元素。

如上圖所示，隊列是典型的 FIFO 數(shù)據(jù)結(jié)構(gòu)。插入（insert）操作也稱作入隊（enqueue），新元素始終被添加在隊列的末尾。 刪除（delete）操作也被稱為出隊（dequeue)。 你只能移除第一個元素。

隊列 - 實現(xiàn)

為了實現(xiàn)隊列，我們可以使用動態(tài)數(shù)組和指向隊列頭部的索引。

如上所述，隊列應(yīng)支持兩種操作：入隊和出隊。入隊會向隊列追加一個新元素，而出隊會刪除第一個元素。 所以我們需要一個索引來指出起點。

循環(huán)隊列

此前，我們提供了一種簡單但低效的隊列實現(xiàn)。

更有效的方法是使用循環(huán)隊列。 具體來說，我們可以使用固定大小的數(shù)組和兩個指針來指示起始位置和結(jié)束位置。 目的是重用我們之前提到的被浪費的存儲。

讓我們通過一個示例來查看循環(huán)隊列的工作原理。 你應(yīng)該注意我們入隊或出隊元素時使用的策略。

[外鏈圖片轉(zhuǎn)存失敗(img-ScULOtla-1564547660610)(queue.gif)]

仔細(xì)檢查動畫，找出我們用來檢查隊列是空還是滿的策略。

以上內(nèi)容來自力扣中國，內(nèi)容有改變

設(shè)計你的循環(huán)隊列實現(xiàn)。 循環(huán)隊列是一種線性數(shù)據(jù)結(jié)構(gòu)，其操作表現(xiàn)基于 FIFO（先進(jìn)先出）原則并且隊尾被連接在隊首之后以形成一個循環(huán)。它也被稱為“環(huán)形緩沖器”。

循環(huán)隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列里，一旦一個隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環(huán)隊列，我們能使用這些空間去存儲新的值。

你的實現(xiàn)應(yīng)該支持如下操作：

MyCircularQueue(k): 構(gòu)造器，設(shè)置隊列長度為 k 。

Front: 從隊首獲取元素。如果隊列為空，返回 -1 。

Rear: 獲取隊尾元素。如果隊列為空，返回 -1 。

enQueue(value): 向循環(huán)隊列插入一個元素。如果成功插入則返回真。

deQueue(): 從循環(huán)隊列中刪除一個元素。如果成功刪除則返回真。

isEmpty(): 檢查循環(huán)隊列是否為空。

isFull(): 檢查循環(huán)隊列是否已滿。

示例：

MyCircularQueue circularQueue = new MycircularQueue(3); // 設(shè)置長度為 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 的范圍內(nèi)；

操作數(shù)將在 1 至 1000 的范圍內(nèi)；

請不要使用內(nèi)置的隊列庫。

一般高級程序設(shè)計語言都會內(nèi)置隊列庫，稍微參考一下即可。在循環(huán)隊列中，我們使用一個數(shù)組和兩個指針（head 和 tail）。 head 表示隊列的起始位置，tail 表示隊列的結(jié)束位置。

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

    /** 初始化數(shù)據(jù)結(jié)構(gòu)，并規(guī)定隊列大小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):
        """
        初始化數(shù)據(jù)結(jié)構(gòu)，并規(guī)定隊列大小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