47-Implement-Deque.md

Implement Deque

Problem Link

Practice Problem

---

Pattern

• Queue
• Deque
• Design

---

Approach

Use a circular array with front and rear indices to support insert and delete at both ends.

---

Time Complexity

O(1) per operation

Space Complexity

O(k)

---

Java Solution

class MyDeque {
    private int[] arr;
    private int front = 0, size = 0;

    public MyDeque(int k) {
        arr = new int[k];
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + arr.length) % arr.length;
        arr[front] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        arr[(front + size) % arr.length] = value;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % arr.length;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        size--;
        return true;
    }

    public int getFront() { return isEmpty() ? -1 : arr[front]; }
    public int getRear() { return isEmpty() ? -1 : arr[(front + size - 1 + arr.length) % arr.length]; }
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == arr.length; }
}