스택(Stack)과 큐(Queue)

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)구조로 되어 있고, 큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)구조로 되어 있다.
스택은 동전통과 같이 아래가 막혀있고 쌓아올리면 아래 쪽은 꺼낼 수 없는 구조이고,
큐는 파이프처럼 한쪽으로는 데이터가 들어오고 한쪽으로는 데이터를 뺄 수 있는 구조라고 보면 쉽다.

예를 들어 스택에 0, 1, 2의 순서로 데이터를 넣었다면 꺼낼 때는 2, 1, 0의 순서로 꺼낸다. 즉 넣은 순서와 꺼낸 순서가 뒤집히게 되는 것이다.
이와 반대로 큐에 0, 1, 2의 순서로 데이터를 넣는다면 꺼낼 때도 0, 1, 2의 순서로 데이터가 나오는 것이다.

스택과 큐를 구현하기 위해서는 어떤 컬렉션을 사용하는 것이 좋을까? 순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합 하지만 큐 같은 경우에는 첫 번째 저장된 데이터를 항상 가져오며 삭제하므로 ArrayList는 메모리 낭비가 매우 심해 LinkedList가 적합하다.

Stack의 메서드

Queue의 메서드

Stack & Queue 예제

public class StackQueueExample {
    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으로 구현하여 제공하지만, 큐는 Queue인터페이스로만 정의해 놓았을 뿐이다. 따라서 Queue인터페이스를 구현한 클래스들이 있기에 그 중 하나를 선택해 사용하면 된다.

활용예시

우리가 쉽게 찾아볼 수 있는 스택과 큐의 활용 예는 다음과 같다

스택의 활용 예
수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
큐의 활용 예
최근 사용 문서, 인쇄작업 대기목록, 버퍼(buffer)

Stack 예제

public class StackQueueExample2 {
    public static void main(String[] args) {
        Stack st = new Stack();
        String expression = "((()))";

        System.out.println("expression:" + expression);

        try {
            for(int i = 0; i < expression.length(); i++) {
                char ch = expression.charAt(i);

                if(ch == '(') {
                    st.push(ch + "");
                } else if (ch == ')') {
                    st.pop();
                }
            }

            if (st.isEmpty()) {
                System.out.println("괄호가 일치합니다");
            } else {
                System.out.println("괄호가 일치하지 않습니다");
            }
        } catch (EmptyStackException e) {
            System.out.println("괄호가 일치하지 않습니다.");
        }
    }
}

위 코드는 괄호가 적절하게 열리고 닫혔는지 숫자를 세어 주는 코드이다. expression안의 괄호를 바꾸면 결과가 다르게 나온다.