Formatted question description: https://leetcode.ca/all/641.html

641. Design Circular Deque

Level

Medium

Description

Design your implementation of the circular double-ended queue (deque).

Your implementation should support following operations:

MyCircularDeque(k): Constructor, set the size of the deque to be k.
insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
getRear(): Gets the last item from Deque. If the deque is empty, return -1.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  			// return 2
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();			// return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Deque library.

Background knowledge: queue vs deque

queue vs deque. Reference: https://www.quora.com/What-is-the-difference-between-queue-and-deque

Queue

Queue is who ever gets in first gets out first i.e First In First Out(FIFO). like a line in front of a super market counter. It is used when there is a single resource(cashier) who has to do the tasks(billing) of all the requests(shoppers in line who want to get the items billed)

Deque

Deque(pronounced as deck) is double ended queue i.e the elements can be added or removed at either end of the line. It is used in situations when there are multiple requests(customers who want their items to be billed) but the contract is such that as soon as the cashier from other counter completes all the requests he can take over the left over requests(customers) from the opposite end of the line. This helps to use up the resource efficiently and requests are cleared at a faster rate.

Solution - one pointer

Similar to 622-Design-Circular-Queue

(2 pointers solution is obvious btw)

Attributes:

self.q: An array of fixed size k, initialized with zeros, used to store the elements of the deque.
self.front: An integer that indicates the current front position of the deque.
self.size: An integer that tracks the current number of elements in the deque.
self.capacity: The maximum number of elements the deque can hold, which is determined by the value k passed to the constructor.

Methods:

`init(self, k: int)`

Initializes the deque with a fixed size k. It sets up the storage array self.q, initializes self.front to 0, self.size to 0, and self.capacity to k.

`insertFront(self, value: int) -> bool`

Inserts an element at the front of the deque. If the deque is not full, it calculates the new front position (taking care to wrap around if necessary using modulo arithmetic) and inserts the new value. The size is then incremented.

`insertLast(self, value: int) -> bool`

Adds an element at the rear of the deque. It calculates the position for the new element based on the current front position and size, then inserts the value. The size is incremented.

`deleteFront(self) -> bool`

Removes an element from the front of the deque. If the deque is not empty, it moves the front pointer to the next element (with wrap-around) and decrements the size.

`deleteLast(self) -> bool`

Deletes an element from the rear of the deque. It simply decrements the size if the deque is not empty.

`getFront(self) -> int`

Returns the value of the front element in the deque. If the deque is empty, it returns -1.

`getRear(self) -> int`

Retrieves the value of the last element in the deque. It calculates the position of the last element using the front position and size, and returns its value. Returns -1 if the deque is empty.

`isEmpty(self) -> bool`

Checks if the deque is empty by comparing the size to 0.

`isFull(self) -> bool`

Determines if the deque is full by comparing the size to the capacity.

Circular Arithmetic:

The circular nature of the deque is maintained using modulo arithmetic (% self.capacity) for operations involving the front pointer and index calculations. This approach ensures that when the front or rear of the deque reaches the end of the array, it wraps around to the beginning, thus making efficient use of the fixed-size storage array.

public class Design_Circular_Deque {

    // ref: https://www.cnblogs.com/Dylan-Java-NYC/p/12079440.html
    class MyCircularDeque {
        int [] arr;
        int start;
        int end;
        int len;
        int k;

        /** Initialize your data structure here. Set the size of the deque to be k. */
        public MyCircularDeque(int k) {
            arr = new int[k];
            start = -1;
            end = -1;
            len = 0;
            this.k = k;
        }

        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        public boolean insertFront(int value) {
            if(isFull()){
                return false;
            }

            if(start == -1){
                start = 0;
            }else{
                start = (start - 1 + k) % k;
            }

            arr[start] = value;
            if(end == -1){
                end = start;
            }

            len++;
            return true;
        }

        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        public boolean insertLast(int value) {
            if(isFull()){
                return false;
            }

            end = (end + 1) % k;
            arr[end] = value;
            if(start == -1){
                start = end;
            }

            len++;
            return true;
        }

        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        public boolean deleteFront() {
            if(isEmpty()){
                return false;
            }

            start = (start + 1) % k;
            len--;
            return true;
        }

        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        public boolean deleteLast() {
            if(isEmpty()){
                return false;
            }

            end = (end - 1 + k) % k;
            len--;
            return true;
        }

        /** Get the front item from the deque. */
        public int getFront() {
            return isEmpty() ? -1 : arr[start];
        }

        /** Get the last item from the deque. */
        public int getRear() {
            return isEmpty() ? -1 : arr[end];
        }

        /** Checks whether the circular deque is empty or not. */
        public boolean isEmpty() {
            return len == 0;
        }

        /** Checks whether the circular deque is full or not. */
        public boolean isFull() {
            return len == k;
        }
    }

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */
}

############

class MyCircularDeque {
    private int[] q;
    private int front;
    private int size;
    private int capacity;

    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        q = new int[k];
        capacity = k;
    }

    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        if (!isEmpty()) {
            front = (front - 1 + capacity) % capacity;
        }
        q[front] = value;
        ++size;
        return true;
    }

    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        int idx = (front + size) % capacity;
        q[idx] = value;
        ++size;
        return true;
    }

    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        --size;
        return true;
    }

    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if (isEmpty()) {
            return false;
        }
        --size;
        return true;
    }

    /** Get the front item from the deque. */
    public int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return q[front];
    }

    /** Get the last item from the deque. */
    public int getRear() {
        if (isEmpty()) {
            return -1;
        }
        int idx = (front + size - 1) % capacity;
        return q[idx];
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return size == 0;
    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return size == capacity;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque obj = new MyCircularDeque(k);
 * boolean param_1 = obj.insertFront(value);
 * boolean param_2 = obj.insertLast(value);
 * boolean param_3 = obj.deleteFront();
 * boolean param_4 = obj.deleteLast();
 * int param_5 = obj.getFront();
 * int param_6 = obj.getRear();
 * boolean param_7 = obj.isEmpty();
 * boolean param_8 = obj.isFull();
 */

// OJ: https://leetcode.com/problems/design-circular-deque/
// Time: O(1) for all
// Space: O(K)
class MyCircularDeque {
    vector<int> q;
    int begin = 0, end = 0, k, cnt = 0;
public:
    MyCircularDeque(int k) : q(k), k(k) {}
    bool insertFront(int value) {
        if (cnt == k) return false;
        begin = (begin - 1 + k) % k;
        q[begin] = value;
        ++cnt;
        return true;
    }
    bool insertLast(int value) {
        if (cnt == k) return false;
        q[end] = value;
        end = (end + 1) % k;
        ++cnt;
        return true;
    }
    bool deleteFront() {
        if (cnt == 0) return false;
        begin = (begin + 1) % k;
        --cnt;
        return true;
    }
    bool deleteLast() {
        if (cnt == 0) return false;
        end = (end - 1 + k) % k;
        --cnt;
        return true;
    }
    int getFront() {
        if (cnt == 0) return -1;
        return q[begin];
    }
    int getRear() {
        if (cnt == 0) return -1;
        return q[(end - 1 + k) % k];
    }
    bool isEmpty() {
        return cnt == 0;
    }
    bool isFull() {
        return cnt == k;
    }
};

class MyCircularDeque:
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.q = [0] * k
        self.front = 0
        self.size = 0
        self.capacity = k

    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        if not self.isEmpty():
            self.front = (self.front - 1 + self.capacity) % self.capacity
        self.q[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if self.isFull():
            return False
        idx = (self.front + self.size) % self.capacity
        self.q[idx] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        # basically, welcome to overwirte it behind frond
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
        # basically, welcome to overwirte
        self.size -= 1
        return True

    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        if self.isEmpty():
            return -1
        return self.q[self.front]

    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        if self.isEmpty():
            return -1
        idx = (self.front + self.size - 1) % self.capacity
        return self.q[idx]

    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        return self.size == 0

    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        return self.size == self.capacity


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

############

class MyCircularDeque(object):

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.queue = []
        self.size = k
        self.front = 0
        self.rear = 0

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.insert(0, value)
            self.rear += 1
            return True
        else:
            return False
        

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.append(value)
            self.rear += 1
            return True
        else:
            return False

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop(0)
            self.rear -= 1
            return True
        else:
            return False

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop()
            self.rear -= 1
            return True
        else:
            return False

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.front]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.rear -1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return self.front == self.rear

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return self.rear - self.front == self.size


# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()

type MyCircularDeque struct {
	q        []int
	size     int
	front    int
	capacity int
}

func Constructor(k int) MyCircularDeque {
	q := make([]int, k)
	return MyCircularDeque{q, 0, 0, k}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	if !this.IsEmpty() {
		this.front = (this.front - 1 + this.capacity) % this.capacity
	}
	this.q[this.front] = value
	this.size++
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	idx := (this.front + this.size) % this.capacity
	this.q[idx] = value
	this.size++
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.front = (this.front + 1) % this.capacity
	this.size -= 1
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.size -= 1
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.q[this.front]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.q[(this.front+this.size-1)%this.capacity]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return this.size == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return this.size == this.capacity
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.InsertFront(value);
 * param_2 := obj.InsertLast(value);
 * param_3 := obj.DeleteFront();
 * param_4 := obj.DeleteLast();
 * param_5 := obj.GetFront();
 * param_6 := obj.GetRear();
 * param_7 := obj.IsEmpty();
 * param_8 := obj.IsFull();
 */

class MyCircularDeque {
    private vals: number[];
    private length: number;
    private size: number;
    private start: number;
    private end: number;

    constructor(k: number) {
        this.vals = new Array(k).fill(0);
        this.start = 0;
        this.end = 0;
        this.length = 0;
        this.size = k;
    }

    insertFront(value: number): boolean {
        if (this.isFull()) {
            return false;
        }

        if (this.start === 0) {
            this.start = this.size - 1;
        } else {
            this.start--;
        }
        this.vals[this.start] = value;
        this.length++;
        return true;
    }

    insertLast(value: number): boolean {
        if (this.isFull()) {
            return false;
        }

        this.vals[this.end] = value;
        this.length++;
        if (this.end + 1 === this.size) {
            this.end = 0;
        } else {
            this.end++;
        }
        return true;
    }

    deleteFront(): boolean {
        if (this.isEmpty()) {
            return false;
        }

        if (this.start + 1 === this.size) {
            this.start = 0;
        } else {
            this.start++;
        }
        this.length--;
        return true;
    }

    deleteLast(): boolean {
        if (this.isEmpty()) {
            return false;
        }

        if (this.end === 0) {
            this.end = this.size - 1;
        } else {
            this.end--;
        }
        this.length--;
        return true;
    }

    getFront(): number {
        if (this.isEmpty()) {
            return -1;
        }

        return this.vals[this.start];
    }

    getRear(): number {
        if (this.isEmpty()) {
            return -1;
        }

        if (this.end === 0) {
            return this.vals[this.size - 1];
        }
        return this.vals[this.end - 1];
    }

    isEmpty(): boolean {
        return this.length === 0;
    }

    isFull(): boolean {
        return this.length === this.size;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * var obj = new MyCircularDeque(k)
 * var param_1 = obj.insertFront(value)
 * var param_2 = obj.insertLast(value)
 * var param_3 = obj.deleteFront()
 * var param_4 = obj.deleteLast()
 * var param_5 = obj.getFront()
 * var param_6 = obj.getRear()
 * var param_7 = obj.isEmpty()
 * var param_8 = obj.isFull()
 */

641 - Design Circular Deque

641. Design Circular Deque

Level

Description

Background knowledge: queue vs deque

Solution - one pointer

Attributes:

Methods:

`init(self, k: int)`

`insertFront(self, value: int) -> bool`

`insertLast(self, value: int) -> bool`

`deleteFront(self) -> bool`

`deleteLast(self) -> bool`

`getFront(self) -> int`

`getRear(self) -> int`

`isEmpty(self) -> bool`

`isFull(self) -> bool`

Circular Arithmetic:

All Problems

All Solutions

Welcome to Subscribe On Youtube

641. Design Circular Deque

Level

Description

Background knowledge: queue vs deque

Solution - one pointer

Attributes:

Methods:

__init__(self, k: int)

insertFront(self, value: int) -> bool

insertLast(self, value: int) -> bool

deleteFront(self) -> bool

deleteLast(self) -> bool

getFront(self) -> int

getRear(self) -> int

isEmpty(self) -> bool

isFull(self) -> bool

Circular Arithmetic:

All Problems

All Solutions

`init(self, k: int)`

`insertFront(self, value: int) -> bool`

`insertLast(self, value: int) -> bool`

`deleteFront(self) -> bool`

`deleteLast(self) -> bool`

`getFront(self) -> int`

`getRear(self) -> int`

`isEmpty(self) -> bool`

`isFull(self) -> bool`