큐란?
- 대기줄을 서는 것처럼 데이터를 이어지게 형태로 자료를 구성하는 구현 방식
- 데이터가 이동하는 입구와 출구가 각각 존재한다.
큐의 특징
- 리스트의 한쪽 끝에서는 삽입 작업만 이루어지고, 반대쪽 끝에서는 삭제 작업만 이루어 진다.
- front
- 큐의 머리에 해당한다.
- 가장 먼저 삽입된 데이터가 front에 해당된다.
- 큐에서 데이터 삭제 연산 시 front는 삭제된 데이터의 다음 차례에 해당하는 데이터를 가리키게 된다.
- rear
- 큐의 꼬리에 해당한다.
- 가장 나중에 삽입된 데이터가 rear에 해당된다.
- 큐에서 데이터 삽입 연산 시 rear는 새로 삽입된 데이터를 가리키게 된다.
- 선입선출 (FIFO, First-In-First-Out)
- 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 특징
- 큐의 연산
- enQueue
- 큐에서 rear을 통해 새로운 데이터를 삽입하는 연산
- deQueue
- 큐에서 front을 통해 마지막 데이터를 삭제하는 연산
- enQueue
구현하기
- Java에서는 큐를 인터페이스만 존재하기 떄문에 LinkedList를 통해서 구현해야 한다.
- 예시
Queue<String> queueStr = new LinkedList<>();
데크
데크(Deque, Double-ended queue)란?
- 큐 두 개 중 하나를 좌우로 뒤집어서 붙인 구조
데크의 특징
- 큐의 양쪽 끝에서 삽입·삭제 연산으 모두 수행할 수 있다.
- 양쪽 끝에서 삽입·식제 연산을 수행하면서 앞·뒤에서 데크의 길이이가 변경하는 일이 발생한다.
- 유연한 동작을 위해 순차 자료구조보다는 이중 연결 리스트를 이용하여 구현하는 것이 효율적이다.
큐의 응용
- 운영체에의 작업 큐
- 시뮬레이션에서의 큐잉 시스템