Computer Science/자료구조

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

dbssk 2023. 3. 15. 01:40

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();

참고: 자바의 정석