[Java] 자바에서 스택(Stack), 큐(Queue), 덱(Deque) 그리고 우선순위큐(PriorityQueue)

스택(Stack)

Stack은 LIFO(Last In First Out) 구조로 되어 있으며, 쉽게 해석하면 "후입 선출" 입니다. 즉, 마지막(최근)에 넣은 것을 먼저 뺀다는 말이다.

그렇다면 어떠한 자료구조를 통해서 스택을 다룰 수 있을까?

스택은 순차적으로 데이터를 추가하고 삭제하기 때문에 ArrayList와 같은 배열기반의 컬렉션 클래스가 적합하다.

java.util에서 Stack.class를 제공하고 있다.

 

아래는 Stack class의 관련 메소드들이다.

메서드	설명
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)

다음은 큐이다.

 Queue는 FIFO(First IN First Out) 구조로, Stack과 반대로 "선입 선출" 이다다. 즉, 먼저 넣은 것(오래된 것)을 먼저 뺀다는 말이다.

큐는 데이터를 꺼낼 때 항상 첫 번째에 저장된 데이터를 삭제하므로 ArrayList와 같은 배열기반 클래스를 사용하게 된다면,

데이터를 거낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생해 비효율적이다. 

그렇기 때문에 큐는 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

위에 보이듯이 Queue 자체는 Collection 인터페이스를 상속한 인터페이스이다.

그래서 Queue의 구현체를 찾아보면 Queue를 Deque 인터페이스가 상속하고 LinkedList가 이 Deque인터페이스를 구현하고 있으므로 Queue의 구현체는 LinkedLIst이다.

Queue queue = new LinkedList();	 // Queue인터페이스의 구현체인 LinkedList를 사용

아래에 관련 메소드들이고,

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

두 비슷한 메서드들은 문제가 발생했을 시 예외를 발생시키느냐, null 또는 false를 반환하느냐의 차이입니다.
큐에 값을 추가하는데 큐가 꽉 찼을 시 add()는 예외를 발생시키고, offer는 추가 실패를 의미하는 false를 반환하는 것이다.

---

덱(Double-ended queue - Deque)

그렇다면 아까 Queue의 구현체인 LinkedList가 구현하고 있는 Deque 인터페이스에 대해서도 알아보자.

덱은 스택과 큐를 합쳐 놓은 개념으로 Deque는 양쪽 끝에서 추가,삭제가 가능하다. 
즉, 양쪽이 뚫린 원통에 양옆으로 자유롭게 물체를 넣었다가 뺄 수 있는 구조이다.

이제 덱의 메소드들을 보자.

 

값 삽입

메서드	설명
add()	마지막에 원소 삽입 용량 초과 시 예외 발생
addFirst()	맨 앞에 원소 삽입 용량 초과 시 예외 발생
addLast()	마지막에 원소 삽입 용량 초과 시 예외 발생
offer()	마지막에 원소 삽입 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환
offerFirst()	맨 앞에 원소 삽입 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환
offerLast()	마지막에 원소 삽입 삽입 성공 시 true, 용량 제한에 걸리는 경우 false 반환

값 삭제

메서드	설명
remove()	맨앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
removeFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
removeLast()	마지막 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
poll	맨 앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 null 리턴
pollFirst()	맨 앞의 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 null 리턴
pollLast()	마지막 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 null 리턴

 

 

요소 확인

메서드	설명
getFirst()	맨 앞의 원소를 리턴 덱이 비어있는 경우 예외 발생
getLast()	마지막 원소를 리턴 덱이 비어있는 경우 예외 발생
removeLast()	마지막 원소 제거 후 해당 원소를 리턴 덱이 비어있는 경우 예외 발생
peek()	맨 앞의 원소를 리턴 덱이 비어있는 경우 null 리턴
peekFirst()	맨 앞의 원소를 리턴 덱이 비어있는 경우 null 리턴
peekLast()	마지막 원소를 리턴 덱이 비어있는 경우 null 리턴

덱 메소드에 대응하는 큐, 스택의 메소드

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
peekFirst()	peek()	-
peekLast()	-	peek()

---

우선 순위 큐 (Priority Queue)

PriorityQueue는 Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼낸다.

해당 큐는 null은 저장할 수 없으며, null을 저장할 시 NullPointerException이 발생한다.

PriorityQueue는 저장공간을 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장합니다.
힙(heap)은 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징을 가진다.

import java.util.PriorityQueue; //import

//int형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//int형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

//String형 priorityQueue 선언 (우선순위가 낮은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); 

//String형 priorityQueue 선언 (우선순위가 높은 숫자 순)
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

priorityQueue.add(1);     // priorityQueue 값 1 추가
priorityQueue.add(2);     // priorityQueue 값 2 추가
priorityQueue.offer(3);   // priorityQueue 값 3 추가

priorityQueue.poll();       // priorityQueue에 첫번째 값을 반환하고 제거 비어있다면 null
priorityQueue.remove();     // priorityQueue에 첫번째 값 제거
priorityQueue.clear();      // priorityQueue에 초기화

priorityQueue.peek();       // priorityQueue에 첫번째 값 참조 = 1

1. 값을 입력했을 때 이런 형태를 가집니다.

 

 

2. 마지막에 입력받은 4와 4의 부모인 1과의 값을 비교해 자식의 값이 부모 값보다 작다면 자리를 바꿉니다.

하지만 4는 1보다 크기때문에 변하지 않습니다.

 

3. 1의 부모인 3과 값을 비교합니다. 부모의 값 3보다 자식의 값 1이 더 작기 때문에 다음과 같이 스왑합니다.

 

 

4. 이제 2의 부모인 3과 값을 비교합니다. 부모의 값 3보다 자식의 값 2가 더 작기 때문에 스왑합니다.

 

 

 

5. 2의 부모인 1과 비교합니다. 부모의 값 1보다 자식의 값 2가 더 크기 때문에 스왑이 일어나지 않습니다.

그리고 다른 값들도 부모의 값보다 더 크기 때문에 더 이상 스왑이 일어나지 않고 [1, 2, 5, 3, 4] 의 배열을 갖게 됩니다.