Queue 와 Deque(Double ended queue)

2017-02-24

2021-10-07

Deque, Queue, java

** 이 포스트는 ArrayList 와 LinkedList +@
의 연장선으로 Queue와 Deque에 대해서 간단하게 살펴보겠습니다. **

먼저 공식 홈페이지의 설명을 훑어 보고 오겠습니다.

Queue (Java Platform SE 8 )
Deque (Java Platform SE 8 )

Queue 역시 Collection과 Iterable 인터페이스를 부모로 하고 있는것을 알 수 있고, Deque는 Queue의 sub interface 입니다.

All Known Subinterfaces:

BlockingDeque, BlockingQueue, Deque, TransferQueue

그리고 ArrayList 와 LinkedList +@에서 살펴봤던 LinkedList는 실제로 Queue를 implementing 했다는 것을 확인 할 수 있습니다.

All Known Implementing Classes:

AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue

학교다닐때 들어봤음직한 stack, queue, deque를 그림으로 표현해봤습니다.

Stack : 입구와 출구가 같습니다 = 먼저 들어온 데이터가 가장 나중에 나갈 수 있습니다 = LIFO (Last In First Out)
Queue : 입구와 출구가 다릅니다 = 먼저 들어온 데이터가 가장 먼저 나갑니다 = FIFO (First In First Out)
Deque : 입구와 출구가 같아도 되고 달라도 됩니다.

#Queue

@Test
public void queue(){
	Queue<String> queue = new LinkedList<>();
	queue.add("first");
	queue.add("second");
	queue.add("third");

	assertEquals("first", queue.remove());
	assertEquals("second", queue.poll());
	assertEquals("third", queue.peek());
	assertEquals("third", queue.poll());

	try {
		queue.remove();
	} catch (NoSuchElementException e) {
		assertNotNull(e);
	}
	assertNull(queue.poll());
}

먼저 Queue를 살펴 보면 add(), remove(), poll(), peek() 함수를 사용했는데

add는 말 그대로 queue에 값을 넣는것 입니다.
remove, poll도 말 그대로 queue에서 값을 제거 하는것 입니다. (제거 하면서 그 값을 return 합니다.)
도 queue에서 값을 뽑아 내는것 입니다
peek 은 값은 return하지만 queue에서 제거하지 않습니다.

remove와 poll 모두 값을 제거하면서 return 해 주는데 왜 같은일을 하는 함수를 나눠놨을까요?

Retrieves and removes the head of this queue. This method differs from poll only in that it throws an exception if this queue is empty.

위는 remove의 javadoc에 적혀 있는 내용입니다.
더이상 queue에서 꺼낼 것이 없는 상황에서 remove를 하게 되면 **NoSuchElementException**을 던집니다.

하지만 더이상 queue에서 꺼낼 것이 없을 때 poll을 하면 null을 return 합니다.

위의 Testcase에서 제가 모든 값을 다 뽑아낸 상태에서 한번도 remove를 하게 해 놓고 NoSuchElementException으로 catch 한 부분을 보시면 assertNotNull(e), 즉 저 테스트 케이스가 pass 하려면 e는 반드시 NoSuchElementException 이어야 합니다.
반면에 poll로 뽑아낸 부분을 보시면 assertNull로 체크를 합니다.

#Deque

@Test
public void deque(){
  Deque<String> deque = new LinkedList<>();

  //queue와 동일하게 FIFO 구조로 사용 가능
  deque.add("first");  //== deque.addLast();
  deque.add("second");
  deque.add("third");

  assertEquals("first", deque.remove());  //== deque.removeFirst();
  assertEquals("second", deque.poll());   //== deque.pollFirst();
  assertEquals("third", deque.peek());
  assertEquals("third", deque.poll());

  //stack 처럼 LIFO 구조로 사용 가능
  deque.addLast("first");
  deque.addLast("second");
  deque.addLast("third");

  assertEquals("third", deque.removeLast());
  assertEquals("second", deque.pollLast());
  assertEquals("first", deque.peekLast());
  assertEquals("first", deque.pollLast());

}

@Test
public void stack(){
  Deque<String> stack = new ArrayDeque<>();
  stack.push("first");
  stack.push("second");
  stack.push("third");

  assertEquals("third", stack.pop());
  assertEquals("second", stack.pop());
  assertEquals("first", stack.peek());
  assertEquals("first", stack.pop());
}

위는 Deque 으로 구현한 queue와 stack 입니다.
Deque는 Queue를 implementing 했기 때문에 queue에서 사용하던 add(), remove(), peek(), poll()을 그대로 사용할 수 있습니다. 그렇게 되면 queue의 특성인 FIFO 를 그대로 따라 갑니다.

하지만 deque은 입구와 출구가 달라도 되기 때문에 기존 함수에 접미사인 First와 Last를 붙인 addFirst(), peekLast()등과 같이 데이터를 넣고 뺄때 명시적으로 TOP에 넣을지 Bottom에 넣을지 정해 줄 수 있습니다. 즉, queue와 stack의 성질을 모두 가질 수 있습니다.

혹은 Stack의 함수인 push()와 pop()을 이용해서 전형적인 stack의 모습으로 구현 하는 것도 가능합니다.

Developmentjava

#Queue

#Deque