JUNGOL 실력키우기 1697 : 큐(queue)

큐는 먼저 들어온 데이터가 먼저 출력된다. 이러한 구조를 선입선출(FIFO - First In First Out)이라고 한다.

이러한 큐 자료구조는 보통 우리의 생활에서는 매우 일상적인 자료구조이다. 

큐 자료구조의 형태를 가장 흔히 볼 수 있는 게 “줄서기”가 될 것이다. 

은행 창구에서 줄을 서거나, 버스를 기다리기 위해서 줄을 설 경우 가장 먼저 줄을 선 사람이 가장 먼저

은행 업무를 처리하거나, 버스를 타게 된다.(새치기 하는 경우는 생각하지 말자)

그림과 같은 큐 자료구조를 설계하고, 처리조건에 맞는 출력을 하시오.

 

≪처리조건≫
1. 주어지는 명령은 다음의 3가지이다.
2. "i a"는 a라는 수를 큐에 넣는다. 이때, a는 10,000 이하의 자연수이다.
3. "o"는 큐에서 데이터를 빼고, 그 데이터를 출력한다. 만약 큐가 비어있으면, "empty"를 출력한다.
4. "c"는 큐에 있는 데이터의 수를 출력한다.

 

첫줄에 N이 주어진다. N은 주어지는 명령어의 수이다.(1≤N≤100)
둘째 줄부터 N+1줄까지 한 줄에 하나씩 명령이 주어진다.

각 명령에 대한 출력 값을 한 줄에 하나씩 출력한다. 출력내용이 하나도 없는 경우는 주어지지 않는다.

7 i 7 i 5 c o o o c

2 7 5 empty 0

---

조건은 지난번 스택에서 수행했던 것과 동일한 것 같습니다.

그러므로 지난번 코드에서 재사용할 수 있는 부분은 재사용하고 스택을 사용한 부분을 큐로 바꾸기만 하면 될 것 같습니다.

이 부분은 스택은 top에서 모든 입, 출력 처리를 하고 큐는 rear에서 입력을 하고 front에서 출력한다는 것을 이해하면 쉽게 해결할 수 있을 것 같습니다.

이 문제에서는 명령어의 최대 개수가 정해져있으므로 선형 큐로 해결이 가능합니다.

그러나 일반적인 문제에서는 선형 큐로 제작한 경우 잘못된 포화 상태 문제가 발생할 수 있으므로 원형 큐를 구성해야 합니다.

혹은 연결 자료구조로 큐를 구성할 경우 잘못된 포화 상태 문제가 발생하지 않습니다.

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
 
    cin >> n;
 
    // 큐의 최대 개수는 명령어의 개수와 같다.
    int *queue = new int[n];
    int front{ 0 }, rear{ 0 };
 
    while (n)
    {
        char opCode;
        cin >> opCode;
 
        // 입력 처리
        if (opCode == 'i')
        {
            cin >> queue[rear++];
        }
        // 출력 처리
        else if (opCode == 'o')
        {
            // 데이터가 없는 경우
            if (front == rear)
            {
                cout << "empty" << endl;
            }
            // 데이터가 있는 경우
            else
            {
                cout << queue[front++] << endl;
            }
        }
        // 데이터 수 확인
        else if (opCode == 'c')
        {
            cout << rear - front << endl;
        }
 
        n--;
    }
 
    delete[] queue;
}

JUNGOL) 문제은행) 실력키우기) 큐(queue)