[Java]컬렉션 프레임웍 (3) - Stack & Queue

스택과 큐 (Stack & Queue)

▶ 스택(Stack) : LIFO구조. 마지막에 저장된 것을 제일 먼저 꺼내게 된다.

스택은 밑이 막힌 상자이다. 상자에 0, 1, 2를 순서대로 넣게 되면 꺼낼 때는 마지막에 넣었던 2, 1, 0 순서로 꺼내게 된다.

이러한 구조를 LIFO(Last In First Out)구조라고 한다.

스택의 특징은 저장한 순서와 추출하는 순서가 반대인것이 특징이다.

스택에서는 저장을 push, 추출은 pop 이라고 한다.

 

▶ 큐(Queue) : FIFO구조. 제일 먼저 저장한 것을 제일 먼저 꺼내게 된다.

큐는 양끝이 뜷린 상자이다. 상자에 0, 1, 2를 순서대로 넣고, 꺼낼 때도 0, 1, 2 순서대로 꺼내게 된다.

이러한 구조를 FIFO(First In First Out) 구조라고 한다.

큐의 특징은 저장한 순서와 추출하는 순서가 일치하는 것이 특징이다.

큐에서는 저장을 offer, 추출을 poll이라고 한다.

 

그럼 스택과 큐를 배열과 링크드 리스트로 구현을 한다면 어떤 걸 멀로 구현하면 좋을까.

물론 배열이나 링크드 리스트 둘 다 구현은 가능하다.

효율을 따졌을 때 스택의 LIFO구조는 배열로 구현하기 좋다.

배열의 순차적 추가와 순차적 삭제 방식은 스택의 LIFO구조를 구현하기 좋다.

반대로 큐의 FIFO구조는 링크드 리스트로 구현하기 좋다.

링크드 리스트는 앞에서부터 삭제를 하더라도 참조 변수만 변경하면 되기 때문에 큐를 구현하기 좋다.

 

---

스택과 큐의 메서드

스택은 클래스이다.

스택을 사용할 때는 객체를 생성해주기만 하면 된다.

▶ Stack st = new Stack();

하지만 큐는 인터페이스이다.

그래서 객체를 바로 생성할 수 없다.

그렇기에 방법은 두 가지가 있다. Queue를 직접 구현하는 방법과 Queue를 구현한 클래스를 사용하는 방법이다.

Queue를 사용하기에는 큐를 구현한 클래스를 사용하는 것이 편하다.

그렇게 Java API의 Queue를 살펴보면 다음과 같다.

Java API문서에서 찾은 Queue

API문서에서 Queue를 구현한 클래스를 보니 LinkedList가 있는 걸 확인할 수 있다.

Queue g = new LinkedList();

큐를 사용할 때는 이렇게 객체를 생성하면 된다.

물론 참조 변수를 Queue가 아닌 LinkedList를 사용해도 무관하지만,

Queue를 사용하면 Queue인터페이스를 구현하는 어떤 클래스로든 변경이 가능하다.

 

Stack의 메서드

Queue의 메서드

 

스택의 활용 예 - 수식계산, 수식 괄호 검사, 워드프로세서의 undo/redo,
                          웹브라우저의 뒤로/앞으로

큐의 활용 예 - 최근 사용 문서, 인쇄 작업 대기목록, 버퍼(buffer)