queue
•
먼저 들어온 데이터가 먼저 나가는 형식의 자료구조
•
선입선출, FIFO, first in first out
•
입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화
◦
예) 은행대기줄
•
한 쪽 끝은 front로 정하여 삭제 연산만 수행한다. -> enqueue
•
다른 쪽 끝은 rear로 정하여 삽입 연산만 수행한다. -> dequeue
•
데이터 삽입 전에는 full 인지 확인, 삭제 전에는 empty 인지 확인해야한다.
•
장단점
◦
데이터의 접근, 삽입, 삭제가 빠르다.
◦
중간에 있는 데이터에 대한 접근이 불가하다.
•
예시
◦
그래프의 넓이 우선 탐색 (BFS) 에서 주로 사용된다.
◦
컴퓨터 버퍼에서 주로 사용된다. 마구 입력되었으나 처리를 못할 때, 일단 버퍼 큐에 일렬로 대기를 시켜놓는다.
◦
프린트의 대기열에도 사용된다.
◦
은행업무, 콜센터 고객 대기시간, 프로세스 관리
•
구현
◦
리스트로 구현은 가능하나, 시간복잡도가 증가한다.
◦
Queue 자료구조를 지원함: LinkedList
◦
java.util.Queue, java.util.LinkedList import 하면 사용할 수 있다.
•
지원 매소드
◦
add : 추가
◦
offer : 추가
◦
poll : 첫번째 요소 제거, queue 비어있다면 null
◦
remove : remove 첫번째 요소 제거
◦
clear : 큐 전체 제거
◦
peek : 맨 첫번째 요소 조회
예시
package practice.algorithm.stackqueue;import java.util.LinkedList;import java.util.Queue;public class QueuePractice { public static void main(String[] args) { Queue<String> queue = new LinkedList<>(); queue.offer("h"); queue.offer("e"); queue.offer("l"); queue.add("l"); queue.add("o"); System.out.println("queue = " + queue); System.out.println("queue.isEmpty() = " + queue.isEmpty()); System.out.println("queue.poll() = " + queue.poll()); System.out.println("queue.remove() = " + queue.remove()); System.out.println("queue.peek() = " + queue.peek()); System.out.println("queue = " + queue); queue.clear(); System.out.println("queue = " + queue); System.out.println("queue.isEmpty() = " + queue.isEmpty()); /** * queue = [h, e, l, l, o] * queue.isEmpty() = false
* queue.poll() = h
* queue.remove() = e
* queue.peek() = l
* queue = [l, l, o] * queue = [] * queue.isEmpty() = true
* */ }}
Java
복사
우선순위 큐 - priority queue
•
선형 큐와는 다르게 우선순위가 높은 요소일수록 먼저 삭제된다.
•
만약에 우선순위가 같다면, 삽입된 순서를 따른다.
•
•
예시
◦
응급실에서 응급환자가 우선순위가 높아서 먼저 진료받는 환자가 뒤로 밀리는 경우
•
시간 복잡도 : 힙으로 구현한다면,
◦
삽입과 삭제 : O(logN)
◦
우선순위가 가장 높은 요소를 탐색할 때에는 O(1)
원형 큐 - circular queue, ring buffer
•
큐는 사이즈가 고정되어있고 데이터 삽입과 삭제시 나머지 요소들은 이동하지 않는다. 그러다가 결국 index 가 마지막을 가리키게 되면, 앞쪽 공간이 텅텅 비어있더라도 그것을 제대로 활용하지 못하게 된다.
•
원형 큐는 문제를 해결하기 위해서 현재의 요소들을 앞으로 재배치하는 별도의 작업을 진행한다.
•
function enqueue() { // ... rear = (rear + 1) % queue_size;
}
function dequeue() { // ... front = (front + 1) % queue_size;
}
◦
위와 같이 큐 전체 사이즈가 5이고, 현재 rear 가 마지막 인덱스인 4를 가리키고 있다면, 다시 enqueue 하는 과정에서 전체 인덱스 범위를 넘어서는 5가 되어버린다. 이때, 이 5를 다시 전체 큐의 사이즈만큼 나누게 되면, (4+1) % 5 = 0이 된다. 인덱스가 다시 처음으로 돌아가게 되는 것이다.