3-3. [C++] 배열로 구현한 큐

배열을 이용해 정수(int)를 저장하는 큐를 구현해보자.

일단 정수를 저장할 1차원 배열이 필요하다. 이를 int data[MAX_QUEUE_SIZE] 라고 하자. (MAX_QUEUE_SIZE는 큐에 저장할 수 있는 최대 요소 개수를 나타낸다.)

또, 큐에서는 삽입 연산을 위한 변수 rear와 삭제 연산을 위한 변수 front가 필요하다.

큐를 처음 생성하면 rear와 front는 0으로 초기화한다.

 

원형 큐에서는 rear와 front가 원의 형태로 계속 순환한다.

두 변수를 순환시키는 것은 나머지 연산자인 mod 연산으로 처리한다.

 

front ← (front + 1) mod MAX_QUEUE_SIZE;
rear ← (rear + 1) mod MAX_QUEUE_SIZE;

mod 연산으로 인해 front와 rear의 값은 (MAX_QUEUE_SIZE - 1)에서 하나 증가되면 0이 된다.

(0 → 1 → 2 → 3 → 4 → 5 → 6 → 7 → 0 → 1 → ... )

enqueue(x) 연산의 유사 코드

enqueue(x)

rear ← (rear + 1) mod MAX_QUEUE_SIZE;
data[rear] ← x;

dequeue() 연산의 유사 코드

dequeue()

front ← (front + 1) mod MAX_QUEUE_SIZE;
return data[front];

---

본격적으로 큐를 구현하기 전에 큐의 ADT를 바탕으로 UML 다이어그램을 설계해보자.

UML 다이어그램을 바탕으로 C++ 클래스로 큐를 구현해보자.

클래스 상속을 위해 circularQueue.h와 circularQueue.cpp 두 파일로 분리했다.

// circularQueue.h
#include <iostream>
using namespace std;
#define MAX_QUEUE_SIZE 100

inline void errorPrint(const char *message) { cout << message << endl; exit(1); }

class CircularQueue {
protected:
    int front;
    int rear;
    int data[MAX_QUEUE_SIZE];

public:
    CircularQueue() { front = rear = 0; }

    bool isEmpty() { return front == rear; }
    bool isFull() { return ((rear + 1) % MAX_QUEUE_SIZE) == front; }

    void enqueue(int x) {
        if (isFull()) errorPrint("Queue overflow");

        rear = (rear + 1) % MAX_QUEUE_SIZE;
        data[rear] = x;
    }

    int dequeue() {
        if (isEmpty()) errorPrint("Queue underflow");

        front = (front + 1) % MAX_QUEUE_SIZE;
        return data[front];
    }
    int peek() {
        if (isEmpty()) errorPrint("Queue underflow");

        return data[(front + 1) % MAX_QUEUE_SIZE];
    }

    void display() {
        cout << "큐 내용 : ";
        int maxIdx = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;
        for (int i = front + 1; i <= maxIdx; i++) {
            cout << '[' << data[i % MAX_QUEUE_SIZE] << ']' << ' ';
        }
        cout << endl;
    }
};

// circularQueue.cpp
#include "circularQueue.h"

int main() {
    CircularQueue queue;
    for (int i = 1; i < 10; i++) {
        queue.enqueue(i);
    }
    queue.display();

    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    
    queue.display();
}

/*
실행 결과 : 
큐 내용 : [1] [2] [3] [4] [5] [6] [7] [8] [9]
큐 내용 : [4] [5] [6] [7] [8] [9]
*/

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.