[자료구조] 큐(Queue)

 

 

 

 

 

 

 

 

 

 

 

자료구조, 큐(Queue)에 대해 알아보기

---

 

 

 

 

 

 

Queue의 구조와 특징 

큐는 추상자료형 중 하나입니다. 큐의 주요 작업은 큐의 뒤쪽에 요소를 추가하는 Enqueue와 큐의 앞쪽에 요소를 제거하는 Dequeue로 나뉩니다. 

• 선입선출(First In First Out) 구조를 가짐 
• 가장 먼저 들어온요소가 가장 먼저 제거됨

 

 

 

 

Queue 의 종류

 

큐에는 2가지 종류가 있습니다. 바로 선형큐와 환형큐입니다. 

 

1.선형큐(Linear Queue)

선형큐는 큐의 가장 기본 형태입니다. 

• 요소들은 선형적으로 정렬돼있음
• 고정된 크기를 갖고 있음
• 요소를 제거한 후 재사용 하지 못하는 underflow 문제가 발생할 수 있음 

 

2.환형(Circular Queue)

 

환형큐는 선형 큐의 한계를 극복하기 위해 설계된 형태입니다. 

• 큐의 끝과 시작이 연결됨
• 공간낭비를 최소화함
• 큐의 공간을 재사용할 수 있음 

 

 

 

 

연결리스트로 구현한 큐 

 

연결리스트를 사용하여 큐를 구현하면, 요소들이 메모리 상에서 연속적으로 위치할 필요가 없으므로 큐의 크기를 동적으로 조절할 수 있습니다. 각 요소는 데이터와 다음 요소를 가리키는 포인터로 구성됩니다. 이 방식은 메모리 할당이 분산되어 있어 큐의 크기 조정이 유연하며, 선형 큐의 고정 크기 한계를 극복할 수 있습니다.

 

 

 

 

Queue 의 연산 

 

1. Enqueue()

 

큐의 뒷쪽에 요소를 추가

 

2. Dequeue()

 

큐의 앞쪽 요소를 제거하고 반환

 

3. Peek or Front()

 

큐의 맨 앞에 있는 요소 조회

 

4. isEmpty()

 

큐가 비었는지 확인

 

5. isFull()

 

큐가 가득 찼는지 확인 

 

 

 

 

Queue 의 시간복잡도 

 

큐의 기본 연산은 대부분 O(1)의 시간 복잡도를 가집니다. 큐의 시작과 끝에만 접근하기 때문에 요소를 추가하거나 제거하는 데 일정한 시간이 소요됩니다.

 

연결리스트로 구현된 큐 역시 O(1)로 수행됩니다.

 

 

 

 

JAVA로 Queue 구현 

 

LinkedLisk 클래스를 통한 큐 구현입니다. 

 

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

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

        // 요소 추가
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 요소 제거 및 출력
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}