자바[JAVA] - Queue와 Deque

Deque를 알기 위해선 Queue에 대한 이해가 필요하기 때문에 같이 설명

 

Queue Interface

---

 

Queue 인터페이스는 선입선출 FIFO(First In First Out)구조를 가진 자료구조다. 시간복잡도는 enqueue O(1) , dequeue O(1) 이며 활용 예시는 Cache구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있다.

 

먼저 들어온 요소가 먼저 나가는 방식으로, 메소드는 총 6가지가 존재한다.

 

요소를 추가하는 메소드는 add()와 offer(), 요소를 제거하는 메소드는 remove()와 poll() , 맨 처음 요소를 반환하는 메소드는 peek(), element()가 있다. 그리고 주로 offer(), poll(), peek()을 사용한다.

 

왜냐하면, 이들 외의 나머지 메소드는 큐가 비어있을 경우 NoSuchElementException을 내뱉기 때문이다.

 

 

1. FIFO

queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out)형식으로 데이터를 저장하는 자료구조다.

그러므로 데이터의 순서가 보장된다는 특징을 갖는다.

 

 

2. enqueue & dequeue

• queue에서 데이터를 추가하는 것을 enqueue.
• queue에서 데이터를 추출 하는 것은 dequeue.

enqueue의 경우 queue의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1) 이다. 이와 비슷하게 dequeue의 경우 맨 앞의 데이터를 삭제하면 완료 되기 때문에 동일하게 O(1)의 시간복잡도를 갖는다.

 

 

 

구현 방식 종류

• Array-Based
  • enqueue와 dequeue 과정에서 남는 메모리가 생긴다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue(원형 큐)형식으로 구현한다.
• List-Based
  • 재할당이나 메모리 낭비의 걱정을 할 필요가 없어진다.

 

Array-Base 와 List-Base의 차이점

 

Array-Base의 경우 queue는 circular queue로 구현하는 것이 일반적이다. 이는 메모리를 효율적으로 사용하기 위함이다.

또한, enqueue가 계속 발생하면 fixed size를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 한다. 그럼에도 enqueue의 시간복잡도는 (amortized)O(1)를 유지할 수 있다.

List-Base의 경우 보통 singly-lilnked list로 구현한다. enqueue는 단순히 singly-lilnked list에서 append를 하는 것으로 구현되고, 이 때 시간복잡도는 O(1)이다. dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에 이 연산도 O(1)의 시간이 걸린다.

 

요약하자면, 두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖는다.

Array-Base의 경우 전반적으로 performance가 더 좋지만, worst case의 경우에는 훨씬 더 느릴 수 있다(resize).

List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있다.

 

 

 

Queue Interface와 LinkedList Class

JAVA에서 흔히 Queue를 생성할 때는 다음과 같이 생성한다.

Queue<Integer> queue = new LinkedList<>();

위 그림에서 보이듯이 LinkedList가 Queue 인터페이스를 상속받았기 때문이며, 결국 Queue는 자식 클래스인 LinkedList를 이용하여 구채화된다.

 

그렇다면, 여기서 의문이 하나 생길 수 있다. 왜 ArrayList가 아닌 LinkedList일까?

 

그것은 LinkedList에서 추가, 삭제 시간복잡도가 O(1)이기 때문이다.  O(N)이 아니고? 물론, 일반적인 상황에서 LinkedList는 추가나 삭제할 데이터를 탐색하는 시간까지 합쳐서 O(N)이 맞지만, 위치를 알고 있을 경우 O(1)이다.

 

Queue의 동작 방식은 요소를 추가할 때 맨 뒤에 요소를 추가하고, 삭제할 때 맨 앞의 요소를 제거하므로 연산에서 시간복잡도는 O(1)이 되는 것이다. 맨 앞의 요소를 반환하는 경우도 마찬가지다.

 

ArrayList도 맨 뒤에 요소를 추가하는 것은 O(1)이지만, 삭제하는 과정은 맨 앞의 요소를 삭제하는 것이므로 그 뒤에 있는 요소를 싹다 한 칸씩 왼쪽으로 밀어야하므로 O(N)이 된다.

 

이러한 이유로 Queue는 LinkedList를 이용하여 생성한다.

 

흥미로운 점은 여기서 Queue는 LinkedList와 다름없어서 LinkedList에 있는 contains()나 stream() 메소드도 호출하여 사용할 수는 있다.

 

 

 

확장 & 활용

queue의 개념에서 조금 확장한 자료구조들로는 양쪽에서 enqueue와 dequeue가 가능한 deque(double-ended queue)와 시간순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 priority queue가 있다.

활용 예시로는 하나의 자원을 공유하는 프린터나, CPU task scheduling, Cache구현, 너비우선탐색(BFS) 등이 있다.

 

 

번외) Queue 두 개를 이용하여 Stack을 구현해 보세요

---

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠다. 두 개의 queue로 stack을 구현하는 방법은 다음과 같다.

1. push() :: q1으로 enqueue()를 하여 데이터를 저장한다.
2. pop() ::
   1. q1에 저장된 데이터의 갯수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue()한다.
      결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
   2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.(LIFO)
   3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap한다.

시간복잡도

• push() : q1.enqueue()를 한번만 하면 되기 때문에 O(1)의 시간복잡도를 갖는다.
• pop() : q1에 저장되어 있는 n개의 원소중에 n-1개를 q2로 옮겨야 하므로 O(n)이 된다.

import java.util.LinkedList;
import java.util.Queue;

class Squeue{
    Queue<Integer> q1;
    Queue<Integer> q2;

    public Squeue(){
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int data){
        q1.offer(data);
    }

    public int pop(){
        int result = -1;

        while(q1.size() > 1){
            q2.offer(q1.poll());
        }

        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return q2.poll();
    }
}
public class Sq {

    public static void main(String[] args) {
        Squeue stack = new Squeue();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

 

 

PriorityQueue Class

---

흔히 우선순위 큐라고 불리는 클래스다. Queue 인터페이스를 상속받았으며, 일반적인 Queue와는 다른 특징을 가진다. 우선순위 큐는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 요소가 먼저 나가는 자료구조다.

 

우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이며, 요소를 삽입할 때 우선순위를 기준으로 최대 힙 혹은 최소 힙을 구성한다. 그리고 요소를 꺼낼 때 루트 노드를 얻어낸 뒤, 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다.

 

메소드는 Queue에서 정의한 6가지 메소드를 모두 사용할 수 있고, Collection 인터페이스도 상속을 받았으므로 그 안의 메소드도 활용이 가능하다. 그래도, 일반적으로는 offer(), poll(), peek(), isEmpty() 정도만 쓰는 편이다.

 

그렇다면, 이 우선순위를 어떻게 정할까? 만약, 우선순위 큐에 들어갈 요소가 Integer, Double, String, Character와 같은 경우, 따로 Comparator을 설정하지 않으면 정렬 기준이 오름차순이 된다.

 

하지만, Car와 Bus와 같이 개발자가 따로 만들어 둔 객체를 우선순위 큐에 바로 넣으면 정렬 기준이 없어서 .ClassCastException이 발생한다. 따라서, 해당 객체 안에 Comparable을 상속받아서 compareTo를 정의해 주거나, 정렬 기준을 Comparator을 사용하여 정해줘야한다.

 

단, 우선순위 큐는 null 요소는 저장이 불가능하다.

 

 

 

 

Deque Class

---

Deque란 Double-Ended Queue의 줄임말로 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조를 의미한다.

java.util 패키지에 소속되어 있고 Null요소는 사용을 하지 못 한다.

사용하기에 따라서 Stack으로 사용될 때는 Stack보다 빠를 수 있고 대기열에서 사용될 때는 LinkedList보다 빠를 수도 있다.

 

특히 한쪽으로만 입력 가능하도록 설정한 덱을 스크롤(scroll)이라고 하며, 한쪽으로만 출력 가능하도록 설정한 덱을 셸프(shelf)라고 한다. 

 

기본적으로 Queue를 상속받고 있으나 Deque만 가지고 있는 일부 메소드가 있다.

 

앞서 말했듯이, 양쪽이 뚫려있는 구조라서 앞에 요소를 추가할 수도 있고, 뒤에 요소를 삭제하는 등 추가와 삭제가 Queue에 비해 비교적 자유롭다.

 

 

Deque는 Queue의 메소드를 모두 가지고 있다. 위 사진은 Queue 메소드와 Deque에서 새롭게 정의한 메소드를 비교하고 있다. Queue의 add(e)와 Deque의 addLast(e)는 같다고 말하고 있다.

 

 

 

 

Deque는 Stack의 메소드도 모두 가지고 있다. 위 사진은 Stack 메소드와 Deque에서 새롭게 정의한 메소드를 비교하고 있다. Stack의 push(e)와 Deque의 addFirst(e)는 같다고 말하고 있다.

 

참고로, 각각의 메소드의 시간복잡도는 모두 O(1)이다. (위치를 알고 있으므로)

 

Deque의 구현 클래스는 ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList이 있는데, 주로 ArrayDeque를 사용하는 편이다.

 

 

 

 

ArrayDeque Class

---

ArrayDeque 클래스는 Deque 인터페이스를 상속받아서 사용하는 구현 클래스다.

 

• ArrayDeque는 사이즈 제한이 없는 가변 배열이다
  • 단, 처음부터 사이즈가 무한대인 것은 아니고 초기 사이즈 16에서 2배씩 늘려나간다
• null 요소는 저장할 수 없다
• 또한, 비동기 방식이라서 멀티 쓰레드 환경에서는 어울리지 않다
• 마지막으로, ArrayDeque는 Stack 목적으로 구현하였을 때 기존의 Stack보다 빠르고, Queue 목적으로 구현하였을 때 LinkedList보다 빠르다.

 

Stack은 대부분의 메소드에 동기화 처리가 되어있는 Vector를 상속하므로 Stack을 사용하는 것보다 ArrayDeque를 통해 Stack을 사용하는 편이 더 성능이 좋다.

 

 

그렇다면, Queue를 목적으로 ArrayDeque를 사용하면 왜 기존 구현 클래스인 LinkedList보다 빠를까?

 

먼저, LinkedList로 구현한 Queue의 경우, 맨 마지막 요소를 추가할 때 새로운 노드를 만들고 이전 노드와 새로운 노드의 주소를 가리키는 등 여러 가지 연결 작업이 필요하다.

 

하지만, ArrayDeque로 구현한 Queue의 경우, 단순히 arr[tail] = e와 같이 마지막 인덱스에 해당하는 값에 요소를 할당해 주면 된다. 그리고 사이즈가 꽉찼다면, 2배로 늘리면 되는 것이다.

 

단, 항상 ArrayDeque가 바람직한 것은 아니다. 만약, 저장해야할 데이터의 양이 방대하다면 ArrayDeque의 사이즈를 계속 2배씩 늘려야하므로 이때는 LinkedList가 더 낫다. 하지만, 일반적인 경우 Queue를 목적으로 ArrayDeque를 사용할 때가 성능이 더 좋다.

 

 

 

ArrayDeque의 시간복잡도

ArrayList의 경우, remove(0)을 할 때 탐색으로 인해 시간복잡도가 O(N)이라고 설명한 적이 있다. 그런데, ArrayDeque도 어쨌든 가변 배열인데, removeFirst()가 어떻게 시간복잡도가 O(1)인지 궁금증이 생겼다. 구글링을 해 보니, ArrayDeque는 원형 큐 방식으로 구현이 되어있었기 때문에 시간복잡도가 O(1)인 것을 알게 되었다. 자세한 구현 과정은 이곳을 참고하시길 바랍니다.

 

 

 

Deque 사용

---

Deque<String> linkedList = new LinkedList<>();
Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new ConcurrentLinkedDeque<>();

자바에서의 덱은 인터페이스로 구현되어 있다. 덱 자료구조의 여러 연산들을 정의한 Deque 인터페이스가 있고 이를 구현한 ArrayDeque, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등의 클래스가 있다. 

 

 

 

 

 

Deque 값 추가

용량 초과 시 예외 발생

• addFirst()
  맨 앞에 원소 삽입
• add()
  마지막에 원소 삽입
  
• addLast()
  마지막에 원소 삽입

 

삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

• offerFirst()
  맨 앞에 원소 삽입
• offer()
  마지막에 원소 삽입
• offerLast()
  마지막에 원소 삽입
  
  

 

 

 

Deque 값 삭제

 

 

덱이 비어있는 경우 예외 발생

• remove()
  맨 앞의 원소 제거 후 해당 원소를 리턴
  
• removeFirst()
  맨 앞의 원소 제거 후 해당 원소를 리턴
  
• removeLast()
  마지막 원소 제거 후 해당 원소를 리턴
  
  

덱이 비어있는 경우 null 리턴

• poll
  맨 앞의 원소 제거 후 해당 원소를 리턴
  
• pollFirst()
  맨 앞의 원소 제거 후 해당 원소를 리턴
  
• pollLast()
  마지막 원소 제거 후 해당 원소를 리턴
  

 

 

Deque 원소 확인

 

덱이 비어있는 경우 예외 발생

• getFirst()
  맨 앞의 원소를 리턴
  
  
• getLast()
  마지막 원소를 리턴
  
  

덱이 비어있는 경우 null 리턴

• peek()
  맨 앞의 원소를 리턴
  
  
• peekFirst()
  맨 앞의 원소를 리턴
  
  
• peekLast()
  마지막 원소를 리턴
  
  

---

 

 기타

• removeFirstOccurrence(x)
  덱의 맨 앞부터 탐색하여 x와 동일한 첫 원소를 제거
  동일한 원소가 없을 시 덱이 변경되지 않음 
  
• removeLastOccurrence(x)
  덱의 마지막부터 탐색하여 x와 동일한 첫 원소를 제거
  동일한 원소가 없을 시 덱이 변경되지 않음 
  
  
• element() == removeFirst()
  
  
• addFirst() == push()
  
  
• removeFirst() == pop()
  
  
• remove(x)
  removeFirstOccurrence(x)와 동일
  
  
• contains(x)
  덱에 x와 동일한 원소가 있는지 true 혹은 false 반환
  
  
• size()
  덱의 원소 개수 리턴
  
  
• iterator()
  덱의 반복자(iterator) 반환
  
  
• isEmpty()
  덱이 비어있는지 true 혹은 false 반환

 

Deque 순회 방법

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuffer sb = new StringBuffer();
        Deque<Integer> deque = new LinkedList<>();

        deque.add(3);
        deque.add(7);
        deque.add(5);

        for (int de : deque) {
            System.out.print(de + " ");
        }

        System.out.println();

        for (Iterator<Integer> it = deque.iterator(); it.hasNext();) {
            System.out.print(it.next() + " ");
        }

        System.out.println();

        Iterator<Integer> it = deque.iterator();
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }
    }
}