컬렉션 List - Stack & Queue

자료구조 중에서 스택(Stack)과 큐(Queue)라는 것이 있다.

 

흔히 스택은 브라우저의 앞으로 가기, 뒤로 가기 같은 기능을 구현하는데 사용할 수 있는 자료구조다.

 

큐는 최근 사용 문서, 인쇄작업 대기 목록 등을 구현하는데 사용할 수 있는 자료구조다.

Stack(스택)

 

스택(Stack)은 마지막에 저장한 데이터를 가장 먼저 꺼내는 선입후출 (LIFO, Last In First Out) 자료구조다.

 

 

 

위에서 이야기했듯이 흔히 브라우저의 앞으로 가기, 뒤로 가기 기능 등을 구현하는데 사용되는 구조다.

 

그렇다면 Stack을 List로 구현하려면 ArrayList와 LinkedList 중 어떤 것이 더 적합할까?

 

바로 ArrayList다.

 

컬렉션 List - ArrayList

 

이전 ArrayList 포스트에서 이야기했듯이 ArrayList는 데이터를 입력하면 순차적으로 쌓이는 구조다.

 

반대로 데이터를 추출할 때는 맨 뒤에서부터 역순으로 데이터를 추출할 때 유리하다.

 

(ArrayList는 중간부터 데이터 삭제가 가능하지만, 이럴 경우 Linked에 비해 자원이 더 낭비된다.)

 

즉 Stack과 딱 맞아떨어지는 구조다.

 

그럼 Stack 자료 구조를 사용하려면 Java에서 ArrayList를 이용해 구현해야할까?

 

당연히 아니다.

 

Java에서는 Stack 자료구조를 간편하게 사용할 수 있도록 Stack 클래스를 제공한다.

 

 

public static void main(String[] args) {

        Stack stack_test = new Stack();

        stack_test.push(1); // stack에 1 저장
        stack_test.push(2); // stack에 2 저장
        stack_test.push(3); // stack에 3 저장

        System.out.println(stack_test); // [1,2,3] 출력됨

        stack_test.pop(); // stack에서 가장 끝 요소 추출

        System.out.println(stack_test); // [1,2] 출력됨

        stack_test.pop(); // stack에서 가장 끝 요소 추출

        System.out.println(stack_test); // [1] 출력됨

    }

 

굳이 ArrayList를 사용해서 구현할 수 있지만, Stack을 이용하는 것이 훨씬 편리하게 사용할 수 있다.

Queue(큐)

 

큐(Queue)는 처음 저장한데이터를 가장 먼저 꺼내게 되는 선입선출 (FIFO, First In First Out) 자료구조다.

 

위에서 이야기했듯 Queue는 최근 사용 문서, 인쇄작업 대기목록 등을 구현하는데 사용된다.

 

그렇다면 스택과 달리 Queue는 ArrayList, LinkedList 중 어떤 것으로 구현하는게 더 효율적일까?

 

바로 LinkedList다.

 

Array는 순차적으로 데이터를 쌓고 맨 뒤에서부터 역순으로 추출하는게 Stack에 유리하다.

 

하지만 Queue는 맨 처음 입력된 데이터가 삭제되어야 하므로 LinkedList가 훨씬 유리하다고 볼 수 있다.

 

그렇다면 Queue의 자료 구조를 사용하려면 어떻게 해야할까?

 

아쉽게도 Queue는 인터페이스만 구현되있고, Stack과 달리 자바에서 제공하는 클래스가 없다.

 

대신 Queue인터페이스를 구현해놓은 클래스가 있어서 이 클래스들 중 선택해서 사용하면 된다.

 

LinkedList도 그 중 하나다.

 

 

public static void main(String[] args) {

        Queue q_test = new LinkedList();

        q_test.offer(1); // Queue에 숫자 1 저장
        q_test.offer(2); // Queue에 숫자 2 저장
        q_test.offer(3); // Queue에 숫자 3 저장

        System.out.println(q_test); // [1,2,3] 출력

        q_test.poll(); // Queue에서 가장 첫번째 요소 추출

        System.out.println(q_test); // [2,3] 출력

        q_test.poll(); // Queue에서 가장 첫번째 요소 추출

        System.out.println(q_test);  // [3] 출력

    }

 

위 코드를 보면 알겠지만 Queue 자료형으로도 LinkedList를 사용할 수 있고

 

LinkedList에도 offer(), poll()처럼 Queue를 위한 메서드도 다 준비되어있다.

 

즉 Queue를 간단하게 사용하고 싶다면 LinkedList를 사용하면 된다.

PriorityQueue

PriorityQueue는 Queue 인터페이스의 구현체 중 하나다.

 

하지만 Queue와는 동작하는 방식이 다르다.

 

PriorityQueue는 저장 순서 관계없이 우선순위가 높은 것부터 리스트에서 추출한다.

 

PriorityQueue는 저장 공간으로 배열을 사용하며,

 

각 요소를 이진 트리를 기반으로 한 힙(heap)이라는 자료 구조 형태로 저장한다.

 

코드를 보면 더 알기 쉬울 것이다.

 

 

public static void main(String[] args) {

        Queue pq = new PriorityQueue();

        pq.offer(3); // PriorityQueue에 숫자 3 저장
        pq.offer(2); // PriorityQueue에 숫자 2 저장
        pq.offer(1); // PriorityQueue에 숫자 1 저장
        pq.offer(5); // PriorityQueue에 숫자 5 저장
        pq.offer(4); // PriorityQueue에 숫자 4 저장

        System.out.println(pq); // [1,3,2,5,4] 추출

        System.out.println(pq.poll()); // 숫자 1 추출
        System.out.println(pq.poll()); // 숫자 2 추출
        System.out.println(pq.poll()); // 숫자 3 추출
        System.out.println(pq.poll()); // 숫자 4 추출
        System.out.println(pq.poll()); // 숫자 5 추출

    }

 

코드에서 볼 수 있듯이 PriorityQueue는 입력 순서와 달리 추출 순서가 다르다.

 

우선 순위에 따라 1,2,3,4,5 순서대로 출력되는 것을 볼 수 있다.

 

다만 코드를 볼 때 알겠지만 Queue 리스트 안에서 바로 정렬되는 것이 아니다.

 

추출시 Queue 리스트에 저장된 요소 중 가장 작은 수를 추출하는 것이다.

 

Deque(Doublc-Ended Queue)

 

Deque는 일반적인 Queue가 한방향으로 자료를 저장하고 추출하는데 비해 양방향 입출력이 가능하다.

 

기존 Queue가 선입선출(LIFO)라면 Deque는 어느방향이든 자료의 저장 추출이 가능하다.

 

위 그림은 이해를 위해 데이터 입력, 추출을 순서대로 되는지 그렸는데 이해가 안되면 아래 그림을 보자.

 

 

 

데이터를 앞이든 뒤든 마음대로 저장, 출추출이 가능하다.

 

 

 

public static void main(String[] args) {

        Deque dq = new LinkedList();

        dq.offerLast(2); // Deque 끝에 숫자 2저장

        System.out.println(dq); // [2] 출력

        dq.offerLast(3); // Deque 끝에 숫자 3저장

        System.out.println(dq); // [2,3]  출력

        dq.offerFirst(1); // Deque 처음에 숫자 1저장

        System.out.println(dq); // [1,2,3]  출력

        dq.pollLast(); // Deque 마지막 숫자 추출

        System.out.println(dq); // [1,2] 출력

        dq.pollFirst(); // Deque 첫 숫자 추출

        System.out.println(dq); // [2] 출력

        dq.pollFirst(); // Deque 첫 숫자 추출

        System.out.println(dq); // [] 출력

    }

 

코드를 보면 알겠지만 Deque도 LinkedList 클래스를 이용해서 구현할 수 있다.

 

offerFirst(), offerLast(), pollFirst(), pollFirst() 4개의 메서드를 이용하면 된다.