[자료구조] Queue/큐 & 배열을 통한 큐 구현 :: C++

 

728x90

1. Queue란?

• 선입 선출(First In First Out) 즉 먼저 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다.
• 우리의 실생활에서 가장 많이 볼 수 있다. ex) 대기열, 프린터 큐
• 시간 복잡도 : O(1)

---

 

2. Queue 구현

구현해본 기능은

1. Push : 원소를 큐에 넣음

2. Pop : 큐에 가장 먼저 들어간 원소를 제거

3. Front : 큐에 가장 먼저 들어간 원소를 출력

4. Size : 큐에 들어가있는 원소의 갯수를 출력

5. IsEmpty : 큐가 비었는지 확인

6. IsFull : 큐가 다 찼는지 확인

 

나는 처음에 사용자한테 queue의 사이즈를 입력받아서 구현했고, 원형 큐 형태로 구현했기 때문에 실제로 사용자가 입력한 큐의 사이즈보다 -1만큼 적게 사용한다. 그래서 입력 받은 사이즈+1 만큼 공간을 생성해줬다.

#include <iostream>
#include <cstdlib>

using namespace std;

class Queue{
private:
    int *arr;
    int front;
    int rear;
    int capacity;
    int count;
    
public:
    Queue(int size);
    ~Queue();

    void Push(int value);
    void Pop();
    int Front();

    int Size();
    bool IsEmpty();
    bool IsFull();
};

Queue::Queue(int size) {
    capacity = size+1;
    arr = new int[capacity];
    front = 0;
    rear = 0;
    count = 0;
}

Queue::~Queue() {
    delete[] arr;
}

void Queue::Push(int value) {
    if(IsFull()) {
        cout << "Queue에 공간이 부족합니다." << "\n";
        exit(EXIT_FAILURE);
    }
    cout << "Push : " << value << "\n";
    rear = (rear+1)%capacity;
    arr[rear] = value;
    count++;
}

void Queue::Pop() {
    if(IsEmpty()) {
        cout << "Queue에 값이 없습니다." << "\n";
        exit(EXIT_FAILURE);
    }

    cout << "Pop : " << Front() << "\n";
    count--;
    front = (front+1) % capacity;
}

int Queue::Front() {
    if(IsEmpty()) {
        cout << "Queue가 비었습니다." << "\n";
        exit(EXIT_FAILURE);        
    }
    else {
        return arr[(front+1) % capacity];
    }
}

int Queue::Size() {
    return count;
}

bool Queue::IsEmpty() {
    return front == rear;
}

bool Queue::IsFull() {
    return front == (rear + 1)%capacity;
}

void menuPrint() {
    cout << "==============Queue===============" << "\n";
    cout << "[1] Push" << "\n";
    cout << "[2] Pop" << "\n";
    cout << "[3] front" << "\n";
    cout << "[4] Size" << "\n";
    cout << "[5] Empty" << "\n";
    cout << "[Exit] Exit(1~5제외 아무키나 누르세요)" << "\n";
}

int main() {
    int size;
    cout << "Queue의 크기를 할당하세요 : ";
    cin >> size;
    cout << endl;
    Queue queue(size);

    while(true) {
        menuPrint();
        char cmd;
        cin >> cmd;
        if(cmd == '1') {
            int value;
            cout << "Push할 값 입력 : ";
            cin >> value;
            queue.Push(value);
        }
        else if(cmd == '2') {
            queue.Pop();
        }
        else if(cmd == '3') {
            cout << "front : " << queue.Front() << "\n";
        }
        else if(cmd == '4') {
            cout << queue.Size() << "\n";
        }
        else if(cmd == '5') {
            if(queue.IsEmpty()) {
                cout << "Queue가 비었습니다." << "\n";
            }
            else {
                cout << "Queue에 값이 존재합니다." << "\n";
            }
        }
        else {
            exit(0);
        }
    }
}

 

3. 원형 큐(Circular Queue)

위에서 구현한 큐는 선형 큐가 아닌 원형 큐를 구현한 것이다. 원형 큐가 탄생한 이유는 선형 큐에는 문제점이 있기 때문이다. 선형 큐에서는 pop(dequeue)연산을 하게되면 앞쪽의 원소가 빠진 자리의 공간을 활용하지 못하여 공간을 낭비하게 된다. 하지만 원형 큐에서는 나머지 연산(modulus)을 활용하여 front와 rear의 위치를 변경해줬다. 

>> push 연산 시 : (rear+1) % capacity | pop 연산 시  : (front+1)%capacity

front는 실제로 값이 존재하는 위치 -1번째에 항상 위치하고 rear는 마지막으로 들어온 값이 존재하는 위치에 위치한다. 위의 코드에서 시작할 떄 front와 rear는 0번째에 위치하고 있고, 값을 Push하면 rear+1의 위치에 입력되는 것이 이 로직이다.

 

그럼 실제 값이 존해하는 위치-1번째 즉 0번째 인덱스는 그냥 아무 이유없이 비어있게 되는데?

이 생각이 맞다. 그 이유는 큐를 구현하는 방법에 있다. 큐를 구현할 때 공간 전체를 사용하고 싶으면 이전에 어떤 연산을 했는지를 저장하면 된다. 만약 마지막 연산이 push연산이고 현재 front==rear이면 현재 큐는 포화상태라고 볼 수 있다. 반대로 마지막 연산이 pop연산이고 현재 front==rear이면 현재 큐는 비어있다고 볼 수 있다. 하지만 마지막 연산을 저장하게 되면 삽입과 삭제하는 시간이 느려지게 되고 queue를 사용하는 상황은 push와 pop연산이 많기 때문에 차라리 공간 1개를 덜 사용하고 시간을 줄이는 방법이 훨씬 좋다. 

CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.
내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐