주니어 백엔드 개발자 인터뷰

# 큐 (Queue)

정의

큐는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료구조입니다.

image

  • 먼저 집어넣은 데이터가 먼저 나오는 스택과는 반대의 개념입니다.
  • 한쪽 끝, 프런트(front)에서는 삽입만 이루어지며, 다른 한쪽 끝끝은 리어(rear)에서는 삭제만 이루어집니다.
  • CPU 작업을 기다리는 프로세스, 스레드 또는 네트워크 접속을 기다리는 행렬, 너비우선 탬색(BFS), 캐시 등에 사용됩니다.

# 큐의 종류

자바에서 제공하는 큐는 인터페이스이고, 큐를 구현하는 클래스는 크게 3가지가 있습니다.

  • PriorityQueue(우선순위 큐)
    • 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조입니다.
    • 내부구조가 힙으로 구성되어 있습니다.
  • ArrayDeque(배열 양방향 큐)
    • 큐의 양쪽에서 데이터의 삽입과 삭제가 모두 가능한 구조입니다.
    • Queue를 상속받은 Dequeue 인터페이스를 사용해야 합니다.
    • Stack이나 Queue보다 빠르지만, Thread-Safe하지 않다는 단점이 있습니다.
  • LinkedList(연결리스트)
    • 대중적이고 쉬운 큐의 사용방식입니다.
    • 배열로 큐를 만든다면, 요소의 양에 따라 배열의 크기를 조절하거나, 원형 큐(Circular Queue)의 형태로 만들어야 하는데, linkedlist를 사용한다면 그러한 단점들이 사라집니다.

큐의 발전

일반 큐의 단점 : 큐에 빈 메모리가 남아 있어도, 꽉 차있는것으로 판단할 수도 있습니다. (rear가 끝에 도달했을 때)
원형 큐 : 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주합니다.
원형 큐의 단점 : 메모리 공간은 잘 활용하지만, 배열로 구현되어 있기 때문에 큐의 크기가 제한됩니다.
연결리스트 큐 : 크기 제한이 없고 삽입, 삭제가 편리합니다.

# 데이터 삽입&삭제 속도

  • O(1)
  • 입구 데이터를 바로 삽입하고, 출구에서 바로 삭제(꺼내기)하면 됩니다.

# 데이터 탐색 속도

  • O(n)
  • 찾는 데이터가 존재하는지 투입된 순서대로 순차 검색이 필요합니다.
  • 따라서 운이 안 좋으면 저장된 모든 값을 확인해야 할 수 도 있습니다.

# 자바에서의 큐

image

  • Collection 인터페이스를 상속 받는 인터페이스 입니다.
import java.util.Queue;
import java.util.LinkedList;

public class Sample() {
    public static void main(String[] args) {
        // 큐 만들기
        Queue<Integer> queue = new LinkedList<>(); // linkedlist 이용
        
        // 큐의 마지막에 요소를 추가
        queue.offer(10);
        queue.add(20);

        // 큐의 첫번째 요소를 제거하지 않고 반환
        Integer a = queue.peek();
        Integer b = queue.element();
        System.out.println(a); //10
        System.out.println(b); //20

        // 큐의 첫번째 요소를 제거하고 제거된 요소를 반환
        Integer c = q.poll();
        Integer d = q.remove();
        System.out.println(c); //10
        System.out.println(d); //20
    }
}
  • 위의 항목은 오로지 Queue 인터페이스에서만 추가된 메소드입니다.
  • offer()와 add()는 동일한 역할을 수행하는 것처럼 보이지만, 차이점은 add()는 공간이 부족해서 삽입이 불가할 때 IllegalStateException이 발생합니다.
  • peek()와 element()는 동일한 역할을 수행하는 것처럼 보이지만, 차이점은 element()는 비어있는 상태 일 때 NoSuchElementException이 발생합니다.
  • poll()와 remove()는 동일한 역할을 수행하는 것처럼 보이지만, 차이점은 remove()는 비어있는 상태 일 때 NoSuchElementException이 발생합니다.
  • offer(), peek(), poll()은 예외를 던지는 것이 아니라, 특별한 값 (null또는 false)를 던진다는 것입니다.

queue_methods

예를 들어, 큐가 비어있는데 remove()를 하면 NoSuchElementException 예외가 발생하지만, poll()을 하면 null값이 반환됩니다.

image

  • 다른 메소드는 Collections 인터페이스 의 메소드를 이용합니다.
  • 결국 둘다 인터페이스이기에 구현체인 LinkedList에서 호출되는 것이지만....

# 2개의 스택으로 큐를 구현하기

image

  1. inbox에 데이터를 삽입한다(push) -> A,B
  2. inbox에 있는 데이터를 추출(pop)하여 outbox에 삽입(push) 한다. -> B,A
  3. outbox에 있는 데이터를 추출(pop)한다. -> A,B 순으로 출력된다.
import java.util.Stack;

public class Queue {
	private Stack inBox = new Stack();
	private Stack outBox = new Stack();
	
	public void enQueue(Object item) {
		inBox.add(item);
	}
	
	public Object deQueue() {
		if (outBox.isEmpty()) {
			while(!inBox.isEmpty()) {
				outBox.push(inBox.pop());
			}
		}
		return outBox.pop();
	}
	
	public static void main(String[] args) {
		Queue queue = new Queue();
		queue.enQueue("A");
		queue.enQueue("B");
		queue.enQueue("C");
		
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
		System.out.println(queue.deQueue());
	}
}

# 참고자료

← 덱 (Deque) →