# LeetCode 622: Design Circular Queue

## Problem Restatement

We need to design a circular queue.

A queue follows FIFO order: first in, first out.

A circular queue uses a fixed-size array, but when the end of the array is reached, the next position wraps around to the beginning. This lets the queue reuse empty space created by earlier removals.

The class must support these operations:

| Operation | Meaning |
|---|---|
| `MyCircularQueue(k)` | Create a queue with capacity `k` |
| `enQueue(value)` | Insert `value` into the queue |
| `deQueue()` | Remove the front element |
| `Front()` | Return the front element |
| `Rear()` | Return the last element |
| `isEmpty()` | Check whether the queue is empty |
| `isFull()` | Check whether the queue is full |

`Front()` and `Rear()` return `-1` when the queue is empty.

`enQueue()` returns `False` when the queue is full.

`deQueue()` returns `False` when the queue is empty.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A capacity `k`, followed by method calls |
| Output | Each method returns the required value |
| Queue type | Fixed-size circular queue |
| Required behavior | All operations should be `O(1)` |

Example class shape:

```python
class MyCircularQueue:

    def __init__(self, k: int):
        ...

    def enQueue(self, value: int) -> bool:
        ...

    def deQueue(self) -> bool:
        ...

    def Front(self) -> int:
        ...

    def Rear(self) -> int:
        ...

    def isEmpty(self) -> bool:
        ...

    def isFull(self) -> bool:
        ...
```

## Examples

Start with a circular queue of size `3`.

```python
q = MyCircularQueue(3)
```

Insert three values:

```python
q.enQueue(1)  # True
q.enQueue(2)  # True
q.enQueue(3)  # True
```

Now the queue is full:

```text
[1, 2, 3]
 front = 0
 size = 3
```

Trying to insert another value fails:

```python
q.enQueue(4)  # False
```

The rear value is `3`:

```python
q.Rear()  # 3
```

The queue is full:

```python
q.isFull()  # True
```

Remove the front value:

```python
q.deQueue()  # True
```

Now `1` is removed. The front moves to `2`.

```text
[1, 2, 3]
    front = 1
    size = 2
```

Insert `4`.

Because the array is circular, `4` goes into the old position at index `0`.

```python
q.enQueue(4)  # True
```

The logical queue is now:

```text
2, 3, 4
```

The physical array may look like:

```text
[4, 2, 3]
 front = 1
 size = 3
```

The rear value is now:

```python
q.Rear()  # 4
```

## First Thought: Use a Python List Directly

A simple queue can be written with a Python list:

```python
queue.append(value)
queue.pop(0)
```

But `pop(0)` is `O(n)` because all later elements must shift left.

This problem asks us to design a fixed-size circular queue. We want each operation to run in constant time.

So we should not move elements around. Instead, we keep pointers.

## Key Insight

Use a fixed array of length `k`.

Keep two pieces of state:

| State | Meaning |
|---|---|
| `front` | Index of the current front element |
| `size` | Number of elements currently stored |

The rear index can be computed when needed.

If the queue has capacity `capacity`, then the next insertion position is:

```python
(front + size) % capacity
```

The rear index is:

```python
(front + size - 1) % capacity
```

The modulo operation is what makes the queue circular.

For example, if `capacity = 3`, then index `3` wraps to index `0`:

```python
3 % 3 == 0
```

## Algorithm

Initialize:

```python
self.queue = [0] * k
self.capacity = k
self.front = 0
self.size = 0
```

For `enQueue(value)`:

1. If the queue is full, return `False`.
2. Compute the insertion index:

```python
index = (self.front + self.size) % self.capacity
```

3. Store the value there.
4. Increase `size`.
5. Return `True`.

For `deQueue()`:

1. If the queue is empty, return `False`.
2. Move `front` forward by one circular step:

```python
self.front = (self.front + 1) % self.capacity
```

3. Decrease `size`.
4. Return `True`.

For `Front()`:

1. If empty, return `-1`.
2. Return `self.queue[self.front]`.

For `Rear()`:

1. If empty, return `-1`.
2. Compute:

```python
index = (self.front + self.size - 1) % self.capacity
```

3. Return `self.queue[index]`.

For `isEmpty()`:

```python
return self.size == 0
```

For `isFull()`:

```python
return self.size == self.capacity
```

## Correctness

The array has fixed length `capacity`, and all array accesses use modulo `capacity`. Therefore every computed position is a valid array index.

The variable `front` always points to the first logical element of the queue when the queue is not empty. Initially the queue is empty, so there is no front element. After the first successful insertion, the insertion index is `(front + size) % capacity = 0`, so the first element is stored at index `0`, matching `front`.

For `enQueue`, the new value must be added after all existing queue elements. Since there are `size` elements starting at `front`, the next free logical position is `front + size`. Taking modulo `capacity` maps that logical position back into the fixed array. So the new value is placed at the correct rear position.

For `deQueue`, removing the front element means the next element becomes the new front. Advancing `front` by one circular step gives exactly that position. Decreasing `size` keeps the number of stored elements correct.

`Front()` returns the element at `front`, which is the first logical element by the invariant above.

`Rear()` returns the element at logical position `front + size - 1`, which is the last stored element. Taking modulo `capacity` gives its physical array index.

`isEmpty()` is correct because the queue has no elements exactly when `size == 0`.

`isFull()` is correct because the queue has used every available slot exactly when `size == capacity`.

Therefore all operations preserve the circular queue behavior.

## Complexity

| Operation | Time | Space |
|---|---:|---:|
| `enQueue` | `O(1)` | `O(1)` |
| `deQueue` | `O(1)` | `O(1)` |
| `Front` | `O(1)` | `O(1)` |
| `Rear` | `O(1)` | `O(1)` |
| `isEmpty` | `O(1)` | `O(1)` |
| `isFull` | `O(1)` | `O(1)` |

The full data structure uses `O(k)` space for the fixed array.

## Implementation

```python
class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.capacity = k
        self.front = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        index = (self.front + self.size) % self.capacity
        self.queue[index] = value
        self.size += 1

        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.front = (self.front + 1) % self.capacity
        self.size -= 1

        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1

        return self.queue[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1

        index = (self.front + self.size - 1) % self.capacity
        return self.queue[index]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity
```

## Code Explanation

The array is allocated once:

```python
self.queue = [0] * k
```

We do not grow or shrink it.

The queue capacity is stored separately:

```python
self.capacity = k
```

The front pointer starts at index `0`:

```python
self.front = 0
```

The current queue has no elements:

```python
self.size = 0
```

When inserting, we first reject the operation if the queue is full:

```python
if self.isFull():
    return False
```

Then we compute the next insertion slot:

```python
index = (self.front + self.size) % self.capacity
```

This slot may be at the end of the array, or it may wrap around to the beginning.

When deleting, we do not erase the old value. We only move the logical front:

```python
self.front = (self.front + 1) % self.capacity
```

The old value can stay in the array because it is outside the logical queue. Future insertions may overwrite it.

The rear value is not stored as a separate pointer. It is computed from `front` and `size`:

```python
index = (self.front + self.size - 1) % self.capacity
```

This keeps the state small and avoids pointer synchronization bugs.

## Testing

```python
def run_tests():
    q = MyCircularQueue(3)

    assert q.enQueue(1) is True
    assert q.enQueue(2) is True
    assert q.enQueue(3) is True
    assert q.enQueue(4) is False

    assert q.Rear() == 3
    assert q.isFull() is True

    assert q.deQueue() is True
    assert q.enQueue(4) is True

    assert q.Rear() == 4
    assert q.Front() == 2

    q2 = MyCircularQueue(1)
    assert q2.isEmpty() is True
    assert q2.Front() == -1
    assert q2.Rear() == -1
    assert q2.enQueue(10) is True
    assert q2.isFull() is True
    assert q2.enQueue(20) is False
    assert q2.Front() == 10
    assert q2.Rear() == 10
    assert q2.deQueue() is True
    assert q2.deQueue() is False
    assert q2.isEmpty() is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Fill capacity `3` | Confirms normal insertion |
| Insert when full | Must return `False` |
| Remove then insert | Confirms circular wrap-around |
| Check `Front()` after wrap | Confirms logical order |
| Capacity `1` | Tests smallest useful queue |
| Read from empty queue | Must return `-1` |
| Delete from empty queue | Must return `False` |