Leetcode Problem:
Summary
- Design a circular double-ended queue (deque) with methods to insert elements at the front and rear, delete elements from the front and rear, and check if the queue is empty or full.
Approach
- A circular deque is implemented using a fixed-size array
- The front and rear indices are used to track the current positions of the front and rear elements
- The insertFront, insertLast, deleteFront, and deleteLast methods update the front and rear indices accordingly
- The isEmpty and isFull methods check the front and rear indices to determine if the queue is empty or full.
Complexity
- O(1) for insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull operations
- O(n) for printing the queue, where n is the number of elements in the queue.
Explain
- The MyCircularDeque class is implemented using a fixed-size array of size k+2
- The front and rear indices are used to track the current positions of the front and rear elements
- The insertFront method adds an element at the front of the queue and updates the front index
- The insertLast method adds an element at the rear of the queue and updates the rear index
- The deleteFront method removes an element from the front of the queue and updates the front index
- The deleteLast method removes an element from the rear of the queue and updates the rear index
- The getFront and getRear methods return the front and rear elements respectively
- The isEmpty and isFull methods check if the queue is empty or full by comparing the front and rear indices.
Solution Code:
class MyCircularDeque {
public:
int deque[1001];
int size;
int front;
int rear;
MyCircularDeque(int k) {
size = k+2;
front = rear = 0;
}
bool insertFront(int value) {
if (isFull()) return false;
if (isEmpty()){
rear++;
rear %= size;
}
deque[front--] = value;
front = (front + size) % size;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
if (isEmpty()){
front = (front-1 + size) % size;
}
deque[rear++] = value;
rear %= size;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1)%size;
if ((front + 1)%size == rear){
rear = front;
}
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + size) % size;
if ((rear - 1 + size)%size == front){
front = rear;
}
return true;
}
int getFront() {
if (isEmpty()) return -1;
int getIdx = (front + 1) % size;
return deque[getIdx];
}
int getRear() {
if (isEmpty()) return -1;
int getIdx = (rear - 1 + size) % size;
return deque[getIdx];
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return front == (rear + 1) % size;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
class MyCircularDeque {
public:
int deque[1001];
int size;
int front;
int rear;
MyCircularDeque(int k) {
size = k+2;
front = rear = 0;
}
bool insertFront(int value) {
if (isFull()) return false;
if (isEmpty()){
rear++;
rear %= size;
}
deque[front--] = value;
front = (front + size) % size;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
if (isEmpty()){
front = (front-1 + size) % size;
}
deque[rear++] = value;
rear %= size;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1)%size;
if ((front + 1)%size == rear){
rear = front;
}
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + size) % size;
if ((rear - 1 + size)%size == front){
front = rear;
}
return true;
}
int getFront() {
if (isEmpty()) return -1;
int getIdx = (front + 1) % size;
return deque[getIdx];
}
int getRear() {
if (isEmpty()) return -1;
int getIdx = (rear - 1 + size) % size;
return deque[getIdx];
}
bool isEmpty() {
return front == rear;
}
bool isFull() {
return front == (rear + 1) % size;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
'알고리즘' 카테고리의 다른 글
| Design a Stack With Increment Operation (0) | 2025.02.13 |
|---|---|
| All O`one Data Structure (0) | 2025.02.13 |
| My Calendar II (0) | 2025.02.13 |
| My Calendar I (0) | 2025.02.13 |
| Sum of Prefix Scores of Strings (0) | 2025.02.13 |
짬뽕얼큰하게
