Stack, Queue

Stack, Queue

https://gohighbrow.com/stacks-and-queues/

Stack은 선입후출 구조이고 Queue는 선입선출구조인다. 

순차적으로 데이터를 추가하고 삭제하는 Stack에는 ArrayList와 같은 배열기반의 컬렉션클래스가 적합하다.

Queue는 데이터를 꺼낼때 마다 첫번째가 삭제됨으로 LinkedList가 더 적합하다. ArrayList로 할경우 삭제되면서 빈공을 채우기 위해 배열의 복사가 일어남으로 메모리에 낭비가 있다. 

 

ex )

import java.util.*;

class StackQueueEx {
    public static void main(String[] args) {
        Stack st = new Stack();
        Queue q = new LinkedList();     // Queue인터페이스의 구현체인 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 : 2, 1, 0

Queue : 0, 1, 2

 

자바는 Stack의 클래스는 구현되어 있지만 Queue는 Interface로 구현