Coding Interview Tutorial 136 - Design Circular Queue [LeetCode]

Learn how to design a circular queue easily and efficiently!

Algorithms, data structures, and coding interviews simplified!

This is an important programming interview problem, and we use the LeetCode platform to solve it.

[yashmishra]

People generally assume that we remove from the head and insert to the tail. Weird that you took this opposite assumption, but works nonetheless.

[rajeshg]

Have a question here - when you initialize the Q, my understanding is, both head and tail would point to the same location and the head would be moved as we keep on adding elements. Isn't it true?

[xiangyulv]

When we enqueue and dequeue at the same time, there will be thread safe problem. Could you add more code to make it thread safe? Thank you!

[pulkitkaushik]

head tail part is confusing just mixing both

[swagatpatra]

class MyCircularDeque {

/** Initialize your data structure here. Set the size of the deque to be k. */
LinkedList<Node> list;
Node head, tail;
int size, capacity;

/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
this.list = new LinkedList<Node>();
this.size = 0;
this.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;

Node n = new Node(value);
if (isEmpty()) {
head = n;
tail = head;
}
head.prev = n;
n.next = head;
head = n;
this.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;
Node n = new Node(value);

if (isEmpty()) {
head = n;
tail = n;
}

tail.next = n;
n.prev = tail;
tail = n;
this.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;
head = head.next;
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;
tail = tail.prev;
size--;
return true;
}

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

/** Get the last item from the deque. */
public int getRear() {
if (isEmpty())
return -1;
return tail.value;
}

/** 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;
}
}