큐(Queue)

큐(Queue)

큐도 스택과 같이 기본적으로 알아둬야 하는 자료구조중 하나이다. 해당 자료구조는 선형 구조와 원형 구조 두가지가 있으며, 상황에 맞게 사용하면 된다. 

https://slidesplayer.org/slide/14917894/

큐는 선입선출 (First In First Out) 자료구조이다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조를 이용하고 있다. 해당 자료구조는 프린터 출력 대기열, BFS(Breath - First Search) 등에 사용이 된다.

 

BFS(Breath - First Search)
가장 얕은 노드부터 검색을 하면서 깊은 노드까지 탐색하는 방식.
Tree 구조에서 사용하는 검색 방식

---

큐 용어설명

• Front : 큐에서 데이터를 꺼내면 제일 먼저 나오는 부분.
• Rear : 큐에서 데이터가 추가되는 부분.
• Enqueue : 큐에 데이터를 삽입.
• Dequeue : 큐에서 데이터를 꺼냄. 

---

자바에서 큐선언 및 초기화, 메소드

선언 및 초기화

• Queue queue = new LinkedList();
• LinkedList queue = new LinkedList(); 
  • new Queue로 사용시 Queue는 인터페이스로 미구현되 메소드들을 구현해야함.

 

메소드

• .add(), offer() : 큐에 데이터 추가.

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

• .poll(), remove() : 큐에서 데이터를 꺼냄. (비어 있을 때 꺼내면 null 값을 반환함.)

System.out.println(queue.poll());
System.out.println(queue.remove());

• .peek() : 큐에서 Front 값을 보여줌.

System.out.println(queue.peek());

• .contains() : 매개변수 값이 존재하는지에 대한 여부 확인(Boolean)

System.out.println(queue.contains(3));

• .size() : 현재 큐의 사이즈를 보여줌.

System.out.println(queue.size());

• .isEmpty() : 현재 큐가 비어져 있는지 확인(Boolean)

System.out.println(queue.isEmpty());

• .clear() : 큐에 있는 모든 값들을 초기화.

queue.clear();

---

시간 복잡도

• Insertion : O(1)
• Deletion : O(1)
• Search : O(n)