자바 [JAVA] - Queue Interface (큐 인터페이스)

 

자료구조 관련 목록 링크 펼치기 

 

 

 

 0. 자바 컬렉션 프레임워크 (Java Collections Framework)

 1. 리스트 인터페이스 (List Interface)

 2. 어레이리스트 (ArrayList)

 3. 단일 연결리스트 (Singly LinkedList)

 4. 이중 연결리스트 (Doubly LinkedList)

 5. 스택 인터페이스 (Stack Interface)

 6. 스택 (Stack)

 7. 큐 인터페이스 (Queue Interface) - [현재 페이지]

 8. 배열 큐 (Array Queue) 

 9. 연결리스트 큐 (LinkedList Queue)

10. 배열 덱 (Array Deque)

11. 연결리스트 덱 (LinkedList Deque)

12. 힙 (Heap)

13. 우선순위 큐 (PriorityQueue)

14. 셋 인터페이스 (Set Interface)

15. 해시 셋 (Hash Set)

16. 연결 해시 셋 (Linked Hash Set)

17. 이진 탐색 트리 (Binary Search Tree)

 

 

 

 

 

 

 

 

---

 

• Queue Interface

 

 

 

 

 

 

만약 이 글을 처음 접한다면 자바 컬렉션 프레임워크 (Java Collections Framework) 글을 먼저 보고 오셨으면 한다.

 

 

다른 자료구조 포스팅을 보셨다면 알겠지만, 자료구조를 구현하는 포스팅 하기 전에 인터페이스를 하나 만들고 시작하려 한다. Interface 장점이 해당 인터페이스를 implements 하는 클래스는 인터페이스에 선언 된 메소드들을 강제적으로 구현하도록 하고 있기 때문에 깜빡 잊어먹고 구현을 안하는 실수를 방지할 수 있다.

 

 

일단 큐(Queue)에 대해 간략하게 설명하겠다.

 

Queue 는 '대기열' 이라고 이해하면 되는데, 우리가 예로들어 에버랜드에 놀이기구를 타기위해 줄을 서서 대기하는 열을 생각하면 된다.

영어 단어를 보면 처음 접하는 분들은 생소할 수 있다. 게임을 즐겨하는 분들이라면 흔히 게임에서 흔히 다인 큐, 솔로 큐, '큐 잡는다' 등 큐가 들어간 단어들이 많은데, 그 큐가 지금 우리가 다루고자 하는 Queue를 의미한다.

 

 

그럼 그 큐(Queue)가 뭘까?

앞서 말했듯 대기열이라고 했다. 즉 '선입선출(先入先出, FIFO = First In First Out)' 자료구조다. 먼저 들어온 놈이 먼저 나가는 것. 대표적으로 놀이공원의 대기 줄도 있고, 은행 같은 곳에서 번호표를 받는 것도 Queue라고 할 수 있다. 

 

큐를 그럼 어디에 활용할까?

 

쉽게 생각하면 시간 순으로 어떤 작업 또는 데이터를 처리할 필요가 있는 것들은 큐의 성질을 갖고 있다고 보면 된다. 또한 대표적으로 알고리즘에서는 BFS(너비 우선 탐색)에 사용된다.

 

 

 

 

 

참고로 자바에서 제공하고 있는 큐는 정확히 말하자면 인터페이스에 불과하고, 큐를 구현하는 클래스는 크게 PriorityQueue(우선순위 큐), ArrayDeque(배열 양방향 큐), LinkedList(연결리스트) 이렇게 3가지가 있다.

 

즉, 어디까지나 실질적으로는 LinkedList 처럼 객체를 연결한 방식 또는 PriorityQueue나, ArrayDeque 처럼 배열에 의해 구현되기 때문에 정해진 방식이 있는 것이 아니다.

 

 

추가로 여기서는 자료구조에 중점을 둘 것이라 LinkedList나 ArrayList를 상속하는 것 까지는 고려하진 않을 것이다. 만약 LinkedList를 구현했었다면 LinkedList를, ArrayList를 구현했었다면 ArrayList를 상속받아 쉽게 구현할 수 있으니 응용해보는 것도 좋을 것이다.

 

 

 

 

 

 

 

 

그럼 이제 Queue 인터페이스에 선언 할 메소드들을 살펴보도록 하겠다.

 

 

<Queue Interface에 선언 할 메소드>

 

 

 

 

큐 같은 경우는 실제로 자바에서도 6가지 밖에 선언이 되어있지 않다.

 

자세한 건 아래 링크를 보면 알겠지만, 먼저 설명하자면 offer() 의 경우 리스트에서의 add() 와 비슷한 역할이고, poll() 의 경우는 remove() 와 비슷한 역할이며, peek() 은 element() 와 비슷한 역할이다.

 

다만 차이점은 add(), remove(), element()는 필자의 포스팅을 보거나 써봤으면 알겠지만, 내부적으로 예외를 처리하고 있다. 예로들어 index 밖을 넘어가거나, 삭제할 요소가 없거나 등등 이러한 예외적 경우에 대해 예외를 던졌다.

 

하지만 offer(), peek(), element()의 경우 예외를 던지는 것이 아닌 특별한 값을 던지는데, 일반적으로 null 또는 false를 던진다고 생각하면 된다. 자세한 건 API에 잘 나와있다.

 

docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Queue.html#

Queue (Java SE 11 & JDK 11 )

 

 

다만, Queue에서 기본적으로 offer, poll, peek을 많이 쓰기도 하고 원리도 비슷하니 이 셋만 쓸 것이다.

 

 

필자는 이를 토대로 앞으로 구현해나갈 것이니 참고하시길 바란다.

 

package Interface_form;

/**
 * 
 * 자바 Queue Interface입니다. <br>
 * Queue는 ArrayQueue, LinkedQueue,
 * Deque, PriorityQueue 에 의해 구현됩니다.
 * 
 * @author st_lab
 * @param <E> the type of elements in this Que
 *
 * @version 1.0
 * 
 */


public interface Queue<E> {
	
	/**
	 * 큐의 가장 마지막에 요소를 추가합니다.
	 * 
	 * @param e 큐에 추가할 요소 
	 * @return 큐에 요소가 정상적으로 추가되었을 경우 true를 반환 
	 */
	boolean offer(E e);
	
	/**
	 * 큐의 첫 번째 요소를 삭제하고 삭제 된 요소를 반환합니다.
	 * 
	 * @return 큐의 삭제 된 요소 반환 
	 */
	E poll();
	
	/**
	 * 큐의 첫 번째 요소를 반환합니다.
	 * 
	 * @return 큐의 첫 번째 요소 반환 
	 */
	E peek();
	
	
}

 

 

 

 

이 번에 메인으로 구현할 큐의 경우 Queue에 한정하여 배열과 연결리스트를 사용한 방법 각각 구현 할 것이다. Deque의 경우 연결리스트로만 구현 할 것이다.

 

또한 기본적으로 여러분들이 재정의(Override), 예외처리(throw), 객체(Object), 인터페이스(nterface), 제네릭(Generic) 이렇게 5개에 대한 기본 지식은 있다는 전제하에 설명 할 것이다. 그렇지 않고 하나하나 설명하다보면 길이 너무 길어져 핵심을 못짚게 되어 결정했다.

 

 

 

 

 

 

---

• 정리

 

 

오늘은 간단하게 Queue에 대해 알아보고 앞으로 사용할 Queue Interface를 간단하게 만들어놓았다. 이를 토대로 ArrayQueue, LinkedQueue, Deque, PriorityQueue 클래스들을 구현할 것이다. 혹여 앞으로의 포스팅에 있어 모르거나 헷갈리는 것이 있다면 언제든 댓글 남겨주시면 감사하겠다.