Deque 자료구조 만들어보기

 

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

사실 예전에 풀었던 문제인데,

 

다행히(?) 인간은 망각의 동물인지라 초면 인 것 마냥 풀었다.

 

deque 구조의 delete / insert 등등의 method를 한번 구현해 보는 것이 골자!

 

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.

#자료구조 를 만드는 것은 파이썬, C로도 어차피 고기서 고기인 마인드로 풀 수 있으니

 

요번엔 C++하나로 집중해서 풀어보았다.

 

일단 아래와 같이 풀었을 땐, 약간 Naive한 감이 있다.

 

특히 int *arr에서 insert를 앞에서 할 때 새로 int *을 만들어주고 data를 복붙하는 것이 시간소요가 째끔 걸리는 편;;

 

그래도 뭐 어떠한가~ 풀리기만 하면 되지

class MyCircularDeque {
public:
    int* arr;
    int capa, size;
    MyCircularDeque(int k) {
        arr = new int[k]; // how we assign size of array in C++
        size = 0;
        capa = k;
    }
    bool insertFront(int value) {
        if(isFull()) return false;
        else{
            int *temp = new int[capa];
            for(int i=0;i<size;i++){
                temp[i+1]=arr[i];
            }
            temp[0] = value;
            delete[] arr;
            arr = temp;
            size++;
            return true;
        }
    }
    bool insertLast(int value) {
        if(isFull()) return false;
        else{
            arr[size] = value;
            size++;
            return true;
        }
    }
    bool deleteFront(){
        if(isEmpty()) return false;
        else{
            for(int i=0;i<size-1;i++){
                arr[i] = arr[i+1];
            }
            size--;
            return true;
        }
    }
    
    bool deleteLast(){
        if(isEmpty()) return false;
        else{
        size--;
        return true;}
    }
    
    int getFront() {
        if(isEmpty()) return -1;
        return arr[0];
    }
    int getRear() {
        if(isEmpty()) return -1;
        return arr[size-1];
    }
    bool isEmpty() {
        return size==0;
    }
    bool isFull() {
        return size==capa;
    }
};

 

GPT한테 위 코드로 답현했다가 혼나서 효율적인 답변을 하나 받아 보았다.

 

근데 % 쓰는 거부터 뭔가 잘 이해가 안 되고 삐걱거린다 -_-

 

조잡하게도 풀어놨다.

 

그런데 이렇게 하면 TIME O(1)이라 효율적이긴 하다.

 

class MyCircularDeque {
public:
    int* arr;
    int front,rear,capa,size;

    MyCircularDeque(int k) {
        arr = new int[k];
        front = 0;
        capa = k;
        size = 0;
        rear = k-1;
    }
    
    bool insertFront(int value) {
        if(isFull()) return false;
        front = (front-1+capa)%capa;
        arr[front] = value;
        size++;
        return true;
    }
    bool insertLast(int value) {
        if(isFull()) return false;
        rear = (rear+1)%capa;
        arr[rear] = value;
        size++;
        return true;
    }
    bool deleteFront() {
        if(isEmpty()) return false;
        front = (front+1)%capa;
        size--;
        return true;   
    }
    bool deleteLast() {
        if(isEmpty()) return false;
        rear = (rear-1+capa)%capa;
        size--;
        return true;           
    }
    int getFront() {
        return isEmpty() ? -1 : arr[front];   
    }
    int getRear() {
        return isEmpty() ? -1 : arr[rear];   
    }
    bool isEmpty() {
        return size==0;
    }
    bool isFull() {
        return size==capa;
    }
};

/**
 * 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();
 */

 

뭐,, Node struct를 class 내부에 만들어서 푸는 방법도 있으니 참고하면 좋을 듯 하다.

 

#include <iostream>

struct Node {
    int value;
    Node* prev;
    Node* next;
    
    Node(int val) : value(val), prev(nullptr), next(nullptr) {}
};

class MyCircularDeque {
public:
    int size, capacity;
    Node* head;
    Node* tail;
    
    MyCircularDeque(int k) {
        capacity = k;
        size = 0;
        head = nullptr;
        tail = nullptr;
    }

    bool insertFront(int value) {
        if (isFull()) return false;
        Node* newNode = new Node(value);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) return false;
        Node* newNode = new Node(value);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) return false;
        Node* temp = head;
        if (head == tail) {  // Only one element
            head = tail = nullptr;
        } else {
            head = head->next;
            head->prev = nullptr;
        }
        delete temp;
        size--;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) return false;
        Node* temp = tail;
        if (head == tail) {  // Only one element
            head = tail = nullptr;
        } else {
            tail = tail->prev;
            tail->next = nullptr;
        }
        delete temp;
        size--;
        return true;
    }

    int getFront() {
        return isEmpty() ? -1 : head->value;
    }

    int getRear() {
        return isEmpty() ? -1 : tail->value;
    }

    bool isEmpty() {
        return size == 0;
    }

    bool isFull() {
        return size == capacity;
    }

    ~MyCircularDeque() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};

 

근데 나는 이걸 좀 더 내 스타일로 아래와 같이 만들어 봤다.

맥락은 비슷함!

 

// solve it with doubly linked list!
struct Node{
    int val;
    Node* prev;
    Node* next;
    Node(int a):val(a),prev(nullptr),next(nullptr){}
};
class MyCircularDeque {
public:
    int size;
    int capa;
    Node* head;
    Node* tail;
    MyCircularDeque(int k) {
        capa = k;
        size = 0;
        head = nullptr;
        tail = nullptr;
    }
    
    bool insertFront(int value) {
        if(isFull()) return false;
        Node* new_node = new Node(value);
        if(!head){
            head = new_node;
            tail = new_node;
        }else{
            new_node -> next = head;
            head -> prev = new_node;
            head = new_node;
        }
        size++;
        return true;
    }
    
    bool insertLast(int value) {
        if(isFull()) return false;
        Node* new_node = new Node(value);
        if(isEmpty()){
            head = new_node;
            tail = new_node;
        }else{
            new_node -> prev = tail;
            tail -> next = new_node;
            tail = new_node;
        }
        size++;
        return true;        
    }
    bool deleteFront() {
        if(isEmpty()) return false;
        Node* temp = head;
        head = head->next;

        if(head) head -> prev = nullptr;
        else tail = nullptr;

        delete temp;
        size--;
        return true;
    }
    bool deleteLast() {
        if(isEmpty()) return false;
        Node* temp = tail;
        tail = tail->prev;

        if(tail) tail -> next = nullptr;
        else head = nullptr;

        delete temp;
        size--;
        return true;        
    }
    
    int getFront() {
        return isEmpty() ? -1 : head->val;        
    }
    
    int getRear() {
        return isEmpty() ? -1 : tail->val;
    }
    
    bool isEmpty() {
        return size==0;
    }
    
    bool isFull() {
        return size==capa;
    }
};

/**
 * 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();
 */