Stack, Queue (Priority Queue와 deque 포함)

스택은 마지막에 저장한 데이터를 가장 먼저 꺼낼 수 있는 LIFO 방식이다.

LIFO (Last In First Out)

 

큐는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO 방식이다.

FIFO (First In First Out)

 

사진 : Java의 정석 (남궁성 지음)

 

예를 들어 데이터 0, 1, 2를 넣었다면 스택으로 꺼낼 때에는 2, 1, 0 순으로 꺼내게 되고 큐로 꺼낼 때에는 0, 1, 2 순서로 꺼내게 된다.

 

 

Stack과 Queue의 데이터 저장, 뽑기 예제

public class Main {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();

        st.push("0");
        st.push("1");
        st.push("2");

        q.offer("0");
        q.offer("1");
        q.offer("2");

        System.out.println("Stack");
        while(!st.empty()) {
            System.out.println(st.pop());
        }

        System.out.println("Queue");
        while(!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
}

Stack과 Queue 데이터 꺼내기

 

 

Stack, Queue의 실사용

Stack은 대표적으로 웹 브라우저의 뒤로/앞으로 가기 버튼에 사용된다.

Queue는 대표적으로 최근 사용문서 기록에 사용된다.

 

네이버 -> 구글 -> 다음 순으로 접근했다가 뒤로가기를 누르면 구글로 접근하게 된다. 이러한 방식은 Stack을 사용한 대표적인 활용 예시라고 볼 수 있다.

 

 

 

PriorityQue

Queue의 인터페이스의 구현체 중 하나인데 저장한 순서에 따라 출력되는 것이 아니라 우선순위가 따로 있고, 그 우선순위에 따라서 데이터를 찾아오는 자료구조이다.

public class Main {
    public static void main(String[] args) {
        Queue pq = new PriorityQueue();
        pq.offer(3);
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        System.out.println(pq);

        Object obj = null;

        while((obj = pq.poll()) != null) {
            System.out.println(obj);
        }
    }
}

우선순위는 숫자가 작을 수록 우선순위가 높기 때문에 1, 2, 3, 4, 5 순으로 하나씩 출력된 것을 확인할 수 있다.

숫자 뿐 아니라 객체를 저장할 수도 있는데 이럴 경우에는 크기를 비교할 수 있는 방법을 제공해야만 한다.

 

 

 

Deque

Queue의 변형으로 양 쪽에 추가/삭제가 가능하여 stack과 que를 하나로 합쳐놓은 것과 같다.

Deque의 조상은 Queue이며, ArrayList와 LinkedList로 구현한다.

사진 : Java의 정석 (남궁성 지음)

 

사진 : Java의 정석 (남궁성 지음)