큐 자료구조 개념 및 예제

 

https://www.programiz.com/dsa/queue

Queue Data Structure and Implementation in Java, Python and C/C++

 

 

큐

• 큐는 FIFO(First In Frist Out) 선입선출 규칙을 따른다.
• enqueue: 큐에 항목을 넣는 것
• dequeue: 큐에 항목을 제거하는 것
• 큐의 한쪽에는 삭제 연산을 수행하는 front, 다른 한쪽에는 삽입 연산만 하는 rear

 

 

큐의 기본 동작

• Enqueue : 큐의 끝에 요소를 추가한다.
• Dequeue : 큐의 앞쪽에서 요소를 제거한다.
• IsEmpty : 큐가 비어있는지 확인한다.
• IsFull : 큐가 가득 찼는지 확인한다.
• Peek : 큐를 제거하지 않고 큐 앞부분의 값을 가져온다.

 

 

큐 사용 예제

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

Queue<Integer> q = new LinkedList<>(); // int형 queue 선언

q.offer(3);
q.offer(5);
q.offer(1);
q.offer(4);

System.out.println(q.peek()); // 3 출력

q.poll();
System.out.println(q); // [5, 1, 4]

q.clear();
System.out.println(q); // []

 

자바에서는 큐를 선언할 때 LinkedList를 사용해야 한다.

 

 

LinkedList를 사용해야 하는 이유

• 링크드리스트는 요소의 개수가 동적으로 변화할 수 있어 큐의 크기를 가변적으로 사용할 수 있다.
• (배열 기반 큐는 크기를 미리 정해야 하고 크기를 초과하면 새로운 배열을 생성해야 하는 단점이 있다.)
• 또한 링크드리스트는 메모리를 동적으로 할당하기 때문에 메모리 사용이 유연하다.
• 배열 기반 큐는 값 삽입, 삭제 시 요소를 이동시키거나 배열의 크기를 조절해야 하지만 링크드리스트는 삽입, 삭제 연산의 시간 복잡도가 O(1)로 매우 빠르다.

 

큐에 요소 추가는 offer(), 삭제는 poll() 메서드로 한다.

peek() 메서드를 사용하면 가장 먼저 추가된 값이 출력된다.