본문 바로가기

Programming/Data Structure

자료구조 · C++로 구현한 덱


덱 (Deque)


덱은 Double-Ended Queue의 약자이며, 양쪽에서 원소의 삽입과 삭제가 가능한 선형 자료구조이다.

큐와 스택을 합친 형태라고 생각하면 된다. 원형 큐(Circular Queue)와 비슷하게 구현하므로, 이전 글을 참조.


  • 한쪽에 push 하고 같은 쪽에서 pop 하면, 스택처럼 사용할 수 있다.
  • 한쪽에 push 하고 반대쪽에서 pop 하면, 큐처럼 사용할 수 있다.






Deque C++ 구현 소스코드


#include <iostream>
using namespace std;

const int MAX = 1e5;

class Deque {
private:
    int data[MAX];
    int index_front;
    int index_back;
public:
    Deque();
    bool empty();
    void push_front(int x);
    void push_back(int x);
    void pop_front();
    void pop_back();
    int front();
    int back();
    int size();
};

Deque::Deque() {
    index_front = 0;
    index_back = 0;
}

bool Deque::empty() {
    return index_front == index_back;
}

void Deque::push_front(int x) {
    data[index_front] = x;
    index_front = (index_front-1+MAX) % MAX;
}

void Deque::push_back(int x) {
    index_back = (index_back+1) % MAX;
    data[index_back] = x;
}

void Deque::pop_front() {
    index_front = (index_front+1) % MAX;
}

void Deque::pop_back() {
    index_back = (index_back-1+MAX) % MAX;
}

int Deque::front() {
    return data[(index_front+1)%MAX];
}

int Deque::back() {
    return data[index_back];
}

int Deque::size() {
    return (index_back-index_front+MAX)%MAX;
}

int main() {
    Deque dq;
    for (int i=1; i<=3; i++) dq.push_front(i);  // Push front 1~3
    dq.pop_front();     // Pop front
    for (int i=4; i<=6; i++) dq.push_back(i);   // Push back 4~6
    dq.pop_back();      // Pop back
    dq.push_front(7);   // Push front 7
    Deque dq2 = dq;     // Copy deque
    cout << "* Pop Back: ";
    while (!dq.empty()) {
        cout << dq.back() << " -> ";
        dq.pop_back();  // Pop back all
    }
    cout << "\n* Pop Front: ";
    while (!dq2.empty()) {
        cout << dq2.front() << " -> ";
        dq2.pop_front();  // Pop front all
    }
    return 0;
}


# main 함수 출력 결과


* Size: 5
* Pop Back: 5 -> 4 -> 1 -> 2 -> 7 ->
* Pop Front: 7 -> 2 -> 1 -> 4 -> 5 ->


✓ 배열로 구현한 덱이다. 예외 처리는 하지 않았다.





Deque 클래스 설명


const int MAX = 1e5;

class Deque {
private:
    int data[MAX];
    int index_front;
    int index_back;
public:
    Deque();
    bool empty();
    void push_front(int x);
    void push_back(int x);
    void pop_front();
    void pop_back();
    int front();
    int back();
    int size();
};


✓ MAX는 덱의 최대 사이즈이다. 값을 바꾸면 최대 사이즈를 조절할 수 있다.

✓ Data는 덱에 넣은 원소를 저장하는 배열이다.

✓ index_front는 앞에 넣은 원소의 위치를 가리키는 변수다.

✓ index_back은 뒤에 넣은 원소의 위치를 가리키는 변수다.




# 생성자와 empty 함수


Deque() {
    index_front = 0;
    index_back = 0;
}

bool empty() {
    return index_front == index_back;
}


✓ 생성자를 이용하여 Front 인덱스, Back 인덱스를 둘 다 0으로 초기화한다.

✓ empty 함수는 덱이 비어있는지 확인하는 함수이다. Front 인덱스와 Back 인덱스가 서로 같다면, 덱이 비어있는 상태이다.



# push_front, push_back 함수


void push_front(int x) {
    // Full check
    data[index_front] = x;
    index_front = (index_front-1+MAX) % MAX;
}

void push_back(int x) {
    // Full check
    index_back = (index_back+1) % MAX;
    data[index_back] = x;
}


✓ 덱에 원소를 집어넣는다. push_front 함수는 덱의 앞에 원소를 넣으며, push_back 함수는 덱의 뒤에 원소를 넣는다.

✓ 원소를 넣기 전에, 덱이 꽉 찬 상태인지 확인하여 예외 처리를 해야 한다.



# pop_front, pop_back 함수


void pop_front() {
    // Empty check
    index_front = (index_front+1) % MAX;
}

void pop_back() {
    // Empty check
    index_back = (index_back-1+MAX) % MAX;
}


✓ 덱에서 원소를 제거한다. pop_front 함수는 덱의 가장 앞에 있는 원소를 빼고, pop_back 함수는 덱의 가장 뒤에 있는 원소를 뺀다.

✓ 원소를 빼기 전에, 덱이 비어있는 상태인지 확인하여 예외 처리를 해야 한다.



# front, back 함수


int front() {
    // Empty check
    return data[(index_front+1)%MAX];
}

int back() {
    // Empty check
    return data[index_back];
}


✓ front 함수는 가장 앞에 넣은 원소가 무엇인지 보는 함수이다.

✓ back 함수는 가장 뒤에 넣은 원소가 무엇인지 보는 함수이다.

✓ 두 함수 모두, 덱이 비어있는 상태인지 확인하여 예외 처리를 해야 한다.



# size 함수


int size() {
    return (index_back-index_front+MAX)%MAX;
}


✓ 덱에 몇 개의 원소가 들어있는지 확인하는 함수이다.



  • 송동훈 2019.11.17 21:48 댓글주소 수정/삭제 댓글쓰기

    안녕하세요 글 잘 읽었습니다. 궁금한게 하나 있는데요. empty여부를 판단할 때 front_index와 back_index를 비교하셨는데, 비어있을 때도 조건을 만족하지만, 데이터를 계속 넣다가 front_index와 back_index가 같아지는 경우도 있지 않나요?