641. Design Circular Deque
Difficulty: Medium
Topics: Array, Linked List, Design, Queue
Design your implementation of the circular double-ended queue (deque).
Implement the MyCircularDeque class:
-
MyCircularDeque(int k)Initializes the deque with a maximum size ofk. -
boolean insertFront()Adds an item at the front of Deque. Returnstrueif the operation is successful, orfalseotherwise. -
boolean insertLast()Adds an item at the rear of Deque. Returnstrueif the operation is successful, orfalseotherwise. -
boolean deleteFront()Deletes an item from the front of Deque. Returnstrueif the operation is successful, orfalseotherwise. -
boolean deleteLast()Deletes an item from the rear of Deque. Returnstrueif the operation is successful, orfalseotherwise. -
int getFront()Returns the front item from the Deque. Returns-1if the deque is empty. -
int getRear()Returns the last item from Deque. Returns-1if the deque is empty. -
boolean isEmpty()Returnstrueif the deque is empty, orfalseotherwise. -
boolean isFull()Returnstrueif the deque is full, orfalseotherwise.
Example 1:
- Input:
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
- Output:
[null, true, true, true, false, 2, true, true, true, 4]
- Explanation:
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1); // return True
myCircularDeque.insertLast(2); // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear(); // return 2
myCircularDeque.isFull(); // return True
myCircularDeque.deleteLast(); // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront(); // return 4
Constraints:
1 <= k <= 10000 <= value <= 1000- At most
2000calls will be made toinsertFront,insertLast,deleteFront,deleteLast,getFront,getRear,isEmpty,isFull.
Solution:
We can use an array to represent the deque structure. We'll maintain a head and tail pointer that will help us track the front and rear of the deque, wrapping around when necessary to achieve the circular behavior.
Let's implement this solution in PHP: 641. Design Circular Deque
Here's a step-by-step solution for the MyCircularDeque class:
<?php
class MyCircularDeque {
/**
* @var array
*/
private $deque;
/**
* @var int
*/
private $maxSize;
/**
* @var int
*/
private $front;
/**
* @var int
*/
private $rear;
/**
* @var int
*/
private $size;
/**
* Initialize your data structure here. Set the size of the deque to be k.
*
* @param Integer $k
*/
function __construct($k) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Adds an item at the front of Deque. Return true if the operation is successful.
*
* @param Integer $value
* @return Boolean
*/
function insertFront($value) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Adds an item at the rear of Deque. Return true if the operation is successful.
*
* @param Integer $value
* @return Boolean
*/
function insertLast($value) {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Deletes an item from the front of Deque. Return true if the operation is successful.
*
* @return Boolean
*/
function deleteFront() {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Deletes an item from the rear of Deque. Return true if the operation is successful.
*
* @return Boolean
*/
function deleteLast() {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Get the front item from the deque. If the deque is empty, return -1.
*
* @return Integer
*/
function getFront() {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Get the last item from the deque. If the deque is empty, return -1.
*
* @return Integer
*/
function getRear() {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Checks whether the deque is empty or not.
*
* @return Boolean
*/
function isEmpty() {
...
...
...
/**
* go to ./solution.php
*/
}
/**
* Checks whether the deque is full or not.
*
* @return Boolean
*/
function isFull() {
...
...
...
/**
* go to ./solution.php
*/
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* $obj = MyCircularDeque($k);
* $ret_1 = $obj->insertFront($value);
* $ret_2 = $obj->insertLast($value);
* $ret_3 = $obj->deleteFront();
* $ret_4 = $obj->deleteLast();
* $ret_5 = $obj->getFront();
* $ret_6 = $obj->getRear();
* $ret_7 = $obj->isEmpty();
* $ret_8 = $obj->isFull();
*/
?>
Explanation:
-
Initialization:
- We initialize the deque using an array of size
kand set all values to-1initially. - The
frontandrearpointers are initialized to0. -
sizekeeps track of the current number of elements in the deque.
- We initialize the deque using an array of size
-
insertFront($value):
- Check if the deque is full using
isFull(). - If not, decrement the
frontpointer (with circular wrap-around using modulo). - Place the value at the new
frontand increment thesize.
- Check if the deque is full using
-
insertLast($value):
- Check if the deque is full.
- If not, place the value at the
rearand move therearpointer forward (again using modulo for wrap-around). - Increment the
size.
-
deleteFront():
- Check if the deque is empty using
isEmpty(). - If not, increment the
frontpointer (circular wrap-around) and decrement thesize.
- Check if the deque is empty using
-
deleteLast():
- Check if the deque is empty.
- If not, decrement the
rearpointer and reduce thesize.
-
getFront():
- If the deque is empty, return
-1. - Otherwise, return the element at the
frontpointer.
- If the deque is empty, return
-
getRear():
- If the deque is empty, return
-1. - Otherwise, return the element before the current
rearpointer (sincerearpoints to the next available position).
- If the deque is empty, return
-
isEmpty():
- Returns
trueif the deque is empty (sizeis0).
- Returns
-
isFull():
- Returns
trueif the deque is full (sizeequalsmaxSize).
- Returns
Example Walkthrough
$myCircularDeque = new MyCircularDeque(3); // Initialize deque with size 3
$myCircularDeque->insertLast(1); // return true
$myCircularDeque->insertLast(2); // return true
$myCircularDeque->insertFront(3); // return true
$myCircularDeque->insertFront(4); // return false, deque is full
echo $myCircularDeque->getRear(); // return 2
echo $myCircularDeque->isFull(); // return true
$myCircularDeque->deleteLast(); // return true
$myCircularDeque->insertFront(4); // return true
echo $myCircularDeque->getFront(); // return 4
Time Complexity:
- Each operation (
insertFront,insertLast,deleteFront,deleteLast,getFront,getRear,isEmpty,isFull) runs in O(1) time since they all involve constant-time array operations and pointer manipulations.
Space Complexity:
- The space complexity is O(k), where
kis the size of the deque. We allocate space forkelements in the deque array.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)