#2 큐 - 배열 기반의 큐의 문제점과 순환 큐 구현하기

1. 배열 기반의 큐의 문제점?

지난 시간에 배열 기반의 큐를 구현하였을때 문제점을 찾지 못했는가?

대부분 아래와 같은 문제를 찾았을 것이다.

6의 용량을 가진 큐가 제거 연산을 수행할 때 마다 용량이 줄어들고 있다.

그렇다고 아래처럼 제거 연산 후 하나씩 옆으로 옮기기에는 비용이 너무 크다.

이 문제를 해결하려면 큐의 시작과 끝을 연결해서 순환할 수 있는 순환 큐(Circular Queue)로 만들면 된다.

아래처럼 순환큐를 만들면 제거연산 후에도 같은 용량을 가질 수 있다.

2. 순환 큐 구현하기

1) 큐, 노드 구조 구현하기

우선 Xcode를 열고 CircularQueue 프로젝트를 만든 다음에 CircularQueue.cpp, hpp를 만들어준다.

큐의 노드와 큐의 구조는 이전시간에 구현한 것과 fullFlag 변수가 추가된것 빼고는 달라진게 없다.

(CircularQueue.hpp)

#include <stdlib.h>
 
class Node {
public:
    int Data;
};
 
 
class CircularQueue {
private:
    int capacity;
    int front;
    int rear;
    Node *nodes;
    bool fullFlag;
public:
    CircularQueue(int _capacity);
    void DestroyCircularQueue();
    void EnQueue(int newData);
    int DeQueue();
};
 

2) 내부 함수 구현하기

먼저 큐의 노드를 자유저장소에 할당하고 제거하는 함수를 구현해보자.

큐 private 멤버변수 fullFlag의 초기화를 제외하곤 달라진게 없다.

(CircularQueue.cpp에 추가)

CircularQueue::CircularQueue(int _capacity) {
    nodes = (Node*)malloc(sizeof(Node) * _capacity);
    capacity = _capacity;
    front = 0;
    rear = 0;
    fullFlag = false;
}
 
void CircularQueue::DestroyCircularQueue() {
    free(nodes);
}

그 다음은 큐의 데이터 삽입과 삭제다. 큐가 비어있는지 꽉 차있는지는 fullFlag를 이용하여 구분할 것이다.

또한 front나 rear가 capacity - 1과(배열 인덱스가 0으로 시작하기 때문) 같으면 0으로 만들어준다.

fullFlag는 EnQueue() 함수를 통해 1씩 증가된 rear가 front와 같아지면 true가 된다.

(CircularQueue.cpp에 추가)

void CircularQueue::EnQueue(int newData) {
    if(fullFlag) {
        printf("Queue is full\n");
        return;
    }
    nodes[rear].Data = newData;
    rear = (rear == capacity - 1) ? 0 : rear+1;
    if(rear == front) fullFlag = true;
}
 
int CircularQueue::DeQueue() {
    int result = 0;
 
    if(front == rear && !fullFlag) {
        printf("Queue is empty\n");
        return -1;
    }
    result = nodes[front].Data;
    front = (front == capacity - 1) ? 0 : front+1;
    fullFlag = false;
    return result;
}

front, rear, fullFlag를 확인하기 위해 디버그 함수를 추가해준다.

(CircularQueue.hpp CircularQueue 클래스 public 멤버에 추가)

int getFront();
int getRear();
bool isFull();

(CircularQueue.cpp에 추가)

int CircularQueue::getRear() {
    return rear;
}
 
int CircularQueue::getFront() {
    return front;
}
 
bool CircularQueue::isFull() {
    return fullFlag;
}

이제 순환 큐 구현이 끝났다.

3. 테스트 해보기

이제 구현한 순환큐를 테스트해보자.

(main.cpp)

#include <iostream>
#include "CircularQueue.hpp"
 
int main(int argc, const char * argv[]) {
    CircularQueue queue(10);
 
    std::cout << "---------------EnQueue 1---------------" << std::endl;
    for(int i=0;i<4;i++) {
        queue.EnQueue(i);
        std::cout << "Data : " << i << " Front : " << queue.getFront() << " Rear : " << queue.getRear() << " isFull? " << queue.isFull() << std::endl;
    }
 
    std::cout << std::endl << "---------------DeQueue 1---------------" << std::endl;
    for(int i=0;i<6;i++) {
        std::cout << "Data : " << queue.DeQueue() << " Front : " << queue.getFront() << " Rear : " << queue.getRear() << " isFull? " << queue.isFull() << std::endl;
    }
 
    std::cout << std::endl << "---------------EnQueue 2---------------" << std::endl;
    for(int i=0;i<15;i++) {
        queue.EnQueue(i);
        std::cout << "Data : " << i << " Front : " << queue.getFront() << " Rear : " << queue.getRear() << " isFull? " << queue.isFull() << std::endl;
    }
 
    std::cout << std::endl << "---------------DeQueue 2---------------" << std::endl;
    for(int i=0;i<12;i++) {
        std::cout << "Data : " << queue.DeQueue() << " Front : " << queue.getFront() << " Rear : " << queue.getRear() << " isFull? " << queue.isFull() << std::endl;
    }
 
    queue.DestroyCircularQueue();
}

우선 10 용량의 순환 큐를 생성해준다. 그 다음 0~3까지 데이터를 큐에 삽입한다. 그 후 6번 출력을 실행한다. 그리고 다시 0~14까지 데이터를 큐에 삽입한다. 마지막으로 12번 출력을 실행한다. 우리가 작성한 코드로 출력을 예상해보면 0~3까지 데이터가 삽입되고 다시 0~3까지 출력된 다음 "Queue is empty" 라는 경고가 2번 출력되고, 0~9까지의 데이터가 삽입된 다음 "Queue is full" 경고가 5번 출력, 마지막으로 0~9까지 데이터가 출력되고, "Queue is empty" 경고가 2번 출력될 것이다.

실행 결과는 다음과 같다.

이번 시간에는 순환 큐를 만들어 보았다. 다음에는 링크드 리스트를 이용하여 큐를 만들어보자.