Queue

큐(Queue)

큐는 먼저 들어간 데이터가 먼저 나오는 FIFO(FIFO : 선입선출, First In First Out)구조의 자료구조

ex. 버스 줄서기

삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.

Enqueue : 데이터를 큐의 뒤(rear)에 추가(줄 맨뒤에 서기)

Dequeue : 데이터를 큐의 앞에서 제거(줄 맨 앞 사람이 빠지는 것)

기본연산

• front : deQueue 할 위치 기억
• rear : enQueue 할 위치 기억

enQueue()

• 데이터를 넣는 연산
• 데이터가 들어오면 rear는 새로 들어온 데이터가 된다. (R -> R’)

dnQueue()

• 데이터를 빼는 연산
• 데이터가 나가면 front는 다음 데이터가 된다. (F -> F’)

isEmpty()

• 데이터가 비었는지 확인
• front == rear

isFull()

• 데이터가 꽉 차있는지 확인
• rear == QueueSize

Peek()

• 가장 첫번째 데이터 확인(삭제 x)

자바 속 Queue

자바에서 Queue는 인터페이스이기 때문에 LinkedList or ArrayDeque로 구현

Queue 선언

Queue<Integer> queue = new LinkedList<>();
Queue<String> queue = new ArrayDeque<>();