# LeetCode 641: Design Circular Deque

## Problem Restatement

We need to design a circular double-ended queue.

A deque supports insertion and deletion from both ends:

| Operation | Meaning |
|---|---|
| `insertFront(value)` | Add a value to the front |
| `insertLast(value)` | Add a value to the rear |
| `deleteFront()` | Remove the front value |
| `deleteLast()` | Remove the rear value |
| `getFront()` | Read the front value |
| `getRear()` | Read the rear value |

The deque has a fixed maximum capacity `k`.

If we try to insert into a full deque, the operation should return `False`.

If we try to delete from an empty deque, the operation should return `False`.

If we try to read from an empty deque, the operation should return `-1`.

## Input and Output

Class shape:

```python
class MyCircularDeque:

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

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

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

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

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

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

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

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

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

The official operations require `O(1)` behavior for insertion, deletion, front access, rear access, and empty/full checks.

## Example

Operations:

```python
deque = MyCircularDeque(3)

deque.insertLast(1)    # True
deque.insertLast(2)    # True
deque.insertFront(3)   # True
deque.insertFront(4)   # False
deque.getRear()        # 2
deque.isFull()         # True
deque.deleteLast()     # True
deque.insertFront(4)   # True
deque.getFront()       # 4
```

After inserting `1`, `2`, and `3`, the deque has capacity `3`, so it is full.

That is why:

```python
deque.insertFront(4)
```

returns:

```python
False
```

After deleting from the rear, there is space again, so inserting `4` at the front succeeds.

## First Thought: Use a Python List

A simple implementation could use a list.

```python
self.data.insert(0, value)
self.data.append(value)
self.data.pop(0)
self.data.pop()
```

This works logically, but `insert(0, value)` and `pop(0)` are `O(n)` because all later elements must shift.

We need all operations to be constant time.

## Key Insight

Use a fixed-size array as a circular buffer.

The array has length `k`.

Instead of physically shifting elements, we keep:

| Variable | Meaning |
|---|---|
| `front` | Index of the current front element |
| `size` | Number of elements currently stored |
| `capacity` | Maximum number of elements |
| `data` | Fixed-size array |

The rear index can be computed from `front` and `size`:

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

The modulo operator makes the index wrap around.

For example, if `capacity = 3`, then after index `2`, the next index is:

```python
(2 + 1) % 3 = 0
```

That is the circular part.

## Index Rules

When inserting at the front, the new front is one step before the old front:

```python
front = (front - 1) % capacity
```

When deleting from the front, the new front is one step after the old front:

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

When inserting at the rear, the rear index is the first empty slot after the current last element:

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

When reading the rear, the rear index is:

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

These formulas avoid shifting elements.

## Algorithm

Initialize:

```python
data = [0] * k
front = 0
size = 0
capacity = k
```

For `insertFront(value)`:

1. If full, return `False`.
2. Move `front` backward with modulo.
3. Write `value` at `front`.
4. Increase `size`.
5. Return `True`.

For `insertLast(value)`:

1. If full, return `False`.
2. Compute the rear insertion index.
3. Write `value`.
4. Increase `size`.
5. Return `True`.

For `deleteFront()`:

1. If empty, return `False`.
2. Move `front` forward.
3. Decrease `size`.
4. Return `True`.

For `deleteLast()`:

1. If empty, return `False`.
2. Decrease `size`.
3. Return `True`.

For `getFront()`:

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

For `getRear()`:

1. If empty, return `-1`.
2. Compute rear index.
3. Return `data[rear]`.

## Implementation

```python
class MyCircularDeque:

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

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

        self.front = (self.front - 1) % self.capacity
        self.data[self.front] = value
        self.size += 1

        return True

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

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

        return True

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

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

        return True

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

        self.size -= 1

        return True

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

        return self.data[self.front]

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

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

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

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

## Code Explanation

The array is fixed-size:

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

We do not resize it.

The `size` variable distinguishes empty from full:

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

Without `size`, `front == rear` could mean either empty or full, which complicates the design.

Insertion at the front moves `front` backward:

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

In Python, modulo handles negative values cleanly:

```python
-1 % 3 == 2
```

So if `front` is `0`, moving backward wraps to the last array index.

Insertion at the rear writes after the current last element:

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

Then `size` increases.

Deleting from the rear only needs:

```python
self.size -= 1
```

The rear index is computed from `front` and `size`, so no separate rear pointer needs to be updated.

## Correctness

The implementation maintains this invariant:

```text
The deque elements occupy size positions starting at front, wrapping around the array if needed.
```

For `insertFront`, the algorithm moves `front` one position backward and stores the new value there. This places the value before all existing elements, so it becomes the new front.

For `insertLast`, the algorithm writes to `(front + size) % capacity`, which is exactly the first empty slot after the current rear. This places the value after all existing elements, so it becomes the new rear.

For `deleteFront`, the algorithm moves `front` one position forward and decreases `size`. This removes the old front from the logical deque.

For `deleteLast`, the algorithm decreases `size`. Since the rear index is derived from `front + size - 1`, reducing `size` removes the old rear from the logical deque.

`getFront` returns the element at `front`, which is the first logical element. `getRear` computes the last logical index and returns that value.

The `isEmpty` and `isFull` methods directly compare `size` with `0` and `capacity`, so they correctly detect underflow and overflow conditions.

Therefore, every operation satisfies the required deque behavior.

## Complexity

Let `k` be the capacity.

| Operation | Time | Space |
|---|---:|---:|
| Constructor | `O(k)` | `O(k)` |
| `insertFront` | `O(1)` | `O(1)` |
| `insertLast` | `O(1)` | `O(1)` |
| `deleteFront` | `O(1)` | `O(1)` |
| `deleteLast` | `O(1)` | `O(1)` |
| `getFront` | `O(1)` | `O(1)` |
| `getRear` | `O(1)` | `O(1)` |
| `isEmpty` | `O(1)` | `O(1)` |
| `isFull` | `O(1)` | `O(1)` |

## Alternative: Track Both Front and Rear

Another valid design stores both `front` and `rear` pointers.

In that version, `rear` points to the current rear element.

This can make `getRear` simpler, but every insert and delete must update both pointer state and size carefully.

The `front + size` design keeps less state, which reduces the chance of pointer drift.

## Testing

```python
def run_tests():
    dq = MyCircularDeque(3)

    assert dq.insertLast(1) is True
    assert dq.insertLast(2) is True
    assert dq.insertFront(3) is True
    assert dq.insertFront(4) is False
    assert dq.getRear() == 2
    assert dq.isFull() is True
    assert dq.deleteLast() is True
    assert dq.insertFront(4) is True
    assert dq.getFront() == 4

    dq = MyCircularDeque(1)
    assert dq.isEmpty() is True
    assert dq.getFront() == -1
    assert dq.getRear() == -1
    assert dq.insertFront(10) is True
    assert dq.isFull() is True
    assert dq.insertLast(20) is False
    assert dq.getFront() == 10
    assert dq.getRear() == 10
    assert dq.deleteFront() is True
    assert dq.deleteLast() is False

    dq = MyCircularDeque(2)
    assert dq.insertLast(1) is True
    assert dq.insertLast(2) is True
    assert dq.deleteFront() is True
    assert dq.insertLast(3) is True
    assert dq.getFront() == 2
    assert dq.getRear() == 3

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Official-style sequence | Checks normal insert, delete, full state |
| Capacity `1` | Checks front and rear are same element |
| Wraparound case | Confirms circular indexing works |