본문으로 바로가기

큐는 데이터를 순차적으로 저장하고 입력된 데이터 중 가장 먼저 입력된 데이터 순서대로 반환하는 선입선출(First In First Out)의 대표적인 자료구조다. 때문에 큐의 앞단(front)에서 출력이 일어나고 큐의 뒷단(rear)에서 입력이 일어난다.

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

Implementation

class Queue {

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

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

  void push_back(const int);// 큐에 데이터를 삽입
  int pop_front();// 가장 먼저 입력된 데이터를 삭제하고 반환

  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);
}

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

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

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

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

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

int Queue::front() const {
  if (empty()) error("Queue is empty");
  return _data[_front];// 가장 먼저 입력된 데이터를 반환
}

void Queue::push_back(const int data) {
  if (full()) error("Queue is full");
  _data[_rear] = data;
  _rear = (_rear + 1) % _size_of_array;// 환형 배열의 개념을 위해 % 연산자 사용
  _size++;
}

int Queue::pop_front() {
  if (empty()) error("Queue is empty");
  int ret = front();
  _front = (_front + 1) % _size_of_array;// 환형 배열의 개념을 위해 % 연산자 사용
  _size--;
  return ret;
}

void Queue::display() const {
  if (empty()) {
    printf("Queue is empty\n");
    return;
  }
  printf("size(): %d\n", size());
  printf("front(): %d\n", front());
  printf("(front) ");
  int i = _front;
  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 push pop
O(1) O(1) O(1) O(1) O(1) O(1)

댓글을 달아 주세요