큐 (Queue)

선형 자료 구조 큐(Queue)는 스택과 정 반대되는 개념으로, 가장 먼저 삽입된 것이 가장 먼저 삭제되는 선입선출 (FIFO, First-In, First-Out) 구조를 가지고 있다. 뭔가를 기다리며 서 있는 줄이나, 컴퓨터 키보드 명령이 한 줄을 다 칠 때까지 키보드 버퍼 메모리에 큐를 형성한 채 기다리는 것이 그 예이다. 스택에서 삽입, 삭제 모두가 맨 뒤에서 일어나는 데 비해 큐에서 삽입은 맨 뒤에서, 삭제는 맨 앞에서 이루어진다. 즉 큐는 양쪽 끝이 모두 사용된다.

 

• 큐 프런트(front) : 큐의 맨 앞
• 큐 리어(rear) : 큐의 맨 뒤
• add / enqueue: 큐 리어에 데이터 삽입
• remove / dequeue : 큐 프런트의 데이터 삭제
• peek : 큐 프런트의 값 반환

https://www.geeksforgeeks.org/queue-data-structure/

 

 

시간 복잡도

• 검색 : O(n), 데이터 개수만큼 이동하며 찾아야 함.
• 삽입 : O(1), 데이터의 개수와 상관없이 삽입 가능.
• 삭제 : O(1), 데이터의 개수와 상관없이 삭제 가능.

 

스택과 마찬가지로 배열과 연결 리스트로 구현 가능하며 둘의 장단점 또한 같다.

 

 

구현

연결 리스트로 스택을 구현할 때에는 리스트의 첫 데이터인 스택 탑을 가리키는 포인터 하나로 충분했다. 그러나 큐는 프런트와 리어라는 양 끝을 접근해야 하므로 기본적으로 포인터 두 개를 예상할 수 있다. 이렇게 되면 삽입, 삭제에 대해 각각 별도의 포인터가 사용된다. 삽입 명령에 대해서는 현재의 리어 포인터가 가리키는 노드 바로 다음에 이어 붙이면 되고, 반대로 삭제 명령에 대해서는 프런트 포인터가 현재 가리키고 있는 노드 바로 다음 노드를 가리키게 하면 된다. 물론 리어 포인터 없이 프런트 포인터 하나만 가지고 큐를 유지할 수도 있지만, 이 경우 삽입 명령이 들어오면 프런트 포인트부터 시작해서 연결 리스트의 끝까지 순회해야 하므로 이동에 대한 시간적 부담을 안게 된다.

 

원형 연결 리스트(Circular Linked List)로 구현해 리어 포인터 하나만으로 큐를 구현하는 것도 가능하다. 마지막 데이터가 다시 처음 데이터를 가리키게 해, 큐의 마지막 데이터는 Rear 포인터로, 첫 데이터는 Rear의 Next 포인터로 단번에 접근이 가능하게 되므로 리스트 전체를 순회하는 데 따른 시간적 부담이 전혀 없이 삽입, 삭제가 가능해진다. 

 

아래는 선형 큐(Linear Queue)를 연결 리스트로 구현한 코드이다.

public class Queue {
    private static class Node {
        private int data;
        private Node next;
        private Node(int data) {
            this.data = data;
        }
    }
    private Node head;      // front queue, 이곳에서 제거
    private Node tail;      // rear queue, 이곳에 추가

    public boolean isEmpty() {  // 큐가 비어있는지 확인
        return head == null;
    }

    public int peek() {     // 큐의 맨 앞(front)에 있는 항목 반환
        if(isEmpty()) return -1;    // 빈 큐 반환 시 underflow
        return head.data;
    }

    public void add(int data) {     // 데이터 추가
        Node node = new Node(data);     // 새로운 노드 생성
        if(isEmpty()) {     // 빈 큐일시 현재 노드를 head 노드로 지정
            head = node;
        } else {
            tail.next = node;   // 큐의 맨 끝 다음에 현재 노드 추가
        }
        tail = node;
    }

    public int remove() {       // 데이터 삭제
        if(isEmpty()) return -1;    // 빈 큐 반환 시 underflow
        int data = head.data;
        head = head.next;       // head 큐 그 다음으로 옮겨짐
        if(head == null) tail = null;   // head와 tail이 같았을 때, 즉 데이터가 한 개밖에 없었을 때 tail도 null로 초기화 시켜줌
        // 참조형은 항상 null로 초기화 되므로 head.next에는 null이 담겨있었음.
        return data;
    }
}

 

 

배열로 큐를 구현하기 위해서는 front, rear라는 변수 두 개를 두어 앞에서 일어나는 큐의 삭제와 뒤에서 일어나는 큐의 삽입을 첫 데이터와 마지막 데이터의 인덱스로 추적해야 한다. 큐의 front 인덱스는 0으로, rear 인덱스는 -1로 초기화하여 삽입시 rear++ 한 후 추가, 삭제 시 front++를 해버리면 되는 것이다. 그러면 원래 가장 왼쪽에 있던 프런트 데이터를 지울 필요 없이 그냥 무시해 버릴 수 있다.

 

그러나 배열로 구현한 큐는 기본적으로 메모리 공간 낭비라는 문제점을 안고 있다. 삽입에 의해 rear 인덱스가 증가하여 큐가 오른쪽으로 계속 자라는 반면 삭제에 의해 front 인덱스가 증가하여 점차 왼쪽에 버려진 공간이 늘어나게 되는 것이다. 이를 표류 현상이라 한다.

 

https://buildgoodhabit.tistory.com/142

 

 

이를 해결하기 위해 고안된 것이 원형 배열(Circular Array)이다. 리어 인덱스를 증가시킬 공간이 없을 경우 다시 처음 인덱스인 0으로 되돌려 거기에 삽입하는 것이다. 모듈로(modulo, %) 연산자를 사용하면 리어 인덱스를 다시 배열의 처음으로 돌릴 수 있다. 원형 배열에서 삽입을 위한 인덱스를 구하는 함수는 (Rear + 1) % MAX로 표시할 수 있다.

 

https://www.geeksforgeeks.org/introduction-to-circular-queue/

 

원형 배열을 사용할 경우 isFull과 isEmpty 상황을 인덱스만으로 판단하는 데에 어려움이 있을 수 있기에 별도의 count 변수를 유지하여 현재 큐에 데이터 몇 개가 있는지 추적하는 것도 방법이다. 이렇게 한다면 인덱스 대신 count 변수 만으로 현재 큐의 상황을 체크할 수 있다. 다음은 원형 큐(Circular Queue)를 코드로 구현한 모습이다. 환형 큐라고도 한다.

 

public class Queue {
    private int head = 0;	// queue front
    private int tail = -1;	// queue rear
    private int count = 0;	// 데이터 총 개수
    private int[] queue;

    private final int MAX;
    public Queue(int MAX) {
        this.MAX = MAX;
        queue = new int[MAX];
    }

    public boolean isEmpty() {  // 빈 큐인지 확인
        return count == 0;
    }

    public boolean isFull() {   // 큐가 꽉 찼는지 확인
        return count >= MAX;
    }

    public void add(int data) {
        if(!isFull()) {     // 큐가 차지 않았을 경우에만 추가
            tail = (tail + 1) % MAX;
            queue[tail] = data;
            count++;    // 데이터 총 개수 한 개 증가
        }
    }

    public int peek() {
        if(isEmpty()) return -1;    // 빈 큐 underflow
        return queue[head];
    }

    public void remove() {
        if(!isEmpty()) {    // 빈 큐가 아닐 시 제거
            head = (head + 1) % MAX;
            count--;        // 데이터 총 개수 한 개 감소
        }
    }
}

 

 

 

사용 사례

• CPU/디스크 스케줄링 (작업을 순서대로 실행하기 위해 대기시킬 때)
• IO 버퍼, 파이프, 파일 IO
• 프로세스 관리
• 너비 우선 탐색
• 캐시(Cache) 구현

 

다음에는 큐를 활용한 데크(Deque)와 우선순위 큐(Priority Queue)에 대해 알아보겠다.

 

 

 

[참고자료]

C/C++로 배우는 자료구조론