자료구조 · 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;
}

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

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

티스토리툴바

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

티스토리툴바