큐(Queue) 구조의 이해

 

 

Queue의 개념

 

 

큐(Queue)는 데이터를 일렬로 저장하고, 반대편에서 순서대로 처리되는 선형 자료구조이다. 큐에 삽입된 데이터는 일종의 대기열로 생각할 수 있으며, 먼저 도착한 데이터가 먼저 처리되는 선입선출법(FIFO, First In - First Out)의 구조를 가진다. Stack과 반대되는 구조라고 할 수 있다.

 

 

Stack의 데이터 삽입(Enqueue)과 삭제(Dequeue) 형태

 

 

Queue 구조에서의 명칭

 

 

한쪽에서 데이터를 삽입하는 것을 Enqueue, 반대편에서 삭제하는 것을 Dequeue라고 한다. 각각 Enqueue는 offer와 add 메소드, Dequeue는 poll과 remove 메소드를 이용한다. 추가로 front 메소드는 첫 번째 요소를 삭제하지 않고 반환한다.

 

 

Queue의 응용

 

 

• Java에서의 활용 예시

Queue<Integer> queue = new LinkedList<>();

queue.add(5);
queue.add(4);
queue.offer(3);

System.out.println(queue.poll()); // 5
System.out.println(queue); // [4, 3]
System.out.println(queue.peek()); // 4
System.out.println(queue.contains(4)); // true
System.out.println(queue.size()); // 2
System.out.println(queue.isEmpty()); // false
queue.clear();
System.out.println(queue.isEmpty()); // true

 

Queue는 이벤트 또는 네트워크의 패킷을 처리하거나 프로세스를 스케줄링하는 데 응용되며, BFS 알고리즘의 자료구조를 구현하기 위한 기반으로도 사용된다. 또한 Stack과 마찬가지로 회계학에서 재고자산 계산법의 일종이기도 하다(훨씬 많이 쓰인다).

 

배열과 연결 리스트로 구현될 수 있는데, 배열은 한 번 생성되면 길이가 변경되지 않는 특성상 큐의 크기를 제한해야 할 때 주로 사용되며, 연결 리스트는 가변적인 크기가 필요할 때 주로 사용된다.