자료구조 Stack 과 Queue
자바에서 구현한 스택과 큐를 설명하기 전에 자료구조 스택과 큐를 먼저 알아보자. Stack(스택) 은 나중에 입력한 값이 가장 먼저 출력되는 LIFO(Last-In First-Out) 구조이다. 그림으로 본다면 다음과 같다.
0 > 1 > 2 > 3 의 순서로 입력하면 3 > 2 > 1 > 0 의 순서로 출력된다.
Queue(큐) 는 먼저 입력한 값이 가장 먼저 출력되는 FIFO(First-In First-Out) 구조이다. 그림으로 본다면 다음과 같다.
0 > 1 > 2 > 3 의 순서로 입력하면 0 > 1 > 2 > 3 의 순서로 출력된다.
Stack
자바에서 스택을 사용하기 위해 구현한 클래스는 Stack 이며 JDK 1.0 버전부터 있었다. Vector 클래스를 상속받은 클래스이므로 다중 상속을 지원하지 않는다.
Stack 클래스는 스택구조(LIFO)를 구현하기 위한 편리한 API 들을 제공하지만 단점이 존재한다.
다음은 JDK11 의 Stack 클래스 코드의 선언부만 가져온 것이다.
package java.util;
public
class Stack<E> extends Vector<E> {
public Stack() {
}
public E push(E item) {
}
public synchronized E pop() {
}
public synchronized E peek() {
}
public boolean empty() {
}
public synchronized int search(Object o) {
}
}코드를 보면 pop(), peek(), search() 가 synchronized 로 선언되어 있는 것을 볼 수 있다. 멀티스레드 환경에서 여러 사용자가 Stack 에 접근하면 안전하지 않을 수 있다. 안정성을 보장하기 위해 스택에 접근할 때 synchronized 로 선언하여 접근하는 사용자가 있으면 접근하지 못하도록 막았다. 안정성은 높였지만 스택에 접근할 때마다 동기화를 시켜 프로그램의 속도가 느려질 수 있다.
JDK 공식문서에서도 다음과 같이 스택을 구현할 때 클래스 Stack 을 사용하는 것이 아닌 Deque 인터페이스를 활용하는 것을 권장한다.
A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:
Deque<Integer> stack = new ArrayDeque<Integer>();Queue
스택이 JDK1.0 에 추가되고 이후 JDK1.2 버전에 Collection 이 추가되었으며 Queue 는 JDK 1.5 버전에서 Collection 을 구현한 인터페이스로 추가되었다.
Queue 인터페이스도 Stack 과 마찬가지로 큐를 구현하기 위한 API 를 제공한다.
PriorityQueue
Queue 인터페이스 구현체 중 PriorityQueue 는 값이 저장된 순서와는 관계없이 정해진 우선순위대로 출력된다. 우선순위는 compare 로 정의한 순서대로 정렬된다. compare 을 오버라이딩 하지 않았다면 기본적으로 오름차순으로 정렬된다.
Deque
Deque 는 Queue 의 변형으로 한 방향에서만 입출력이 가능했던 Queue 와 달리 양쪽에서 입력 및 출력이 가능하다. 그림으로 나타내면 다음과 같다.
자바에서 Deque 도 Queue 와 마찬가지로 인터페이스이며 JDK 1.6버전에 추가되었다. Deque 를 표현하기 위해서 구현체를 사용해야 한다.
ArrayDeque
ArrayDeque 는 생성할 때 사이즈를 지정할 수 있으며 지정한 사이즈를 넘어가면 내부에서 사이즈를 키운다. null 을 저장할 수 없으며 양 끝쪽의 값을 추가 및 제거에 효과적이다.
LinkedList
LinkedList 는 null 을 저장할 수 있으며 중간 값을 추가 및 제거에 효과적이다. ArrayDeque 보다 메모리를 더 많이 소모한다.
