---
# System prepended metadata

title: 環狀queue
tags: [LeetCode筆記]

---

###### tags: `LeetCode筆記`
# 環狀queue

[toc]

##  Circular Queue 實作方法


-   One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
    
-   環狀佇列的重點
    
    -   full 和empty的判斷有很多種寫法，但核心概念一樣
    -   下面是透過公式去求的當前的佇列大小。
    -   circular queue 有個缺點，會浪費一個記憶體空間，這樣才可以讓演算法判斷整個queue是不是滿的
    -   以下為名詞解釋
    -   **Algorithm for Circular Queue-1**
        1.  `size`:
            -   If, `tail >= head`, `size = tail - head`
            -   But if, `head > tail`, then `size = maxSize - (head - tail)`
        2.  `dequeue`: Check if the number of elements in the queue is zero:
            -   If **Yes**, then return **Queue is empty**
            -   If **No**, then increment the `head` pointer.
        3.  `enqueue`: Check if the number of elements is equal to `maxSize - 1`:
            -   If **Yes**, then return **Queue is full**
            -   If **No**, then add the new data element to the location of `tail` pointer and increment the `tail` pointer.
        4.  Initialize the queue, with size of the queue defined (`maxSize`), and `head` and `tail` pointers.
    





## 圖解

一開始在設定值的時候是為-1

這邊如果用(rear+1)%max_size 會錯誤，所以我們直接設定
if front ==rear ==-1 則 queue is empty

初始化
![](https://i.imgur.com/CJ84PnI.png)
enqueue 之後他的rear 的算法是如左下

![](https://i.imgur.com/s0iKAqv.png)

如果如左下判斷式的時候，可判斷enqueue為Full
![](https://i.imgur.com/vNLCLdK.png)

dequeue 的方式也是一樣
![](https://i.imgur.com/Fe8Vznx.png)


## 基本資料結構


![](https://i.imgur.com/6VP9xJc.png)

### enqueue method 第一步：判斷是否為滿了，或是空了。
![](https://i.imgur.com/EbXDCph.png)

第二步
![](https://i.imgur.com/GZwh32n.png)


### Dequeue method

如果front ==rear 的情況 就是front 追上Rear 因為 front 是先取出當下這個值 在移動到下一個值 ，所以這時候會相等，代表整個queue 剩下這個值，然後我們上一步已經先把他放到tme 裡面了，所以我們可以直接１８３ front &rear 歸0 從來這樣子

第一步：判斷是否空了，以及是否滿了
![](https://i.imgur.com/k2Ekyi2.png)

第二步：
![](https://i.imgur.com/5o1OP2B.png)

第三步：取出 tem 
![](https://i.imgur.com/XRfEUZg.png)

### empty method

![](https://i.imgur.com/hzg0xgb.png)

### full method

![](https://i.imgur.com/ZNm6EoJ.png)

###  peek method

![](https://i.imgur.com/bphb6cz.png)

## 全部程式碼 


```python=

# This is the CircularQueue class
class CircularQueue:
  
  # constructor for the class
  # taking input for the size of the Circular queue 
  # from user
  def __init__(self, maxSize):
    self.queue = list()
    # user input value for maxSize
    self.maxSize = maxSize
    self.head = 0
    self.tail = 0

  # add element to the queue
  def enqueue(self, data):
    # if queue is full
    if self.size() == (self.maxSize - 1):
      return("Queue is full!")
    else:
      # add element to the queue
      self.queue.append(data)
      # increment the tail pointer
      self.tail = (self.tail+1) % self.maxSize
      return True
  
  # remove element from the queue
  def dequeue(self):
    # if queue is empty
    if self.size() == 0:
      return("Queue is empty!")
    else:
      # fetch data
      data = self.queue[self.head]
      # increment head
      self.head = (self.head+1) % self.maxSize
      return data
  
  # find the size of the queue
  def size(self):
    if self.tail >= self.head: 
      qSize = self.tail - self.head # 已經填滿一圈
    else:
      qSize = self.maxSize - (self.head - self.tail) #正常我們還沒填滿一圈

    # return the size of the queue
    return qSize 

# input 7 for the size or anything else
size = input("Enter the size of the Circular Queue")
q = CircularQueue(int(size))

# change the enqueue and dequeue statements as you want
print(q.enqueue(10))
print(q.enqueue(20))
print(q.enqueue(30))
print(q.enqueue(40))
print(q.enqueue(50))
print(q.enqueue('Studytonight'))
print(q.enqueue(70))
print(q.enqueue(80))
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
```