Chapter 11. Collection Framework - 2.5 (Stack, Queue)
Stack 개념
stack은 후입선출(Last In First Out) 이다.
Queue 개념
queue는 선입선출(First In First Out) 이다.
Java에서의 Stack, Queue
우선 명명법이 다른것은 앞선 "Chapter 11. Collection Framework - 1 (컬랙션 프레임웍의 인터페이스에 대하여)"에서 말했듯이 자바의 Collection Framework가 생기기 이전부터 존재하던 인터페이스이면서 클래스이다.
그러므로 기존 소스와의 호환 및 여러 이유로 인해 그대로 이름을 유지중이다.
그리고 Collection Framework 에 맞게 내부적으로 수정이 이루어져 현재는 결국 Collection 인터페이스의 자손 클래스 혹은 인터페이스이다. 하지만 Queue와 Stack은 상속 체계가 다르다.
Queue는 Collection 인터페이스의 아들 인터페이스이고, Stack은 Vector의 아들 클래스이고, Vector는 List 인터페이스의 구현체이다.
Java에서의 Stack, Queue 구현체
자바에서는 Stack은 Stack만의 구현체를 따로 만들어 두었지만, Queue는 별도의 구현체가 없고 인터페이스만 제공한다.
그런데 LinkedList 클래스가 Queue의 자손 인터페이스인 Deque를 List 인터페이스와 함께 구현되어 있으므로 구현체로써 사용 가능하다.
- Stack의 주요 구현체
Stack
- 특징
1. 후입선출 구조이므로, 가장 마지막 저장된 데이터가 가장 먼저 나오게 된다. - Queue의 주요 구현체
LinkedList, PriorityQueue
- 특징
1. 선입선출 구조이므로, 가장 처음 저장된 데이터가 가장 먼저 나오게 된다.
- Stack 구현체의 대한 정리 -
- 주요 메서드
: boolean empty ()
: Object peek () - Stack에서 가장 마지막에 저장된 데이터를 꺼냄 (꺼내면서 삭제 하지는 않으며, 비었을땐 EmptyStackException 발생)
: Object pop () - Stack에서 가장 마지막에 저장된 데이터를 꺼내면서 사게
: Object push (Object item)
: int search (Object o)
- Queue 구현체의 대한 정리 -
LinkedList
선입선출이라는 기본적인 Queue의 기능이 구현되어 있다.
List 컬랙션 설명부분에서 이미 언급한것과 같이 내부적으로 각 요소는 Node라는 데이터 구조를 가진다.
PriorityQueue
저장순서와 상관없이 우선순위가 높은것부터 데이터를 꺼내어 온다.
null은 저장 불가하다.
내부적으로 데이터구조는 배열로 이루어져 있다.
각 요소는 heap이라는 데이터 구조를 가진다. (저장공간에서 쓰이는 heap과는 관련이 없다)
- 주요 메서드
: boolean add (Object o) - 객체를 Queue에 추가, 성공하면 true, 실패시 false 반환, 저장공간 부족시 IllegalStateException 발생
: Object remove () - queue에서 데이터를 꺼내면서 삭제 (비었을땐 NoSuchElementException 발생)
: Object element () - 삭제 없이 요소를 읽어옴. peek과 달리 queue가 비어있을때, NoSuchElementException 발생
: Object offer (Object o) - Queue에 객체를 저장, 성공하면 true, 실패 false 반환
: Object poll () - Queue에서 객체 꺼내면서 반환, 비어있을땐 null
: Object peek () - 삭제없이 요소 읽음. 비어있다면 null
Stack, Queue의 관련코드
- 코드
package ch11.practice.subPractice;
import java.util.*;
public class StackQueuePractice {
public static void main(String[] args) {
Queue queue = new LinkedList();
queue.offer("00");
queue.offer("02");
queue.offer("01");
System.out.println("===== queue test =====");
System.out.println("queue.element() : " + queue.element());
System.out.println("- queue 내용물 -");
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
System.out.println("- queue 내용물 -");
System.out.println("===== queue test =====");
System.out.println();
System.out.println("===== PriorityQueue test =====");
Queue priorityQueue = new PriorityQueue();
priorityQueue.offer(123); //오토박싱
priorityQueue.offer(54);
priorityQueue.offer(333);
priorityQueue.offer(1);
System.out.println("- PriorityQueue 내용물 -");
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll());
}
System.out.println("- PriorityQueue 내용물 -");
System.out.println("===== PriorityQueue test =====");
System.out.println();
System.out.println("===== stack test =====");
Stack stack = new Stack();
stack.push(1);
stack.push(4);
stack.push(3);
stack.push(9);
System.out.println("stack에서 9 검색 결과 : " +stack.search(9));
System.out.println("- stack 내용물 -");
while (!stack.empty()) {
System.out.println(stack.pop());
}
System.out.println("- stack 내용물 -");
System.out.println("stack에서 9 검색 결과 : " +stack.search(9));
System.out.println("stack에서 9 검색 결과 : " +stack.search(9));
System.out.println("===== stack test =====");
}
}
- 코드 결과
결과화면에서 보듯이 일반적인 queue는 선입선출의 결과이고, priorityqueue는 저장된 순서와는 상관없이 우선순위가 높은 순서대로 출력을 하였는데, 기본적으로 숫자가 작을수록 우선순위가 높다는 기준이 있기 때문이다.
그리고 PriorityQueue에 저장 가능한 타입은 물론 객체도 가능하다. (사실 위에 경우도 1,2 와 같이 리터럴 값으로 보이는 데이터들은 오토박싱이 되어 Integer객체로 들어간것이다. 하지만 Integer와 같은 숫자와 관련된 래퍼 클래스들은 모두 Number라는 추상 클래스의 자손으로써 모두 우선순위, 정렬의 기준을 가지고 있기 때문에 가능한 것이다) 그런 경우에는 저장되는 객체간의 우선순위를 정할 기준을 정해줘야 한다. (Comparator, Comparable 을 사용하면 될것같다)
추가적인 Queue의 인터페이스
- Deque
Queue의 변형으로 한쪽으로 저장, 나머지 한쪽으로는 출력(삭제) 만 가능하던 Queue를 보완한것으로
양쪽 끝에서 저장과 출력(삭제)이 가능한 구조이다.
구현체로는 ArrayDeque, LinkedList 등이 있다