Queue에 대해 알아보자

이번 시간에는 queue에 대하여 알아보려 합니다.

Queue는 ‘대기줄’이라는 뜻을 가진 영어 단어입니다.

Java의 Queue 인터페이스는 선입선출(FIFO: First In First Out) 형태로 자료를 보관하고 꺼내는 버퍼입니다.

음식점, 은행 같은 곳에서 줄을 설 때 먼저 온 사람부터 서비스를 받을 수 있는 것처럼, 가장 먼저 저장(push)된 데이터가 가장 먼저 인출(pop)됩니다.

Queue는 주로 linkedlist 형태로 구현되며, queue에서 자주 사용되는 메소드는 다음과 같습니다.

메소드	설명
boolean add(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴.
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함.
boolean offer(E e)	해당 큐의 맨 뒤에 전달된 요소를 삽입함.
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환함. 만약 큐가 비어있으면 null을 반환함.
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고, 해당 요소를 큐에서 제거함. 만약 큐가 비어있으면 null을 반환함.
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거함.

예제와 같이 queue을 구현해 보았습니다.

package jaryogujo;
import java.util.*;

public class Queue {

	public static void main(String[] args) {
		LinkedList<String> qu = new LinkedList<String>(); // 큐의 생성

		// offer () 메소드를 이용한 요소의 저장
		qu.offer("넷");
		qu.offer("둘");
		qu.offer("셋");
		qu.offer("하나");

		// peek() 메소드를 이용한 요소의 반환
		System.out.println(qu.peek());
		System.out.println(qu);

peek()을 통해 맨 처음 들어가서 가장 먼저 반환될 요소가 ‘넷’이라는 사실을 알 수 있었습니다.

그리고 qu에 저장된 순서대로 [넷, 둘, 셋, 하나] 가 출력됩니다.
stack에서처럼 offer()가 아닌 add()를 사용할 수도 있지만, 두 메서드는 약간의 차이점이 존재합니다.

// poll() 메소드를 이용한 요소의 반환 및 제거
	System.out.println(qu.poll());		
       	System.out.println(qu);

Poll()메서드는 맨 처음 들어가서 가장 먼저 반환되는 요소를 보여주고, 이를 queue 객체에서 빼내 주는 역할을 합니다.

// remove() 메소드를 이용한 요소의 제거
		qu.remove("하나");
		System.out.println(qu);
	}

}

Remove()메서드를 통해 “하나”를 제거했습니다.

Queue도 stack과 마찬가지로 인덱스 주소 값은 반환할 수 있지만, 어떤 값이 어디에 들어있는 지 탐색하는 기능은 없습니다.

줄 중간에 누가 서있는지를 궁금해하지는 않는다는 뜻입니다.

따라서 삽입, 삭제 외에 다른 기능이 없습니다.

맨 앞에 무엇이 있는지만 보이고, 누가 있는지는 알 수 없는 줄로 생각할 수 있을 것 같네요.

방향성도 없으니, 삽입과 삭제 모두에서 시간복잡도는 O(1)이겠죠.

이번 시간에는 queue에 대해 알아보았습니다.