[Data Structures] 큐(Queue) (with. a little deep dive and Java)

안녕하세요. 성조입니다.

 

이번 포스팅은 자료구조와 정보처리기사에서 흔히 접할 수 있는 알고리즘인 큐(Queue)에 대해서 정리하는 시간을 가져보려 합니다.

 

혹시나 오타 또는 부족한 지식 전달, 잘못된 지식 전달이라고 판단되시면 언제든지 댓글로 얘기 주시면 감사드리겠습니다!

---

본인이 캔바 pro 구독으로 가져온 이미지입니다

서론

큐에 대해서 본격적으로 시작하기 전에 큐(Queue)를 처음 공부하는 사람이라면 위 이미지를 보면 어떤 느낌이 드는지 묻고 싶다.

한 줄로 무엇을 대기하여 기다리고 있는 것 같아 보인다면 좋을 것 같다.

맨 처음 있는 사람이 방향에 맞게 시간이 지나면서 다음 사람이 그 자리를 채우는 형식을 띠고 있는 것 아닌가?

이것이 포스팅의 목표인 큐(Queue)를 가볍게 작성한 것이라 생각하면 좋을 것 같다.

 

 

큐(Queue)란?

큐(Queue)는 컴퓨터 과학에서 자주 사용되는 기본적인 자료구조이다. 큐는 항목들이 "들어온 순서대로 나간다."(First-In-Frist-Out, FIFO) 구조를 가지고 있다.


즉, 큐에 먼저 들어온 데이터가 먼저 나가게 되는 것이다. 우리는 실생활에서 음식 식당을 대기할 때. 대기 번호를 받고 한 줄 서기하여 먼저 온 손님이 먼저 입장하는 것을 봤을 것이다. 그런 건 구조가 큐 구조로 이뤄졌다고 보면 된다.

 

큐를 구현하는 것은 가장 일반적인 방법으로 배열 또는 연결 리스트를 활용해서 만드는 것인데 어떤 방법을 활용해서 만들더라도 큐의 핵심인 FIFO 원칙을 따르는 것이 중요하다.

 

 

큐의 사용 사례

1. 대기열 관리

여러 개의 인쇄 작업이 요청되면, 프린터는 이를 큐에 저장하고 순차적으로 처리한다. 우리가 현실에서 프린트기를 활용할 때 먼저 신청한 것들이 먼저 출력되는 것을 볼 수 있다. 또한 예약 시스템, 콜 센터 등의 케이스가 추가적으로 존재하는 것을 알 수 있다.

 

2. 네트워크

데이터 패킷을 전송할 때, 네트워크 장비는 패킷들을 큐에 저장하고 순차적으로 전송하게 되는데 그 때 큐(Queue) 구조가 사용된다.

 

3. 운영체제

운영체제에서 프로세스 관리, 디스크 스케줄링, 메모리 관리, 캐시 등의 다양한 프로세스들이 큐(Queue) 구조를 활용한다.

 

4. 이벤트 드리븐 프로그래밍

프로그래밍 과정에서 이벤트가 나오는 경우. 먼저 발생한 이벤트를 큐에 저장하고 순차적으로 처리하게 된다.

 

 

큐의 핵심 연산

1. Enqueue

큐의 뒤쪽(rear)에 데이터를 삽입하는 연산이다.

- 배열 기반으로 하는 큐에서는 rear 포인터를 이용해 새로운 요소가 삽입될 위치를 트래킹한다.

- 연결 리스트를 이용하는 경우에는 새 노드를 생성하여 리스트를 끝에 추가한다.

 

2. Dequeue

큐의 앞쪽에서 데이터를 제거하고 그 값을 반환하는 연산이다.

- 배열 기반으로 하는 큐에서는 front 포인터를 이용해 제거할 요소의 위치를 트래킹한다.

- 연결 리스트를 이용하는 경우에는 리스트의 첫 번째 노드를 제거한다.

 

3. Peek/Front

큐의 앞쪽에 있는 데이터를 조회하는 연산이다. 이 연산의 경우 데이터를 제거하지는 않는다. (GET 메서드 같은 것이다.)

 

4. IsEmpty

큐가 비어있는지 확인하는 연산이다.

front나 rear 포인터의 위치를 비교하거나, 큐에 저장되어 있는 요소의 수를 추적하는 정도로 변수를 사용하여 큐가 비어있는지를 확인하는 용도로 쓰인다.

 

5. IsFull

큐가 꽉 차있는지 확인하는 연산이다.

(IsFull의 경우 큐가 고정된 경우만 유효하며, 크기가 유동적인 경우에는 확인할 수 없다.)

 

 

다양한 형태의 큐

1. 선형 큐(Linear Queue)

가장 기본적인 형태의 큐로, 앞에서는 삭제. 뒤에서는 삽입 연산이 이뤄지는 큐(Queue)를 말한다.

쉽게 접할 수 있는 만큼 가장 오래된 큐 구조이다. 이 큐 구조는 메모리 영역에 있는 데이터를 제거한 후에 다시 재사용할 수 없다는 단점을 가지고 있다.

 

2. 원형 큐(Circular Queue)

선형 큐의 단점인 메모리 낭비를 보완한 형태의 큐이다. 마지막 요소 다음에 첫 번째 요소가 오는 방식으로 구현된다.

앞에 있는 값이 제거되면 뒤에 있는 값이 앞으로 이동하여 자리를 채우는 원형 구조의 큐로 바로 위의 선형 큐의 단점인 메모리 공간 낭비를 줄이기 위해 만들어진 형태이다.

 

3. 우선순위 큐(Priority Queue)

각 요소가 우선순위를 가지고 있고, 우선순위가 가장 높은 요소가 먼저 dequeue 되는 것을 말한다.

우선순위 큐의 경우. 우선순위를 가지는 값을 먼저 제거하기 때문에 일반적인 FIFO 원칙을 사용하지 않는다. 힙(heap)과 같은 자료 구주를 활용하는 것이 더 효율적으로 구현될 수 있다.

 

4. 덱(Deque, Double Ended Queue)

양쪽 끝에서 삽입과 삭제가 모두 가능한 큐(Queue)를 말한다.

하이브리드에 가깝다고 생각한다. 덱은 앞(front)으로 데이터를 추가 삭제할 수 있고, 뒤(rear)로도 데이터를 추가 삭제할 수 있기 때문이다. 그러나 이런 하이브리드의 문제는 1개의 일을 하는 것보다 2개의 일을 했을 때 조금 더 복잡해질 수 있다는 점이다. 즉, 유연하게 프로그래밍할 수 있는 장점이 있지만 구현하는 곳이나 사용하는 곳에서 복잡도가 올라갈 수 있는 단점이 존재한다.

 

5. 블로킹 큐(Blocking Queue)

큐가 가득 찬 상태에서 새로운 요소의 삽입, 또는 큐가 비어 있는 상태에서 요소의 제거를 시도하면, 해당 연산이 가능해질 때까지 대기한다.

Java의 경우 java.util.concurrent 패키지에서 BlockingQueue 인터페이스를 활용하여 만들어낼 수 있다.

 

 

큐(Queue)의 장점 및 단점

장점

1. FIFO 원칙

First-In-First-Out 순서로 처리하는 것이 장점이다. 하지만 단점이 될 수 있는 부분이기도 하다. 그래도 컴퓨터 공학에 많은 문제들을 해결하는데 중요한 역할을 해주는 것이므로 장점이 크다.

 

2. 처리 순서 보장 

선점형과 같이 추가된 순서대로 스케줄링을 처리되어야 하는 경우 매우 유용하게 사용된다.

 

3. 다양한 활용 사례

상단에 활용 사례를 정리했으니 참고하자.

 

4. 병렬 컴퓨팅

여러 작업을 동시에 수행하고 관리할 때 유용하게 활용된다.

 

5. 메모리 관리

여러 데이터를 순차적으로 저장하므로 큐 구조는 메모리 영역을 효율적으로 사용할 수 있다.

 

 

단점

1. 중간 데이터를 삽입/삭제하기 어려움

큐의 경우 시작과 끝에서만 데이터를 접근할 수 있기 때문에 중간에 끼어있는 데이터는 접근이 어려운 단점이 존재한다. 장점 1번에서 얘기했던 단점이 되는 부분이다.

 

2. 속도 제한

삽입, 삭제 연산의 경우 O(1)의 시간 복잡도를 가지지만(스택 구조도 다음 설명에서 다룰 예정이다.) 연결 리스트의 큐가 아닌 배열 큐에서는 데이터를 이동할 때 배열에 할당된 메모리 위치가 어긋나는 경우 O(n)의 시간이 걸릴 수 있다.

 

3. 배열 큐에 비해서 복잡한 연결 리스트를 통한 큐 구현

배열의 경우 비교적 구현하기 쉽지만 연결 리스트를 활용하여 구현하면 조금은 복잡한 것이다. 큐 자체의 문제이기보다는 상황에 맞는 구현 방법을 선택했을 때 리스크가 될 수 있는 점이다.

 

4. 오버플로우/언더플로우 위험 

가득 차있는 상태에서 추가 제거 연산할 때 문제가 발생할 수 있다.

배열 기반의 큐를 구현할 때는 메모리 크기를 미리 할당해야 하므로 모든 공간이 활용되지 않을 때 낭비될 수 있다. 범위를 작게 줬을 때 또는 크게 할당했을 때 오버플로우/언더플로우에 대하여 어떻게 대처할 것인지 중요하다.

 

 

코드 구현

 

라이브러리 없이 구현한 원형 큐 (Array Java Code)

public class Queue {

    private int[] elements;
    private int size;
    private int front;
    private int rear;

    public Queue(int capacity) {
        elements = new int[capacity];
        front = 0;
        rear = -1;
        size = 0;
    }

    public void enqueue(int data) {
        if (size == elements.length) {
            throw new IllegalStateException("큐가 가득 찼다.");
        }
        rear = (rear + 1) % elements.length; // 원형 큐 구현을 위해 모듈로 연산 사용
        elements[rear] = data;
        size++;
    }

    public int dequeue() {
        if (size == 0) {
            throw new IllegalStateException("큐가 비어있다.");
        }
        int data = elements[front];
        front = (front + 1) % elements.length; // 원형 큐 구현을 위해 모듈로 연산 사용
        size--;
        return data;
    }

    public int peek() {
        if (size == 0) {
            throw new IllegalStateException("큐가 비어있다.");
        }
        return elements[front];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == elements.length;
    }
    
    public static void main(String[] args) {
        Queue queue = new Queue(5);

        // 큐에 데이터 추가
        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);

        // 큐의 첫 번째 데이터 조회
        System.out.println("조회: " + queue.peek());

        // 큐에서 데이터 제거
        int removedItem = queue.dequeue();
        System.out.println("제거된 큐 데이터: " + removedItem);

        // 큐가 비어 있는지 확인
        System.out.println("비어 있는지? " + queue.isEmpty());

        // 큐가 가득 찼는지 확인
        System.out.println("가득 차있는지? " + queue.isFull());
	}
}

 

 

라이브러리 없이 구현한 원형 큐 (Linked List Java Code)

public class Queue<T>{
	
	public static void main(String[] args) {
		Queue<Integer> queue = new Queue<>();

	    // 큐에 데이터 추가
	    queue.enqueue(10);
	    queue.enqueue(20);
	    queue.enqueue(30);

	    // 큐의 첫 번째 데이터 조회
	    System.out.println("첫 번째 조회: " + queue.peek());

	    // 큐에서 데이터 제거
	    int removedItem = queue.dequeue();
	    System.out.println("데이터 제거: " + removedItem);

	    // 큐가 비어 있는지 확인
	    System.out.println("비어 있는지 조회. " + queue.isEmpty());
	}
	
	private Node<T> first;
    private Node<T> last;

    private static class Node<T> {
        private T data;
        private Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    public void enqueue(T item) {
        Node<T> t = new Node<T>(item);
        if (last != null) {
            last.next = t;
        }
        last = t;
        if (first == null) {
            first = last;
        }
    }

    public T dequeue() {
        if (first == null) {
            throw new IllegalStateException("큐가 비어있다");
        }
        T data = first.data;
        first = first.next;
        if (first == null) {
            last = null;
        }
        return data;
    }

    public T peek() {
        if (first == null) {
            throw new IllegalStateException("큐가 비어있다");
        }
        return first.data;
    }

    public boolean isEmpty() {
        return first == null;
    }
}

 

 

라이브러리를 활용한 원형 큐(Linked List Java Code)

import java.util.LinkedList;
import java.util.Queue;

public class Queue {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();

        // 요소가 추가된다.
        q.add(1);
        q.add(2);
        q.add(3);

        System.out.println("초기 큐: " + q);

        // 시작 부분의 요소가 제거된다.
        int removedElement = q.remove();
        System.out.println("제거된 요소: " + removedElement);
        System.out.println("제거된 후. 다음 값 요소: " + q);

        // 첫 번째 요소 확인.
        int head = q.peek();
        System.out.println("맨 처음 값은: " + head);
        System.out.println("마지막 큐 값은: " + q);
    }
}

 

데크(Deque) (Java Code)

import java.util.ArrayDeque;
import java.util.Queue;

public class Deque {
    public static void main(String[] args) {
        Queue<Integer> queue = new ArrayDeque<>();

        // offer 메서드를 사용하여 큐에 요소를 추가.
        for (int i = 0; i < 5; i++) {
            queue.offer(i);
        }

        // peek 메서드를 사용하여 큐의 첫 번째 요소를 확인.
        System.out.println("큐의 첫 번째 요소: " + queue.peek());

        // poll 메서드를 사용하여 큐에서 요소를 제거하고 그 값을 출력.
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

        // 큐가 비어 있는 상태에서 poll 메서드를 호출하면 null을 반환.
        System.out.println("큐가 비어 있는 상태에서 poll 호출: " + queue.poll());
    }
}

 

 

 

---

오타나 궁금한 점이 있다면 언제든지 댓글 부탁드리며, 잘 못 된 지식 전달이라 판단되는 경우에도 댓글 주시면 감사드립니다.

 

좋은(올바른 지식 전달) 포스팅이 될 수 있도록 노력하겠습니다.

다음 포스팅 때 뵙겠습니다!