큐(Queue) 자료구조 | 백준 18258번 문제

1. 큐(Queue)란 무엇인가

큐는 데이터를 먼저 넣은 순서대로 꺼내는 구조를 가진 자료구조다.
영어로는 “Queue”라고 하며, FIFO(First In, First Out) 구조라고 부른다.
즉, 먼저 들어온 데이터가 먼저 나가는 방식이다.

은행 창구에 줄을 서는 모습을 떠올리면 이해하기 쉽다.
먼저 온 사람이 먼저 업무를 보고, 나중에 온 사람은 뒤에서 기다린다.
이와 달리, 스택(Stack)은 나중에 넣은 데이터가 먼저 나오는 LIFO(Last In, First Out) 구조다.

 

 

2. 큐의 기본 동작

큐는 보통 다음과 같은 동작을 수행한다.

• push : 데이터를 큐의 뒤쪽(rear)에 추가한다.
• pop : 큐의 앞(front)에서 데이터를 꺼내고 제거한다.
• front : 큐의 가장 앞 데이터를 확인한다.
• back : 큐의 가장 뒤 데이터를 확인한다.
• size : 큐에 들어 있는 데이터의 개수를 구한다.
• empty : 큐가 비어 있으면 1, 아니면 0을 반환한다.

이 동작들은 운영체제의 프로세스 관리, 네트워크 패킷 처리, BFS 탐색 등
다양한 분야에서 기본적으로 사용된다.

 

 

다음은 큐의 기본 동작을 간단히 시뮬레이션한 예시다.

push 10   → [10]
push 20   → [10, 20]
push 30   → [10, 20, 30]
pop       → [20, 30]     (10 제거)
front     → 20
back      → 30
size      → 2
empty     → 0

 

큐는 앞(front)에서 꺼내고, 뒤(rear)에서 넣는다.
즉, 데이터를 넣는 위치는 rear, 꺼내는 위치는 front다.

3. 큐 구현하기

배열과 두 개의 인덱스 front, rear를 이용하면 큐를 간단히 구현할 수 있다.

• front : 큐의 맨 앞을 가리킨다.
• rear : 큐의 맨 뒤 다음 위치를 가리킨다.

데이터를 추가하면 rear를 하나 증가시키며 데이터를 넣고,
데이터를 꺼내면 front를 하나 증가시키며 데이터를 제거한다.
이렇게 하면 한쪽에서 데이터를 넣고 다른 쪽에서 꺼내는 선입선출(FIFO) 구조를 만들 수 있다.

#define MAX 2000000   // 큐의 최대 크기
int queue[MAX];       // 데이터를 저장할 배열
int front = 0;        // 큐의 맨 앞 인덱스
int rear = 0;         // 큐의 맨 뒤 다음 인덱스

• queue[MAX] : 큐의 데이터를 저장하는 공간
• front : 현재 큐의 맨 앞 위치
• rear : 다음 데이터를 삽입할 위치

rear는 항상 마지막 데이터의 다음 위치를 가리킨다.
데이터를 넣을 때는 queue[rear++] = x,
꺼낼 때는 queue[front++]로 처리한다.

4. 백준 18258번 문제 설명

이 문제는 정수를 저장하는 큐(Queue) 를 직접 구현하는 문제다.
입력으로 주어지는 명령을 하나씩 처리하면서 그 결과를 출력해야 한다.

명령의 종류는 다음과 같다.

push X : 정수 X를 큐의 뒤에 넣는다.
pop : 큐의 앞에 있는 정수를 빼고 출력한다. 만약 큐가 비어 있으면 -1을 출력한다.
size : 큐에 들어 있는 정수의 개수를 출력한다.
empty : 큐가 비어 있으면 1, 아니면 0을 출력한다.
front : 큐의 맨 앞에 있는 정수를 출력한다. 없으면 -1을 출력한다.
back : 큐의 맨 뒤에 있는 정수를 출력한다. 없으면 -1을 출력한다.

 

예를 들어, 다음과 같은 입력이 들어오면

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

 

출력은 아래와 같다.

 

순서	명령어	출력	큐 상태
1	push 1		[1]
2	push 2		[1, 2]
3	front	1	[1, 2]
4	back	2	[1, 2]
5	size	2	[1, 2]
6	empty	0	[1, 2]
7	pop	1	[2]
8	pop	2	[]
9	pop	-1	[]
10	size	0	[]
11	empty	1	[]
12	pop	-1	[]
13	push 3		[3]
14	empty	0	[3]
15	front	3	[3]

 

5. 함수별 구현과 설명

 

(1) push 함수 – 데이터 추가

void push(int x) {
    queue[rear++] = x;
}

• 새로운 데이터를 큐의 맨 뒤에 넣는다.
• rear가 다음 인덱스로 이동하면서 새로운 삽입 위치를 준비한다.

예)
push(5) 실행 시 → [5]
rear가 1 증가하여 다음 공간을 가리킴.

 

(2) pop 함수 – 데이터 제거

int pop() {
    if (front == rear) return -1;  // 큐가 비어 있음
    return queue[front++];
}

• 큐의 맨 앞 데이터를 꺼내서 반환한다.
• front를 한 칸 이동시켜 다음 데이터를 가리킨다.
• front == rear이면 큐가 비어 있으므로 -1을 반환한다.

예)
[10, 20, 30] 상태에서 pop() 실행 → 10 출력, 큐는 [20, 30]

 

(3) size 함수 – 데이터 개수 확인

int size() {
    return rear - front;
}

• 큐의 전체 크기는 rear - front로 계산된다.
• rear는 넣은 횟수, front는 뺀 횟수를 의미한다.

예)
rear = 5, front = 3 → size = 2

 

(4) empty 함수 – 큐 비어 있는지 확인

int empty() {
    return (front == rear) ? 1 : 0;
}

• 큐가 비어 있으면 1, 아니면 0을 반환한다.
• front와 rear가 같을 때 큐에 데이터가 존재하지 않는다.

 

(5) front_value 함수 – 맨 앞 데이터 확인

int front_value() {
    if (front == rear) return -1;
    return queue[front];
}

 

• 큐의 맨 앞 데이터를 확인만 한다. (제거하지 않음)
• 비어 있으면 -1을 반환한다.

 

 

(6) back_value 함수 – 맨 뒤 데이터 확인

int back_value() {
    if (front == rear) return -1;
    return queue[rear - 1];
}

 

• 큐의 맨 뒤 데이터를 반환한다.
• rear - 1이 마지막 데이터의 실제 위치다.
• 큐가 비어 있으면 -1을 반환한다.

 

 

6. 전체 코드

#include <stdio.h>
#include <string.h>

#define MAX 2000000

int queue[MAX];
int front = 0;
int rear = 0;

void push(int x) {
    queue[rear++] = x;
}

int pop() {
    if (front == rear) return -1;
    return queue[front++];
}

int size() {
    return rear - front;
}

int empty() {
    return (front == rear) ? 1 : 0;
}

int front_value() {
    if (front == rear) return -1;
    return queue[front];
}

int back_value() {
    if (front == rear) return -1;
    return queue[rear - 1];
}

int main() {
    int N;
    char command[10];
    int x;

    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        scanf("%s", command);

        if (!strcmp(command, "push")) {
            scanf("%d", &x);
            push(x);
        }
        else if (!strcmp(command, "pop")) {
            printf("%d\n", pop());
        }
        else if (!strcmp(command, "size")) {
            printf("%d\n", size());
        }
        else if (!strcmp(command, "empty")) {
            printf("%d\n", empty());
        }
        else if (!strcmp(command, "front")) {
            printf("%d\n", front_value());
        }
        else if (!strcmp(command, "back")) {
            printf("%d\n", back_value());
        }
    }

    return 0;
}