Crocus

Stack, Queue, Deque

1. Deque란?

Deque는 스택과 큐가 함께 합쳐진 자료구조이다.

우선 스택이 뭔지, 큐가 뭔지 이해하고 있어야 한다.

스택 원리( LIFO(Last In First Out) )

STL stack이 뭔지 알아보고

https://www.acmicpc.net/problem/10828 문제 풀어보기

큐 원리( FIFO(Frist In First Out) )

STL queue가 뭔지 알아보고

https://www.acmicpc.net/problem/10845 문제 풀어보기

이 두 과정이 이해가 됐다면 이제 우리는 deque를 짜 봐야 한다.

** 스택, 큐 부터 알려주고 deque라는 것도 알려주세요 **

어짜피 스택 + 큐 = deque라서 우리는 스택, 큐를 따로 공부할 필요가 없다.

deque에서 함수를 몇개 제거하면 스택이되고, 큐가 되기 때문이다.

(+ 시간이 얼마 없다. 스택과 큐를 할 시간에 deque한번으로 두개를 끝내고자 한다.)

deque라는 것은 앞으로 넣어나 뒤로 넣거나 앞으로 빼거나 뒤로 빼거나 모든 것이 가능하다.

이 과정을 이제 더미노드를 이용한 이중 연결리스트를 이용하여 작성해볼 수 있다.

push_front, pop_front :: 큐를 의미한다.

push_back, pop_back :: 스택을 의미한다.

따라서 deque를 만들고 front 함수를 지우면 스택이 되고, back 함수를 지우면 큐가 된다.

STL deque가 뭔지 알아보고

https://www.acmicpc.net/problem/10866 문제 풀기

2. deque 소스 코드

이전에 배운 더미노드가 있는 이중 연결리스트를 잘 생각하면서 코딩을 해보자.

헷갈릴때는 절대 생각으로 하지말고 그림을 그려가며 해보자

코딩 후 위의 3문제 모두 STL을 쓰지 말고 자신이 코딩한 deque로 제출해보기

#include <iostream>
#include <cstdio>
 
using namespace std;
 
class NODE{
    friend class DEQUE;
 
private:
    int data;
    NODE *left;
    NODE *right;
};
 
class DEQUE {
private:
    int sz;
    NODE *head;
    NODE *tail;
    
public:
    DEQUE(){
        //cout << "\n\n생성자 호출\n\n" << endl;
        sz = 0;
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
    }
 
    ~DEQUE() {
        init();
        delete head;
        delete tail;
 
        //cout << "\n\n소멸자 호출\n\n " << endl; 
    }
 
    void init() {
        // 더미노드 사이 모든 값 삭제
        NODE *pos = head;
        while (pos->right != NULL)
        {
            NODE *delNode = pos;
            pos = pos->right;
 
            delete delNode;
        }
        delete tail; // 마지막 tail이 삭제되지 않았다.
 
        // 더미노드 새로 생성(생성자와 동일)
        NODE *dummyHead = new NODE;
        NODE *dummyTail = new NODE;
 
        dummyHead->left = dummyHead->right = NULL;
        dummyTail->left = dummyTail->right = NULL;
 
        head = dummyHead;
        tail = dummyTail;
        sz = 0;
    }
    void push_front(int val){
        if (head->right == NULL)
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->left = head;
            head->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
 
        else
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->right = head->right;
            head->right->left = newNode;
 
            newNode->left = head;
            head->right = newNode;
        }
 
        sz++;
    }
 
    void push_back(int val) {
        if (head->right == NULL)
        {
            NODE *newNode = new NODE;
            newNode->data = val;
 
            newNode->left = head;
            head->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
 
        else
        {
            NODE *newNode = new NODE;
            newNode->data = val;
            
            newNode->left = tail->left;
            tail->left->right = newNode;
 
            newNode->right = tail;
            tail->left = newNode;
        }
 
        sz++;
    }
 
    void pop_front() {
        if (!sz)
            cout << "deque가 비어있습니다." << endl;
        else
        {
            NODE *pos = head->right;
            head->right->right->left = head;
            head->right = head->right->right;
            
            delete pos;
 
            sz--;
        }
    }
    void pop_back() {
        if (!sz)
            cout << "deque가 비어있습니다." << endl;
        else
        {
            NODE *pos = tail->left;
            tail->left->left->right = tail;
            tail->left = tail->left->left;
 
            delete pos;
 
            sz--;
        }
    }
    int front() {
        if (!sz)
            cout << "deque가 비어있습니다." << endl;
        else
            return head->right->data;
    }
    int back() {
        if (!sz)
            cout << "deque가 비어있습니다." << endl;
        else
            return tail->left->data;
    }
    void all() {
        NODE *pos = head;
        while (pos != NULL)
        {
            // 더미노드는 출력하지 않는다.
            if (!(pos == head || pos == tail))
                cout << pos->data << " ";
        
            pos = pos->right;
        }
        cout << endl;
    }
 
    int size() {
        return sz;
    }
 
    bool empty() {
        return !sz;
    }
};
void menu() {
    cout << "┏━━━━━━━━━━━━━━━━┓" << endl;
    cout << "┃ 1 :: init　　　┃" << endl;
    cout << "┃ 2 :: push_front┃" << endl;
    cout << "┃ 3 :: push_back ┃" << endl;
    cout << "┃ 4 :: pop_front ┃" << endl;
    cout << "┃ 5 :: pop_back　┃" << endl;
    cout << "┃ 6 :: front　　 ┃" << endl;
    cout << "┃ 7 :: back　　　┃" << endl;
    cout << "┃ 8 :: all 　　　┃" << endl;
    cout << "┃ 9 :: size　　　┃" << endl;
    cout << "┃ 10 :: empty　　┃" << endl;
    cout << "┃ 11 :: exit　　 ┃" << endl;
    cout << "┗━━━━━━━━━━━━━━━━┛" << endl;
}
int main()
{
    DEQUE dq;
    cout << "Datastructure :: Deque" << endl;
    while (1)
    {
        menu();
 
        int num;
        cin >> num;
 
        if (num == 1)
            dq.init();
 
        else if (num == 2)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            dq.push_front(val);
        }
 
        else if (num == 3)
        {
            int val;
            cout << "값 :: ";
            cin >> val;
            dq.push_back(val);
        }
 
        else if (num == 4)
            dq.pop_front();
 
        else if (num == 5)
            dq.pop_back();
 
        else if (num == 6)
            cout << dq.front() << endl;
 
        else if (num == 7)
            cout << dq.back() << endl;
 
        else if (num == 8)
            dq.all();
 
        else if (num == 9)
            cout << dq.size() << endl;
 
        else if (num == 10)
            cout << (dq.empty() ? "empty" : "non empty") << endl;
 
        else if (num == 11)
            break;
        cout << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

Crocus

저작자표시 비영리 변경금지

'Tutoring > Data Structure' 카테고리의 다른 글

튜터링 연습문제 1주차 (0)	2018.03.21
hash (0)	2018.03.04
heap (0)	2018.03.04
Tree, Binary Tree, Tree traversal (0)	2018.03.01
Double Linked List (0)	2018.02.28

Crocus

Stack, Queue, Deque

'Tutoring > Data Structure' 카테고리의 다른 글

티스토리툴바