[자료구조] Queue(큐) & Deque(덱)

Queue란?

• 선입선출 (First In First Out; FIFO) 자료구조
  • 먼저 들어온 데이터가 먼저 나가는 구조
• 입력 순서대로 데이터 처리가 필요할 때 사용
  • BFS (Breath-First Search)

---

Queue 기본 구조

---

Queue 기본 연산

• Queue 생성
  • 큐는 배열기반의 컬렉션 클래스를 사용하면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터를 복사해야 하므로 LinkedList로 구현하는 것이 적합하다.

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

Queue queue = new LinkedList();
// Queue는 interface로 구현되어 있음. 따라서 바로 객체로 만들 수 없음. -> Queue queue = new Queue(); (X)

• add(item) / offer(item) - 큐의 rear에 요소 추가

queue.add(1);
queue.offer(2);

• poll() - 큐의 front에 있는 요소 반환하며 삭제

queue.poll();

• peek() - 큐의 front에 있는 요소를 반환, 하지만 삭제는 하지 않는다. 스택과는 다르게 큐가 비어있으면 null을 반환한다.

queue.peek();

• contains(item) - 큐 안에 요소가 있는지 확인

queue.contains(1);

• isEmpty() - 큐가 비어있는지 확인

queue.isEmpty();

• clear() - 큐의 모든 요소 삭제

queue.clear();

---

Queue의 형태

1. 선형 큐
2. 원형 큐

---

Deque란?

• Double-Ended Queue 즉, 양쪽 끝에 추가/삭제가 가능하다.
• 덱은 스택과 큐를 하나로 합쳐놓은 것과 같아서 스택으로 사용할 수 있고, 큐로 사용할 수도 있다.

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()	-
peekLast()	-	peek()

Deque vs Queue

---

Deque 기본 연산

• Deque 생성
  • LinkedList와 ArrayDeque를 사용할 수 있다.

import java.util.LinkedList;
import java.util.Deque;

Deque deque = new LinkedList();

• add(item) / offer(item) - 큐의 rear에 요소 추가

deque.add(1);
deque.offer(2);

• poll() / pollFirst() - 큐의 front에 있는 요소 반환하며 삭제
  pollLast() - 큐의 rear에 있는 요소 반환하며 삭제

deque.poll();
deque.pollFirst();
deque.pollLast();

• peek() / peekFirst() - 큐의 front에 있는 요소를 반환, 하지만 삭제는 하지 않는다.
  peekLast() - 큐의 rear에 있는 요소를 반환

deque.peek();
deque.peekFirst();
deque.peekLast();

• contains(item) - 큐 안에 요소가 있는지 확인

deque.contains(1);

• isEmpty() - 큐가 비어있는지 확인

deque.isEmpty();

• clear() - 큐의 모든 요소 삭제

deque.clear();

---

참고: 자바의 정석