큐는 원소에 대해 enqueue, dequeue 동작을 가지고 있고 순서가 있는 집합을 제공하는 추상 데이터 타입이다.
enqueue는 집합의 가장 끝(rear) 쪽에 원소를 추가하는 동작이다
dequeue는 집합의 가장 앞(front) 쪽에 원소를 제거하는 동작이다
먼저 들어온 값을 먼저 제거하므로 FIFO(First In, First Out)으로 불린다.
추가적으로 Peek 동작이 있는데,
Peek은 dequeuing을 하지 않으면서 집합의 가장 앞 쪽 값을 반환하는 동작이다.
Method
enqueue
dequeue
peek
isEmpty
Example
은행 업무
콜센터 고객 대기시간
BFS
import
타입은 Queue로 선언이 가능하지만,
인스턴스는 Linked List를 이용하여 만든다
import java.util.Queue
import java.util.LinkedList
Offer vs Add
Offer은 크기를 넘어서 넣게 되면 IllegalStateException이 발생하지 않지만
Add는 크기를 넘어서 넣는 경우 IllegalStateException을 던진다
(Capacity Restriction)
Priority Queue
일반적인 스택, 큐와 같은 추상 데이터 타입
일반적이지 않게 원소가 "우선 순위"를 가지고 있음
우선 순위가 높은 경우, 우선 순위가 낮은 원소보다 먼저 제공된다
우선 순위가 같은 경우, 일반적인 Queue와 같이 동작한다
import
import java.util.PriorityQueue
Stack으로 Queue 만들기
stack 자료구조를 2개 이용한다.
삽입 시 stack 자료구조 한 곳에 계속 추가한다.
삭제 시 stack 자료구조의 원소를 pop하며 다른 stack에 넣는다
마지막 1개가 남았을 때, 해당 원소를 다른 스택에 넣지 않고 반환한다
Deque
Double Ended Queue의 줄임말
해석을 하면 양쪽 끝에서 삽입과 삭제가 모두 가능한 추상 데이터 타입이다
두 개의 포인터를 사용한다
언제 사용할까?
시작점, 끝점의 사용이 빈번한 경우에 좋은 선택지
List는 끝 점에 대해 O(n)인 반면 Deque은 O(1)이다
Method
first
last
addFirst
addLast
removeFirst
removeLast
remove (== queue)
add ( == queue)
size
contains
Import
import java.util.ArrayDeque
