본문으로 바로가기

덱은 양방향 큐(Double-Ended Queue)의 약자로 앞단(front)과 뒷단(rear) 모두에서 입출력이 일어나는 자료구조다. 한쪽에서만 입력과 출력이 각각 일어나는 큐와 다르게 덱은 양쪽 모두 입출력을 구현해야 한다.

이번 포스트에서는 환형 배열을 사용하여 양방향 큐를 구현한다. 양방향 큐의 최대 사이즈를 인자로 받아 양방향 큐의 앞단과 뒷단에서 일어나는 입출력 메소드를 정의한다. 효율적인 양방향 큐의 구현을 위해 환형 배열의 개념을 도입하는데 환형 배열의 개념이란 배열의 첫 인덱스와 마지막 인덱스가 연결되어 있는 것처럼 생각하는 것이다.

Implementation

class Deque {

public:
  Deque(const int = 10);
  ~Deque();

  bool empty() const;// 덱이 비어있는지 유무를 반환
  bool full() const;// 덱이 가득차있는지 유무를 반환
  int size() const;// 덱에 저장된 데이터의 개수를 반환
  int front() const;// 가장 먼저 입력된 데이터를 반환
  int back() const;// 가장 최근에 입력된 데이터를 반환

  void push_front(const int);// 덱의 최전방에 데이터를 삽입
  void push_back(const int);// 덱의 최후방에 데이터를 삽입
  int pop_front();// 가장 먼저 입력된 데이터를 삭제하고 반환
  int pop_back();// 가장 최근에 입력된 데이터를 삭제하고 반환

  void display() const;

private:
  int _front;// 데이터가 삽입될 최전방의 인덱스
  int _rear;// 데이터가 삽입될 최후방의 인덱스
  int _size;// 덱에 입력된 데이터의 개수
  int _size_of_array;// 데이터를 저장할 배열의 사이즈
  int* _data;// 데이터를 저장할 배열

};
inline void error(const char *message) {
  printf("%s\n", message);
  exit(1);
}

Deque::Deque(const int size): _front(0), _rear(1), _size(0), _size_of_array(size), _data(new int[size]) {
  // 생성자는 배열의 사이즈를 인자로 받아 배열을 동적으로 할당한다
  // 환형 배열의 개념을 사용하기 때문에 _front와 _rear의 값은
  // 어떤 값으로 초기화해도 무방하나 _rear의 값이 _front의 값보다
  // 1이 크도록 초기화시켜주면 된다
}

Deque::~Deque() {
  delete[] _data;// 동적으로 할당된 배열을 해제
}

bool Deque::empty() const {
  return size() == 0;
}

bool Deque::full() const {
  return size() == _size_of_array;
}

int Deque::size() const {
  return _size;
}

int Deque::front() const {
  if (empty()) error("Deque is empty");
  // _front는 최전방에 삽입될 데이터의 인덱스를 가리키기 때문에
  // _front보다 한 칸 뒤에 있는 인덱스가 가장 먼저 입력된 데이터이다
  int front_index = (_front + 1) % _size_of_array;
  return _data[front_index];
}

int Deque::back() const {
  if (empty()) error("Deque is empty");
  // _rear는 최후방에 삽입될 데이터의 인덱스를 가리키기 때문에
  // _rear보다 한 칸 앞에 있는 인덱스가 가장 최근에 입력된 데이터이다
  // 음수값 방지를 위해 _size_of_array를 한 번 더해줘야 한다
  int rear_index =  (_rear - 1 + _size_of_array) % _size_of_array;
  return _data[rear_index];
}

void Deque::push_front(const int data) {
  if (full()) error("Deque is full");
  // _front 인덱스에 데이터를 삽입하고 _front의 인덱스를 한 칸 앞으로 옮긴다
  // 음수값 방지를 위해 _size_of_array를 한 번 더해줘야 한다
  _data[_front] = data;
  _front = (_front - 1 + _size_of_array) % _size_of_array;
  _size++;
}

void Deque::push_back(const int data) {
  if (full()) error("Deque is full");
  // _rear 인덱스에 데이터를 삽입하고 _rear의 인덱스를 한 칸 뒤로 옮긴다
  _data[_rear] = data;
  _rear = (_rear + 1) % _size_of_array;
  _size++;
}

int Deque::pop_front() {
  if (empty()) error("Deque is empty");
  // _front는 최전방에 삽입될 데이터의 인덱스를 가리키기 때문에
  // _front보다 한 칸 뒤에 있는 인덱스가 가장 먼저 입력된 데이터이다
  _front = (_front + 1) % _size_of_array;
  _size--;
  return _data[_front];
}

int Deque::pop_back() {
  if (empty()) error("Deque is empty");
  // _rear는 최후방에 삽입될 데이터의 인덱스를 가리키기 때문에
  // _rear보다 한 칸 앞에 있는 인덱스가 가장 최근에 입력된 데이터이다
  // 음수값 방지를 위해 _size_of_array를 한 번 더해줘야 한다
  _rear = (_rear - 1 + _size_of_array) % _size_of_array;
  _size--;
  return _data[_rear];
}

void Deque::display() const {
  if (empty()) {
    printf("Deque is empty\n");
    return;
  }
  printf("size(): %d\n", size());
  printf("front(): %d\n", front());
  printf("back(): %d\n", back());
  printf("(front) ");
  int i = (_front + 1) % _size_of_array;
  do {
    printf("%d ", _data[i]);
    i = (i+1) % _size_of_array;
  } while (i != _rear);
  printf("(rear)\n");
}

Performance Analysis

Time Complexity
empty full size front back push pop
O(1) O(1) O(1) O(1) O(1) O(1) O(1)

댓글을 달아 주세요