Design Circular Deque[M,Array,Linked List,Design,Queue]

https://leetcode.com/problems/design-circular-deque/description/

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

Implement the MyCircularDeque class:

• MyCircularDeque(int k) Initializes the deque with a maximum size of k.
• boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
• int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
• boolean isEmpty() Returns true if the deque is empty, or false otherwise.
• boolean isFull() Returns true if the deque is full, or false otherwise.

 

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 <= 1000
• 0 <= value <= 1000
• At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

드디어 나온 최종시험st 문제이다. 보니까 "Design" 이라는 category에 요런 느낌의 문제가 많다.

 

시험에서 자주 물어보는게 Py,C,C++로 특정 Data Structure를 구현할 수 있냐를 물어보고,

또는 Search/Sorting/Merge 할 수 있냐를 물어보니까 이런 느낌의 문제를 많이 풀어봐야한다.

 

1. Python

class MyCircularDeque:
    def __init__(self, k: int):
        self.capa = k
        self.size = 0
        self.deque = []

    def insertFront(self, value: int) -> bool:
        if self.isFull() :return False
        else:
            if self.deque != []:
                self.deque.insert(0,value)
                self.size+=1
            else :
                self.deque.append(value)
                self.size+=1            
        return True
    def insertLast(self, value:int) -> bool:
        if self.isFull() :return False
        self.deque.append(value)
        self.size+=1
        return True
    def deleteFront(self) -> bool:
        if self.isEmpty():return False
        self.deque.pop(0)
        self.size-=1
        return True
    def deleteLast(self) -> bool:
        if self.isEmpty():return False
        self.deque.pop()
        self.size-=1
        return True
    def getFront(self) -> int:
        if self.isEmpty():return -1
        return self.deque[0]

    def getRear(self) -> int:
        if self.isEmpty():return -1
        return self.deque[self.size-1]

    def isEmpty(self) -> bool:
        return self.size == 0
    def isFull(self) -> bool:
        return self.size == self.capa
        


# 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()

 

문제를 풀긴했는데,, 굉장히 찝찝하다.

만능소스인 List를 써버려서 치팅을 한 느낌이 든다 ㅋ;;

 

2. C

 

사실상 C / C++로 풀길 원했던 문제들..

 

C에도 Struct Constructor를 만드는 지 몰랐다. 아 진짜 개복잡하네. 답지를 봐버렸음

typedef struct {
    int *arr;
    int front;
    int rear;
    int size;
    int capacity;
} MyCircularDeque;


MyCircularDeque* myCircularDequeCreate(int k) {
    MyCircularDeque* obj = (MyCircularDeque*)malloc(sizeof(MyCircularDeque));
    obj -> size = 0;
    obj -> rear = 0;
    obj -> front = 0;
    obj -> capacity = k;
    obj -> arr = (int*)malloc(k*sizeof(int));
    return obj;
}
// constructor?
bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
    return obj->size == 0;
}

bool myCircularDequeIsFull(MyCircularDeque* obj) {
    return obj->size == obj->capacity;
}
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
    if(myCircularDequeIsFull(obj)) return false;
    obj -> front = (obj -> front -1 + obj->capacity) % obj->capacity;
    obj -> arr[obj -> front] = value;
    obj -> size++;
    return true;
}

bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
    if(myCircularDequeIsFull(obj)) return false;
    obj->arr[obj->rear] = value;
    obj->rear = (obj->rear + 1) % obj->capacity;
    obj->size++;
    return true;        
}

bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) {
        return false;
    }
    obj->front = (obj->front + 1) % obj->capacity;
    obj->size--;
    return true;    
}

bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) {
        return false;
    }
    obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;
    obj->size--;
    return true;    
}

int myCircularDequeGetFront(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) {
        return -1;
    }
    return obj->arr[obj->front];    
}

int myCircularDequeGetRear(MyCircularDeque* obj) {
    if (myCircularDequeIsEmpty(obj)) {
        return -1;
    }
    return obj->arr[(obj->rear - 1 + obj->capacity) % obj->capacity];    
}



void myCircularDequeFree(MyCircularDeque* obj) {
    free(obj->arr);
    free(obj);
}

/**
 * Your MyCircularDeque struct will be instantiated and called as such:
 * MyCircularDeque* obj = myCircularDequeCreate(k);
 * bool param_1 = myCircularDequeInsertFront(obj, value);
 
 * bool param_2 = myCircularDequeInsertLast(obj, value);
 
 * bool param_3 = myCircularDequeDeleteFront(obj);
 
 * bool param_4 = myCircularDequeDeleteLast(obj);
 
 * int param_5 = myCircularDequeGetFront(obj);
 
 * int param_6 = myCircularDequeGetRear(obj);
 
 * bool param_7 = myCircularDequeIsEmpty(obj);
 
 * bool param_8 = myCircularDequeIsFull(obj);
 
 * myCircularDequeFree(obj);
*/

 

풀다보니까 문제가 깔끔하지가 않다.

특히 capa랑 % 연산 쓰는 게 좀 애매함.. C++은 Skip한다.