[Java] 컬렉션 프레임워크 - Stack과 Queue

자바에서 제공하는 Stack과 Queue에 대해서 알아보기 이전에 스택(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와 같은 배열 기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

다음은 Stack의 메서드들이다.

메서드	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위에 저장된 객체를 반환, pop()과 달리 Stack에서 객체를 꺼내지는 않음.(비었을 때는 EmptyStackException 발생)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. (비었을 때는 EmptyStackException 발생)
Object push(Object item)	Stack에 객체(item)을 저장한다.
int search(Object o)	Stack에서 주어진 객체(o)를 찾아서 그 위치를 반환, 못찾으면 -1을 반환(배열과 달리 위치는 0이아닌 1부터 시작)

 

다음은 Queue의 메서드들이다.

메서드	설명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true를 반환, 저장공간이 부족하면 IllegalStateException 발생.
Object remove()	Queue에서 객체를 꺼내 반환, 비어있으면 NoSuchElementException 발생
Object element()	삭제없이 요소를 읽어온다. peek와 달리 Queue가 비었을 때 NoSuchElementException 발생
boolean offer(Object o)	Queue에 객체를 저장, 성공하면 true, 실패하면 false를 반환
Object poll()	Queue에서 객체를 꺼내서 반환, 비어있으면 null을 반환
Object peek()	삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환

 

// 스택, 큐 예제
import java.util.*;

class StackQueueEx {
    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 인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue 인터페이스를 구현한 클래스들이 있어서 이 들 중 하나를 선택해서 사용하면 된다.