Leetcode: Design Circular Deque
This question is asked at Amazon and Facebook, and is as follows:
Design your implementation of the circular double-ended queue (deque).
Your implementation should support these:
MyCircularDeque(k) : Constructor to set the size of the Deque to be k.
insertFront: Adds the item at the front of the Deque, and return true if the operation is successful.
insertLast: Adds the item to the back of the Deque and Return true if the operation is successful.
deleteFront() : Deletes an item from the front of the Deque and return true if the operation is successful.
deleteLast(): Deletes an item from the rear of the Deque, returns true if the operation is successful.
getFront() gets the front item from the Deque or return -1.
getRear() gets the last item from Deque and returns -1 if Deque is empty.
isEmpty() checks whether the Deque is empty or now.
isFull() checks whether the Deque is full or not.
The first thing we need to do is initialize the head and the tail and point the next of the tail to the head and the size equal to zero.
For the insert front, what we want to do is to initialize just a head connected to a tail double linked list, as follows:
insertlast puts an element after the tail and before tail.next which means put the node in between the tail and the element before the tail. That is, unless the queue is full.
Unless the queue is empty, deleteFront() would both decrement the size and change the index of the front of the array.
The deleteLast() method deletes the item from the rear of the queue by changing the index of the array again.
The insertFront() method inserts an element to the front of the Deque and increases the size, inserting the front to the last element of the array, otherwise, we decrement the previous front and put the front as the first element, and put the new front in the array.
Getfront() returns the element with an index on the front and getRear() returns the element with an index on the back.
isEmpty and isFull checks if the size == 0 or arr.length, respectively.
class MyCircularDeque {
int[] arr;
int front;
int rear;
int size;
//initialize the front, rear, size, and circular buffer.
public MyCircularDeque(int k) {
this.front = 0;
this.rear = -1;
this.size = 0;
arr = new int[k];
}
//insert to the front, if front is last element go back to zero otherwise decrement front
//add the size, move the front back and insert a new front.
//increment the size.
public boolean insertFront(int value) {
if(size == arr.length) return false;
if(front == 0) {
front = arr.length - 1;
} else {
--front;
}
if(size == 0) {
rear = front;
}
this.size++;
arr[front] = value;
return true;
}
//add an item the the rear of the deque by making the rear first the next element and assigning the rear value.
public boolean insertLast(int value) {
if(size == arr.length) return false;
this.rear = (rear + 1) % arr.length;
if(size == 0) front = rear;
arr[rear] = value;
this.size++;
return true;
}
//decrement the size, reset the front (front is in the back? da f? )
public boolean deleteFront() {
if(size == 0) return false;
size--;
this.front = (front + 1) % arr.length;
return true;
}
//decrement the back, reset the rear circularly
public boolean deleteLast() {
if(size == 0) return false;
size--;
if(rear == 0){
rear = arr.length - 1;
} else {
rear--;
}
return true;
}
//return the front index
public int getFront() {
if(size == 0) {
return -1;
}
return arr[front];
}
//return the rear index
public int getRear() {
if(size == 0) {
return -1;
}
return arr[rear];
}
//return if size is zero.
public boolean isEmpty() {
return size == 0;
}
}
Comments
Post a Comment