[Queue] 줄 서서 처리하는 선입선출(FIFO) 자료구조

큐(Queue) 

프로그래밍에서 데이터를 순차적으로 저장하고 처리해야 하는 상황은 매우 흔합니다. 이때 유용하게 사용되는 자료구조가 바로 큐(Queue) 입니다. 큐는 먼저 들어간 데이터가 먼저 나오는(FIFO, First-In-First-Out) 특성을 가지며, 실제 생활 속 줄 서기와 매우 유사한 구조를 가지고 있습니다. 이러한 특성 덕분에 프로세스 관리, 작업 스케줄링, 너비 우선 탐색(BFS) 등 다양한 분야에서 큐는 필수적으로 활용됩니다.

 

---

1.  큐(Queue)의 개념

큐는 놀이공원의 줄 서기와 같습니다. 먼저 줄을 선 사람이 먼저 놀이기구를 타게 되죠!

큐는 데이터를 먼저 들어온 순서대로 처리하는 선형 자료구조입니다. FIFO (First-In-First-Out) 구조로, 먼저 추가한 데이터가 먼저 제거됩니다.

주요 연산

• enqueue : 큐의 뒤쪽(rear)으로 데이터 추가
• dequeue : 큐의 앞쪽(front)에서 데이터 제거 및 반환
• peek 또는 front : 현재 가장 앞에 있는 데이터 조회
• isEmpty : 큐가 비어있는지 확인

 

---

2.  문제 예시 - 프린터 큐

여러 문서가 인쇄 대기 중일 때, 중요도가 높은 문서를 먼저 인쇄하는 프린터가 있습니다. 주어진 문서들 중, 특정 문서가 몇 번째로 출력되는지를 구하세요.

입출력 예시

문서 중요도 리스트	목표 문서 위치	출력 순서
[2, 1, 3, 2]	2	1
[1, 1, 9, 1, 1, 1]	0	5

문제 풀이 아이디어

• 큐를 사용해 문서를 순서대로 관리
• 매번 가장 앞 문서를 꺼내서,
  • 뒤에 더 높은 중요도의 문서가 있으면 다시 큐에 넣고
  • 그렇지 않으면 출력
• 목표 문서가 몇 번째에 출력되는지 추적

a.  Python

from collections import deque

def printer_queue(priorities, location):
    queue = deque([(v, i) for i, v in enumerate(priorities)])
    order = 0

    while queue:
        current = queue.popleft()
        if any(current[0] < q[0] for q in queue):
            queue.append(current)
        else:
            order += 1
            if current[1] == location:
                return order

• deque 를 사용해 빠른 popleft 를 지원합니다.
• (우선순위, 인덱스) 형태로 저장하여 추적합니다.
• any() 를 통해 뒤에 더 큰 값이 있으면 뒤로 보냅니다.

b.  C++

#include <queue>
#include <vector>
#include <utility>
using namespace std;

int printerQueue(vector<int> priorities, int location) {
    queue<pair<int, int>> q;
    for (int i = 0; i < priorities.size(); ++i)
        q.push({priorities[i], i});
    
    int order = 0;
    while (!q.empty()) {
        auto current = q.front(); q.pop();
        bool hasHigher = false;
        for (auto elem : q) {
            if (elem.first > current.first) {
                hasHigher = true;
                break;
            }
        }
        if (hasHigher) {
            q.push(current);
        } else {
            ++order;
            if (current.second == location)
                return order;
        }
    }
    return -1;
}

• queue<pair<int, int>> 를 사용합니다.
• 범위 기반 for문(for(auto elem : q))으로 확인합니다.

c.  Java

import java.util.*;

class Solution {
    public int printerQueue(int[] priorities, int location) {
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < priorities.length; i++) {
            queue.add(new int[]{priorities[i], i});
        }

        int order = 0;
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            boolean hasHigher = false;
            for (int[] elem : queue) {
                if (elem[0] > current[0]) {
                    hasHigher = true;
                    break;
                }
            }
            if (hasHigher) {
                queue.add(current);
            } else {
                order++;
                if (current[1] == location)
                    return order;
            }
        }
        return -1;
    }
}

• Queue<int[]> 을 사용합니다.
• LinkedList 로 큐를 구현합니다.
• 배열 [priority, index] 로 저장합니다.

d.  JavaScript

function printerQueue(priorities, location) {
    let queue = priorities.map((priority, index) => [priority, index]);
    let order = 0;

    while (queue.length) {
        let [priority, idx] = queue.shift();
        if (queue.some(([p]) => p > priority)) {
            queue.push([priority, idx]);
        } else {
            order++;
            if (idx === location) {
                return order;
            }
        }
    }
}

• 배열을 큐처럼 사용합니다. (shift(), push())
• some() 메서드로 뒤에 더 높은 우선순위 있는지 검사합니다.

 

---

3.  마무리

• 큐는 선입선출(FIFO) 구조를 가지며, 데이터를 순서대로 처리할 때 필수적인 자료구조입니다.
• 프린터 큐 문제처럼 우선순위와 순서를 동시에 관리하는 문제에서 큐가 자연스럽게 적용됩니다.
• Python, C++, Java, JavaScript 모두 큐를 다루는 기본 지원을 제공하지만, 사용 방법은 언어마다 조금씩 다릅니다.

함께 하면 좋은 자료

블로그 글 :

[Stack] 쌓고 꺼내는 후입선출(LIFO) 자료구조

 

---