큐란?
-
FIFO(First In First Out)으로 처음 입력된 자료가 먼저 출력되는 자료구조
-
BFS, 버퍼 등에 사용된다.
-
push : 데이터 삽입
-
pop : 가장 먼저 입력된 데이터 뺌
-
peek : 다음에 출력될 데이터 조회
-
isFull : 가득 차있는지 여부
-
isEmpty : 비어있는지 여부
Array로 구현한 큐
- 구현
큐의 크기인 queueSize 만큼 배열을 생성하고.
현재 데이터가 존재하는 가장 첫 인덱스를 top. 가장 마지막 인덱스를 rear로 두어,
top에서 pop이. rear에서 push가 일어나도록 구현하였다.
- 한계
Size를 5만큼 잡은 뒤, push를 다섯번. pop을 다섯번하면.
큐가 비어있는데도, rear가 MAX(4) 까지가서 큐가 꽉 찼다고 인식하게 된다.
Linked List로 구현한 큐
- 구현
Stack에서 활용한 node 클래스를 활용하였다.
큐의 제일 처음 노드를 head. 큐의 제일 마지막 노드를 tail로 하여. 초기에는 null로 둔다.
head에서 pop이 일어나고, tail에서 push가 일어나도록 구현하였다.
Example
0 1 2 3 4 순으로 push 후 pop을 진행하자, 먼저 입력한 순서대로 pop이 진행되는 것을 확인할 수 있다.
라이브러리 사용
java에서 queue는 인터페이스로 제공되므로 LinkedList를 통해 생성한다.
add 메서드로 push를. poll메서드로 pop을 수행하게된다.
