Queue와 Deque

✔ Queue

• LinkedList로 구성되어 있으며, 한 쪽에서는 삽입이 한 쪽에서는 삭제가 이루어지는 형태의 구조이다.
• 위의 구조로 인해 선입선출(FIFO, First-in First-out)의 구조를 가진다.
  

✔ Deque

• Double Ended Queue의 줄임말로, 보통 덱(Deck)이라고 읽는다.
• Queue의 장점과 Stack의 장점을 합친 것으로, 큐의 시작과 끝이 이어져있어 양쪽 모두에서 삽입과 삭제가 가능하다.
  

---

✔ Java에서의 Queue와 Deque

• 두 자료구조 모두 Java.util 에서 사용이 가능하다.
• Deque같은 경우에는 Queue를 상속 받기 때문에, Queue의 메서드를 먼저 살펴보고, Deque에서는 어떻게 확장되었는지 알아보도록 하자.

✅ Queue

		// Queue는 LinkedList 기반
		Queue<String> que = new LinkedList<>();

		// ~~~ 삽입 : Queue는 맨 뒤로만 값을 넣을 수 있음

		// add : 맨 뒤로 값 삽입. 삽입 실패 시 에러 발생
		que.add("add1");
		que.add("add2");

		// offer : 맨 뒤로 값 삽입. 삽입 실패 시 아무 일도 발생하지 않음
		que.offer("offer1");
		que.offer("offer2");


		// ~~~ 확인 : 현재 큐의 첫 번째 값 확인
		
		que.element(); // 큐의 첫 번째 값 확인. 없을 시 에러 발생
		
		que.peek(); // 큐의 첫 번째 값 확인. 없을 시 null 반환


		// ~~~ 삭제 : 현재 큐의 첫 번째 값 삭제 및 반환

		que.remove(); // 큐의 첫 번째 값 삭제. 없을 시 에러 발생
		String a = que.remove();
		System.out.println(a);

		que.poll(); // 큐의 첫 번째 값 삭제. 없을 시 null 반환
		String b = que.poll();
		System.out.println(b);

• Queue의 경우, LinkedList를 기반으로 하기 때문에 LinkedList로 선언한다.
• 선입선출이 원칙이므로 맨 뒤로만 값을 넣고, 맨 앞으로만 값을 삭제할 수 있다.
• 각 메서드별로 Error를 발생시키는 것과 무시하는 것 두 가지로 나뉜다.

✅ Deque

		Deque<String> que = new ArrayDeque<>();
		
		
		// 삽입 관련
		
		// add : 공간이 부족하여 삽입할 수 없을 때 에러를 발생시킨다.
		que.addFirst("addFirst");
		System.out.println("que = " + que);

		que.add("add");
		System.out.println("que = " + que);

		que.addLast("addLast");
		System.out.println("que = " + que);

		// addAll : 다른 Collection의 값들을 맨 뒤에 삽입한다.
		Deque<String> que2 = new ArrayDeque<>(Arrays.asList("addAll1", "addAll2"));
		que.addAll(que2);
		System.out.println("que = " + que);

		// offer : 공간이 부족하여 삽입할 수 없을 때 아무 일도 일어나지 않는다.
		que.offerFirst("offerFirst");
		System.out.println("que = " + que);

		que.offer("offer");
		System.out.println("que = " + que);

		que.offerLast("offerLast");
		System.out.println("que = " + que);


		// 확인 관련

		// get : Queue의 element와 동일.
		// 맨 앞이나 뒤의 값을 확인하고, 없을 경우 에러를 발생시킨다.

		System.out.println(que.getFirst());
		System.out.println(que.getLast());

		// peek : 맨 앞이나 뒤의 값을 확인하고, 없을 경우 null을 반환한다.

		System.out.println(que.peekFirst());
		System.out.println(que.peek());
		System.out.println(que.peekLast());


		// 삭제 관련
		
		// remove : 맨 앞이나 뒤의 값을 삭제 및 반환. 없을 시 에러 발생
		System.out.println(que.removeFirst());
		System.out.println(que.remove());
		System.out.println(que.removeLast());

		// 지정 삭제
		que.removeFirstOccurrence("addAll1"); // 맨 처음에 나오는 해당 값을 삭제. 없을 시 변경 없음
		que.removeLastOccurrence("addAll2"); // 맨 마지막에 나오는 해당 값을 삭제. 없을 시 변경 없음


		// poll : 맨 앞이나 뒤의 값을 삭제 및 반환. 없을 시 null 반환
		System.out.println(que.pollFirst());
		System.out.println(que.poll());
		System.out.println(que.pollLast());

		// 스택 관련
		que.push("push"); // Stack의 push와 동일. addFirst와 동일하게 작동
		
		que.pop(); // Stack의 pop과 동일. removeFirst와 동일하게 작동

• 앞서 말했듯, Deque는 Queue를 상속하기 때문에 관련 메서드를 모두 사용할 수 있다.
• 이외에도, 앞 뒤로 자유롭게 삽입 및 삭제가 가능하기 때문에, 관련 메서드들이 추가되었다.
• removeFirstOccurrence와 removeLastOccurrence가 추가되어, 탐색의 방향을 설정할 수 있으며 addAll로 다른 컬렉션의 값을 삽입하기 용이하다.

---

참고자료

https://docs.oracle.com/javase/8/docs/api/