JAVA에서의 Queue 사용법( C++과 다른 점이 있으므로 주의!!)

잠깐 덱에 관해서도 살짝 언급하고 가자면, 큐는 단방향으로 요소(데이터)가 들어가는 방향과 나오는 방향이 다르다.

반면 덱은 Double-ended Queue 의 줄임말인데, 말 그대로 양방향의 지점이 있는 큐다. 설명으로는 어려울테니 컨셉이 어떤지 그림으로 보고가도록 하자.

 

 

 

 

 

 

 

그리고 이 문제를 풀 떄 중요한 점이 있다.

 

물론 대개는 구현해서 풀겠지만, 라이브러리를 사용한다는 가정하에 C++같은 경우 queue 라이브러리에는 가장 맨 뒤에 있는 요소를 반환하는 back() 메소드가 있지만, Java의 경우는 Queue 인터페이스로 선언하여 라이브러리를 사용할 경우 back() 과 같은 역할을 하는 메소드는 없다. (맨 앞의 원소를 반환하는 것은 peek() 메소드가 있다.)

 

즉, 예로들어 아래와 같이 쓸 경우 맨 뒤의 원소를 반환하는 메소드가 없다는 것이다.

	Queue<Integer> q = new LinkedList<>();
	Queue<Integer> q = new ArrayDeque<>();

 

쉽게 말해 Queue 및 Queue의 부모 인터페이스인 Collection으로 선언하는 경우 (Queue<Integer> q 와 같이) 뒤의 원소를 꺼내올 수 있는 방법이 없다.

 

아래 이미지를 참고하면 된다.

 

 

 

 

그러면 어떻게 해야 할까?

 

일단 해결책으로 여러가지가 있지만 라이브러리를 이용하는 방법 중 대표적으로 활용 할 수 있는 방법들을 소개하자면 이렇다.

아래 백준 문제 참조!!

https://www.acmicpc.net/problem/18258

18258번: 큐 2

	/*
	* 방법 1
	* LinkedList는 Deque(Queue를 상속받고 있음)도 구현하고 있기 때문에
	* LinkedList로 선언해주어 사용 할 수 있다.
	*/
	LinkedList<Integer> q = new LinkedList<>();
	q.offer(); // push
	q.pop(); // pop
	q.size(); // size
	q.isEmpty(); // empty
	q.peek(); // front
	q.peekLast(); // back
	/*
	* 방법 2
	* Deque 인터페이스로 선언한 뒤
	* LinkedList나 ArrayDeque로 생성하여 이용 할 수 있음
	*/
	Deque<Integer> q = new LinkedList<>();
	Deque<Integer> q = new ArrayDeque<>();
	// 메소드는 동일함
	q.offer(); // push
	q.pop(); // pop
	q.size(); // size
	q.isEmpty(); // empty
	q.peek(); // front
	q.peekLast(); // back

 

 

이렇게 여러 생성 방법이 있으니 라이브러리를 이용할 경우 위에서 각자가 편한 선언 방식을 쓰면 된다.

 

 

또는 마지막 방법으로는 직접 구현하는 것이다. 이 방법은 필자가 위에 참고하라는 글 중 배열 큐(ArrayQueue)에 모든 원리가 다 들어가 있으니 달리 설명하진 않겠다. 대신 주석으로 달아놓도록 하겠다.

 

참고로 ArrayList로도 큐처럼 사용 할 수는 있지만 삽입 삭제가 많아서 효율이 LinkedList 보다 안좋다. 필자가 테스트 해보니까 시간초과가 난다.