###### 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

初始化
enqueue 之後他的rear 的算法是如左下


如果如左下判斷式的時候，可判斷enqueue為Full

dequeue 的方式也是一樣

## 基本資料結構


### enqueue method 第一步：判斷是否為滿了，或是空了。

第二步

### Dequeue method

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

第一步：判斷是否空了，以及是否滿了

第二步：

第三步：取出 tem

### empty method


### full method


### peek method


## 全部程式碼

# 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())