[코딩 테스트 합격자 되기 C++ 편] 07 큐

07-1 큐의 개념

큐(Queue)는 '줄을 서다'라는 뜻을 가지고 있다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조이다.

이러한 큐의 특징을 선입선출 또는 FIFO(First In First Out)이라고 한다.

스택과 마찬가지로 큐도 삽입하는 연산은 푸시, 꺼내는 연산은 팝이라고 한다.

 

큐에서 데이터가 이동하는 과정 살펴보기

빈 큐 선언부터 Push, Pop까지의 과정

큐의 특성을 활용하는 분야

• 작업 대기열 : 네트워크 통신 시 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리한다. 이 때, 큐를 활용할 수 있다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있다.

이 외에도 여러 이벤트가 발생했을 때, 순서대로 처리할 때나 심지어는 실생활에서도 영화관에서 줄을 서는 사람들을 처리해야 할 때, 먼저 줄을 선 사람을 먼저 처리하는 등 다양하게 사용되고 있다.

 

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean 값을 반환한다.
	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값을 반환한다.
	void push(ItemType item)	큐에 데이터를 푸시한다.
	ItemType pop()	큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환한다.
상태	int front	큐에서 가장 마지막에 팝한 위치를 기록한다.
	int rear	큐에서 최근에 푸시한 데이터의 위치를 기록한다.
	ItemType data[maxsize]	큐의 데이터를 관리하는 배열. 최대 maxsize 개의 데이터를 관리한다.

큐의 세부 동작에 대해 조금 더 자세히 알아보기

1. isFull() 연산으로 현재 큐가 가득 찼는지 확인하고 큐가 가득 차지 않았으면 rear를 +1한 다음 rear가 가리키는 위치에 item을 푸시한다.
2. 이 상태에서 팝을 하면,
   1. isEmpty() 연산을 통해 큐가 비었는지 확인한다.
   2. 만약 비어 있지 않다면 front를 +1한다. 이렇게 하면 front와 end가 0으로 같아지므로 isEmpty() 연산 시 큐가 빈 것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있다.
3. 계속해서 푸시를 진행해본다.
   1. isFull() 연산을 통해 가득 차지 않았다면 푸시를 진행하게 된다.
4. 큐가 가득 찼을 때 푸시를 하게되면,
   1. rear가 maximize - 1과 같아지게 된다. 즉, isFull() 연산의 값이 true가 되어 푸시하지 못하게 된다.

생각해볼만한 부분은 큐가 관리하는 데이터가 이렇게 되면 front의 다음부터 rear까지 관리한다는 점이다. 실제 배열에 존재하는 데이터의 개수는 큐가 관리하는 데이터 + 1개이므로 메모리 공간이 낭비된 상황이다.

이렇게 된 이유는 큐를 한 방향으로 관리하고 있기 때문인데, 이를 개선하기 위해서는 다른 형태의 큐가 필요하다. 바로 원형 큐이다.

 

큐 구현하기

C++ STL에서 제공하는 큐의 push(), pop(), front(), empty() 연산은 모두 시간 복잡도가 O(1)이다.

#include <iostream>
#include <queue>

int main()
{
    queue<int> q;

    q.push(10);
    q.push(20);
    q.push(30);

    cout << "Front: " << q.front() << endl;

    while(!q.empty())
    {
        cout << q.front() << "을 큐에서 삭제했습니다." << endl;
        q.pop();
    }
    
    cout << "큐가 비어있나요? " << (q.empty() ? "Yes" : "No") << endl;

    return 0;
}