9. Collections Framework : Queue, Deque

이번 포스팅에서는

 Stack과 Queue에 대해서

알아보도록 하겠습니다.

Queue 계열의 클래스들은 많이 쓰이지는 않지만

자료구조 측면에서는 반드시 알아야 하는 개념입니다.

=============================================================

 Collections Framework : Queue, Deque

1. Stack : What?

 Stack 클래스는 자료구조의 Stack과 동일합니다.

스택은 가장 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 구조입니다. 이를 Last In First Out 이라하여 LIFO 구조라고 합니다.

Stack 구조는 웹브라우저의 앞, 뒤로 가는 기능을 생각하면 좋습니다. 웹브라우저에서 브라우저를 이동할 때 스택 구조로 쌓이게 되어 특정 페이지에서 뒤로 가기 버튼을 누르면 바로 이전 페이지가 나오게 되는데 이는 브라우저가 stack 구조로 쌓이게 되기 때문입니다. 

 이러한 Stack 클래스를 자바에서는 Queue 인터페이스를 구현하여 만들었습니다.

[Stack 클래스의 메서드]

2. Queue : What?

Queue는 스택과 비슷한 동작을 합니다. 

스택과의 다른 점은 스택은 한 곳에서 입출력을 다 하는 반면에 Queue는 한쪽에서는 입력을, 다른 한쪽에서는 출력을 합니다.

가장 먼저 입력한 값이 가장 먼저 출력되므로 First In First Out의 구조입니다. 줄여서 FIFO라고 부릅니다.

이러한 Queue는 위아래로 뚫려있는 구조를 가지고 파이프와 같은 형태를 띱니다.

[Queue의 메서드]

3. Queue : PriorityQueue, Deque?

 Queue는 클래스가 아닌 인터페이스이기 때문에 Stack이 이를 구현하여 클래스로 설계되어있다 했습니다.

Queue를 구현하는 클래스는 Stack뿐만 아니라 대표적으로 PriorityQueue와 ArrayDeque가 존재합니다.

- PriorityQueue : 

 PriorityQueue의 특징은 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼내게 된다는 것입니다. 저장공간을 배열로 사용하여 각 요소를 힙이라는 자료구조의 형태로 저장합니다. 

 - ArrayDeque : 

Deque는 Queue의 업그레이드 버전이라고 볼 수 있습니다. Double-Ended Queue의 약자로 Queue는 한쪽 끝으로만 추가, 삭제 기능이 가능한 단점을 보완하여 어느 방향에서든 추가와 삭제가 가능한 형태입니다. 이러한 Deque 인터페이스를 구현하여 설계된 클래스는 ArrayDeque와 LinkedList가 있습니다.

 스택과 큐를 합쳐놓은 것과 같은 구조로 Deque를 이용하여 Stack과 Queue로 사용할 수 있습니다.

[ArrayDeque의 메서드]

4. Stack vs Queue vs Deque?

Stack	Queue	Deque
offerLast()	offer()	push()
pollLast()		pop()
pollFirst()	poll()
peekFirst()	peek()
peekLast()		peek()
	최근사용문서, 인쇄작업 대기목록, 버퍼	수식계산, 수식괄호검사, 웹브라우저의 뒤로/앞으로

5. Queue : How?

public class Source12_Queue {
    public static void main(String[] args) {
        Queue<String> que = new ArrayDeque<>();       // 들어간 순서대로 정렬해놓고 차례대로 기능하는 Queue
        // Queue<String> que = new PriorityQueue<>(); // 크기로 정렬해놓고 기능하는 Queue

        que.add("Monday");
        que.add("Monday");
        System.out.println(que.size());    // 2

        que.add("Friday");
        que.add("ThursDay");
        System.out.println(que.toString());    // [Monday, Monday, Friday, ThursDay]

        System.out.println(que.peek());       // 제일 먼저 저장한  첫 번째 요소객체 뽑아냄.   /Monday
        System.out.println(que.peek());       // Monday
        System.out.println(que.element()); // Monday  / peek과 같음

        System.out.println(que.size());       // 4

        String s = que.poll();          // 가장 앞에 있는 객체를 뽑아내고 Queue에서 제외시킴.
        System.out.println(s);          // Monday
        System.out.println(que.size());       // 한번 뽑았으므로 3
        System.out.println(que.toString());    // [Monday, Friday, ThursDay]

        que.remove("Friday");           // queue의 고유 기능이 아니라 모든 컬렉션에 있는 기능
        String s1 = que.remove();        // poll() 과 같은 기능
        System.out.println(s1);             // Monday
        System.out.println(que.size());       // 1
        System.out.println(que.toString());    // [ThursDay]

        que.offer("Sunday");            // add()와 같은 기능
        System.out.println(que.size());       // 2
        System.out.println(que.toString());    // [ThursDay, Sunday]

    }
}

public class Source13_Deque {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // 뒤쪽 마지막에 객체를 추가시키는 기능
        deque.add("조운");
        deque.offer("관우");
        deque.addLast("주유");
        deque.offerLast("태사자");

        System.out.println(deque.toString());  // [조운, 관우, 주유, 태사자]

        // 앞에서부터 밀어넣는 기능 List의 add(0)과 같은 기능, 하지만 인덱스로 제어는 불가능
        deque.addFirst("제갈량");
        deque.addFirst("하후돈");
        deque.offerFirst("사마의");
        deque.push("순욱");
        System.out.println(deque.toString());  // [순욱, 사마의, 하후돈, 제갈량, 조운, 관우, 주유, 태사자]

        // peekFirst(), peekLast(), pollFirst(), pollLast()
        System.out.println(deque.peekFirst()); // 맨 앞의 객체를 확인만하고 지우진 않음.  / 순욱
        System.out.println(deque.peek());     // peekFirst와 같음            / 순욱
        System.out.println(deque.peekLast());  // 맨 뒤의 객체를 확인만 하고 지우진 않음. / 태사자

        System.out.println(deque.pollFirst()); // 맨 앞의 객체를 확인하고 지움.   / 순욱
        System.out.println(deque.toString());  // [사마의, 하후돈, 제갈량, 조운, 관우, 주유, 태사자]

        System.out.println(deque.pollLast());  // 맨 뒤의 객체를 확인하고 지움.   / 태사자
        System.out.println(deque.toString());  // [사마의, 하후돈, 제갈량, 조운, 관우, 주유]

        System.out.println(deque.pop());      // pollFirst()랑 같음           / 사마의
        System.out.println(deque.toString());  // [하후돈, 제갈량, 조운, 관우, 주유]

        // push로 객체저장하고 pop으로 객체를 확보하면 가장 마지막에 push된 객체가 pop으로 나옴. -> Stack 특성
        // offer로 객체저장하고 poll로 객체를 확보하면 가장 첫번째에 offer된 객체가 poll로 나옴. -> Queue 특성
        // Queue에서 peekFirst, pollFirst, peekLast, pollLast로 양쪽방향으로 어느 곳이든 데이터를 제어할 수 있음 -> Deque 특성

    }
}

 사실.. Collection 부분은 코드상으로의 사용은 어렵지 않습니다. 다만 내부적으로 데이터가 어떤 특성으로 관리되는지 이해가 필요한 부분입니다.

만약 데이터 관리의 이해가 되셨다면 코드해석은 쉬울 거라 생각합니다.