Queue(큐)
- 줄을 서다
- 먼저 들어간 데이터가 먼저 나오는 자료 구조
- 맛집에서 줄을 선 순서대로 식당에 입장하는 것과 유사
- 선입선출
- FIFO(First in first out)
큐의 ADT
| 구분 | 정의 | 설명 |
|---|---|---|
| 연산 | boolean isFull() | 큐에 들어 있는 데이터의 개수가 maxsize인지를 확인해 boolean 값 반환 |
| boolean isEmpty() | 큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean 값 반환 | |
| void add(ItemType item) | 큐에 데이터를 add | |
| ItemType poll() | 큐에서 처음에 add한 데이터를 poll하고 그 데이터를 반환 | |
| 상태 | int front | 큐에서 가장 마지막에 poll한 위치 기록 |
| int rear | 큐에서 최근에 add한 데이터의 위치 기록 | |
| ItemType data[maxsize] | 큐의 데이터를 관리하는 배열. 최대 maxsize개의 데이터를 관리 |
큐의 구현
Queue 인터페이스 활용
- add 연산 : add() / offer()
- poll 연산 : poll()
ArrayDeque 클래스 활용
- 일반적인 코딩 테스트에서는 LinkedList보다 ArrayDeque를 더 많이 사용함
//큐를 구현한 ArrayDeque 객체 생성
Queue<Integer> queue = new ArrayDeque<>();
//큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);
//큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
//first : 1
//큐에 데이터 추가
queue.add(4);
queue.add(5);
//큐의 맨 앞 데이터를 제거하면서 반환
first = queue.poll();
//first : 2덱을 큐처럼 사용하기
- 덱 : Double Ended Queue. 양 끝에서 삽입이나 삭제할 수 있는 큐를 구현한 것
- 양 끝에서 삽입이나 삭제할 수 있음
ArrayDeque queue = new ArrayDeque<>();
ArrayDeque<Integer> queue = new ArrayDeque<>();
//큐에 데이터 추가
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);
//큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
//first : 1
//큐에 데이터 추가
queue.addLast(4);
queue.addLast(5);
//큐의 맨 앞 데이터를 제거하면서 반환
first = queue.pollFirst();
//first : 2큐를 기준으로 왼쪽이 first, 오른쪽이 last이다. 그래서 데이터를 왼쪽에서 꺼내는 것은 pollFirst()이고, 오른쪽으로 넣는 것은 addLast()이다.
또한, 데이터를 addFirst()로만 넣고 pollFirst()로만 꺼내면 stack의 push(), pop()과 동일하므로 ArrayDeque 하나로 큐, 스택, 덱을 전부 구현할 수 있는 것이다.
컴퓨터가 이해하는 코드는 바보도 작성할 수 있다. 사람이 이해하도록 작성하는 프로그래머가 진정한 실력자다. -마틴 파울러