[DataStructure & Algorithm] Queue

자료구조 및 알고리즘

---

개요 - Queue란?

Queue의 사전적 의미는 어떤 것을 기다리는 사람, 차 등의 줄 또는 줄을 서서 기다리는 것을 의미한다.

이처럼 줄을 지어서 순서대로 처리되는 자료구조가 Queue라고 한다. 큐는 LIFO 구조를 사용하는 Stack과는 다르게 FIFO(First In First Out)의 구조를 가지는 자료구조이다.

 

FIFO는 가장 먼저 들어오는 데이터가 가장 먼저 나가는 구조를 의미한다. 

 

자료구조의 맨 뒤에 데이터가 들어오는 것을 Enqueue, 맨 앞에서 데이터가 나가는 것을 Dequeue라고 한다.

Queue

---

특징

• FIFO 구조를 갖는다 : 가장 먼저 들어온 데이터가 가장 먼저 밖으로 나가게된다.
• 큐의 앞쪽을 front, 큐의 뒤쪽을 rear로 정한다.
  • Front에서는 Dequeue의 기능을, Rear에서는 Enqueue 기능을 수행한다.
• 그래프의 BFS(너비 우선 탐색)에서 사용된다
• 컴퓨터의 버퍼에서 사용된다. 키보드입력을 큐를 사용해서 처리한다.

enqueue

 

dequeue

---

구현

Integer 부분만 바꾸면 해당 Type의 Queue를 선언하게 된다.

Queue는 LinkedList나 ArrayDeque를 통해서 구현하게 된다.

 

Q. 왜 Stack이랑은 다르게 new Queue<>();는 안되나요?

 

A. Queue는 자바에서는 Interface로 선언되어 있어서, new Queue<>()를 사용하려면, 해당 인터페이스 내부에 선언된 모든 메서드들을 오버라이딩해야할 필요가 있습니다.

하지만 LinkedList와 ArrayDeque에는 해당 내용들이 모두 오버라이딩 되어 있어, 아래와 같은 방식으로 코드를 작성하면 됩니다.

 

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

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

        integerQueue.add(1);
        integerQueue.add(2);
        integerQueue.add(3);

        integerQueue2.add(1);
        integerQueue2.add(2);
        integerQueue2.add(3);

        System.out.println("integerQueue = " + integerQueue);
        System.out.println("integerQueue2 = " + integerQueue2);

    }
}
// integerQueue = [1, 2, 3]
// integerQueue2 = [1, 2, 3]

---

메서드

• 데이터 삽입
  • offer(value), add(value) 메서드 안에 큐의 원소 타입에 맞게 원소를 넣으면 삽입됩니다.
    • offer(value)는 성공하면 true, 실패하면 false
    • add(value)는 성공하면 true, 실패하면 IllegalStateException를 던집니다.
• 데이터 제거
  • poll(),remove() 메서드을 통해 Queue의 front 부분의 데이터를 추출하고 해당 데이터를 리턴합니다.
    • poll()은 데이터를 반환하지만, remove()는 그냥 삭제만 합니다.
• 데이터 조회
  • peek(), element()를 사용해서 front 부분에 존재하는 데이터를 반환합니다.
    • peek은 큐가 비어있을 경우, null을 반환합니다.
    • element는 큐가 비어있을 경우, NoSuchElementException를 던집니다.
• 큐 상태 조회
  • isEmpty()는 큐가 비어있는 경우, true. 아닌경우, false를 반환합니다.
  • contain(value)는 value가 있는 경우 true, 아닌경우 false를 반환합니다.

---

응용

• BFS : 그래프나 트리 구조에서 너비 우선 탐색(BFS)을 수행할 때 큐를 사용하여 각 노드를 순서대로 탐색합니다.
• 작업 스케줄링 큐 :여러 작업이 동시에 실행되어야 할 때, 큐를 사용하여 작업을 순서대로 처리하도록 스케줄을 관리할 수 있습니다.
  • 추후에 따로 다룰 메세지 큐도 여기에 해당됩니다.
• 웹 서버의 요청 처리 :웹 서버가 도착하는 HTTP 요청을 처리할 때 큐를 사용하여 요청을 순차적으로 처리합니다. 이는 서버가 한 번에 하나의 요청을 처리하고 다음 요청으로 넘어가는 순서를 유지하는 데 도움이 됩니다.