자료구조와 알고리즘/자료구조

[자료구조] 큐(Queue)

프린이8549 2024. 10. 4. 22:59

1. Queue의 정의

1.1. 큐의 정의

큐는 자료구조에 삽입(enqueue)된 데이터가 제일 먼저 삭제(dequeue)되는 선입선출(First In First Out; FIFO) 방식의 자료구조이다.

 

영단어 queue는 본디 표 같은 것을 구매하기 위한 대기열을 의미하는데, 표를 사기 위해 줄을 서는 사람들을 연상하면서 하단의 내용과 그림을 보면 어떤 형태의 자료구조인지 파악하기 쉬울 것이다.

 

앞서 살펴본 스택과는 달리 먼저 들어온 데이터가 먼저 나가기 때문에 삽입과 삭제가 양방향에서 이루어지는 특성이 있다.

Do it! 알고리즘 코딩 테스트 자바 편

1.2. 관련 용어

위치

  • rear : 값이 삽입되는 위치(큐의 가장 뒤쪽)
  • front : 값이 제거되는 위치(큐의 가장 앞쪽)

주요 연산

  • add : rear 부분에 새로운 데이터를 삽입하는 연산
  • poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • peek : front에 있는 데이터를 확인할 때 사용하는 연산

 

2. 구현

큐는 배열과 연결 리스트를 이용하여 구현할 수 있으며 그 형태는 크게 선형 큐와 원형 큐로 분류할 수 있다.

2.1. 선형 큐

선형 큐는 배열을 사용하여 구현하는 막대 모양의 큐이다.

 

https://yjg-lab.tistory.com/115

 

단점

  • 스택처럼 중간 자료에 임의 접근할 수 없기 때문에 삭제(dequeue) 연산 시 모든 요소를 꺼내 한 칸씩 옮겨야하므로[O(N)] 매우 비효율적
  • 인덱스를 감소시키지 않고 증가하면서 사용하는 방식이기에 삭제와 생성이 계속 일어났을때, 마지막 배열에 도달 후 실제로는 데이터 공간이 남아있지만 오버플로우 발생

 

2.2. 원형 큐(환형 큐)

앞선 선형 큐의 단점을 해결하기 위해 원형 버퍼(ring buffer) 개념을 이용하여 구현한 큐이다.

 

나머지 연산자를 통해 배열의 시작과 끝이 연결된 것처럼 동작한다. 즉, 배열의 끝에 도달하면 다시 배열의 처음으로 돌아와서 데이터를 삽입하거나 삭제할 수 있다.

 

https://yjg-lab.tistory.com/115

 

원형 큐를 배열을 사용하여 구현한다면, 

 

  • 큐를 위한 배열 생성(N + 1) 
    • 하나의 인덱스를 비워두기 때문(포화상태와 공백상태 구분하기 위함; 후술)
  • front, rear 변수 생성
  • 삽입 연산 : rear 위치에 데이터 삽입 후 나머지 연산을 통해 rear를 다음 위치로 이동
    • 만약  rear 가 배열의 마지막 인덱스에 위치하면, rear를 다시 배열에 첫 번째 인덱스로 이동시켜 삽입
    • rear = (rear + 1) % 배열의 크기
      • rear의 다음 위치로 이동시켜야하기 때문에 (rear + 1) 한 뒤 나머지 연산 실시
    • ==> 이 방식을 통해 큐가 원형으로 순환 가능
  • 삭제 연산 : front 위치에서 데이터 삭제 후 나머지 연산을 통해 front를 다음 위치로 이동
    • front가 배열의 마지막 인덱스에 도달 시, 배열의 첫번째 인덱스로 이동
    • front = (front + 1) % 배열의 크기

원형 큐의 공백 상태와 포화 상태는 아래와 같이 확인할 수 있다.

 

공백 상태( 큐가 비었는지 )

  • rear == front

포화 상태( 큐가 가득 찼는지 )

  • rear + 1 == front

상식적으로 생각하면 포화 상태도 rear == front 일 것이다.

그러나 이렇게 되면 공백 / 포화 상태를 명확히 구분할 수 없기 때문에 의도적으로 rear + 1 == front(rear가 front의 바로 앞에 있음) 를 포화 상태로 결정함으로써 두 상태를 구분하고 있다.

 

구현(백준 2164번 문항)

package BOJ;

import java.io.*;
import java.util.NoSuchElementException;

public class Main {
	/*
    BOJ NO.2164 : 카드 2
    	큐를 사용하여 동작 구현하기
    */
	
    static int[] queue;
    static int front; // 삭제 위치
    static int rear;  // 삽입 위치

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 카드 갯수 입력
        int N = Integer.parseInt(br.readLine());

        // 원형 큐는 하나의 인덱스를 비워두기 때문에 크기를 N + 1로 설정
        queue = new int[N + 1];

        // 초기 상태
        front = 0;
        rear = 0;

        // 큐에 카드 넣기
        for (int i = 1; i <= N; i++) {
            add(i);
        }

        // 카드가 1장 남을 때까지 지속
        while (size() > 1) {
            // 1. 최상단 카드 버리기
            poll();

            if (size() == 1) break;

            // 2. 최상단 카드를 최하단으로 옮기기
            int num = poll();
            add(num);
        }

        // 마지막 남은 카드 출력
        bw.write(String.valueOf(poll()));
        bw.flush();
        bw.close();
        br.close();
    }

    // 삽입 연산
    public static void add(int num) {
        if (isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        queue[rear] = num;
        rear = (rear + 1) % queue.length; // 원형 큐 동작
    }

    // 삭제 연산
    public static int poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        int num = queue[front];
        front = (front + 1) % queue.length;
        return num;
    }

    // 큐의 크기 반환
    public static int size() {
        return (rear - front + queue.length) % queue.length;
    }

    public static boolean isEmpty() {
        return rear == front;
    }

    public static boolean isFull() {
        return (rear + 1) % queue.length == front;
    }
}

 

장점

  • 메모리 재사용
    • 배열의 끝과 시작이 연결됨에 따라 빈 공간을 효율적으로 사용 가능
  • 삽입 / 삭제 연산의 효율성
    • 삽입과 삭제 연산의 시간 복잡도가 O(1) 정도로 매우 효율적

 

2.3. 링크드 큐

연결 리스트로 구현한 큐이다. 큐의 길이를 쉽게 늘릴 수 있어 오버플로우가 발생하지 않는 장점이 있다.

 

필요에 따라 원형으로 만들 수 있으며 원형이 아니더라도 삽입과 삭제가 제한되지 않아 편리하다.

 

 

3. 활용

큐는 선입선출 특성 때문에 데이터의 처리 순서가 중요한 여러 상황에서 사용된다.

3.1. 프린터 작업 대기열

 프린터는 작업 요청이 들어온 순서대로 출력 작업을 진행한다. 각 요청은 큐에 저장되고, 요청된 순서대로 출력되기 때문에 선입선출 구조가 유용하다.

 

 추가적으로 콜센터 상담 대기, 게임 대기열, 수강신청 대기열 등도 큐를 통해 이루어진다.

 

3.2. 프로세스 스케줄링

 프로세스 스케줄링 기법 중 FIFO, 라운드 로빈, 다단계 큐 스케줄링(MultiLevel Queue Scheduling; MLQ) 등에서 프로세스 대기열을 관리하기 위해 사용된다.

 

3.3. 네트워크 패킷 처리

네트워크에서는 데이터 패킷이 도착한 순서대로 처리된다. 큐에 패킷을 저장 후 패킷을 하나씩 꺼내 처리하는 방식으로 진행되기 때문에 선입선출 구조가 매우 적합하다.

 

3.4. 너비 우선 탐색(BFS)

그래프 탐색 알고리즘인 BFS는 큐를 사용하여 가까운 노드부터 탐색하는 방식으로 동작한다. 노드들은 탐색 순서대로 큐에 저장되며, 순차적으로 꺼내 탐색을 진행한다.

 

3.5. 코딩 테스트에서 큐의 활용 사례

프로세스 관리, 작업 스케줄링, BFS 문제에서 자주 큐가 활용되며

 

순서와 처리 우선순위가 중요한 상황에서 유용하게 사용된다.

 

 

4. 참고자료

 

1. < Do it! 알고리즘 코딩 테스트 자바 편>

2. https://namu.wiki/w/%ED%81%90(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

3. https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)