[Java/Collection] Stack과 Queue(feat. Priority Queue, Deque)

최지수·2022년 4월 29일

Deque Java collection framework priority queue queue stack

Java

목록 보기

21/27

Collection Framework
데이터 군을 저장하는 클래스들을 표준화한 설계를 의미해요. 다수의 데이터 그룹들을 관리하는 표준화된 프로그래밍 방식을 말해요.

자바에선 다수의 데이터를 다루는데 필요한 다양하고 풍부한 클래스들을 제공하며, 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 재사용성이 높은 코드를 제공해요.

사용법에 앞서, Stack과 Queue에 대해 알아봐요

스택Stack은 LIFOLast-in First-out이라 하여, 마지막에 넣은 데이터를 추출하는 자료구조에요. 그리고 큐는 FIFOFirst-in First-out이라 하여 처음에 저장한 데이터를 가장 먼저 꺼내는 자료구조에요.

여기서 스택에서 데이터를 추가하는 것을 push, 꺼내는 것을 pop이라고 해요. 큐는 추가를 offer, poll이라고 불려요.

예를 들면 [0,1,2] 순으로 넣으면 스택의 경우 2 $\to$ 1 $\to$ 0 순으로 반환하고, 큐의 경우 0 $\to$ 1 $\to$ 2 순으로 반환해요.

스택과 큐를 구현하기 위한 효율적인 자료구조는, 스택은 ArrayList 같은 배열 기반 그리고 큐는 LinkedList, 링크드 리스트에요. 큐의 경우 가장 앞에 있는 것을 추출하기 때문에 이를 배열로 구현하면 데이터를 빼내고 새로운 배열을 생성해서 복사를 해야하기 때문에 추가/삭제가 쉬운 링크드 리스트를 사용해요.

자바에서의 Stack

자바에서 Stack은 JDK 11 기준으로 Vector를 상속해요. 여담으로 한번 적어봤어요.

push & (pop vs. peek)

push는 스택에 데이터를 추가해요. 그리고 pop은 맨 위의 데이터를 '추출'하고 스택에서 지워줘요. pop을 실행할 때 스택 안에 데이터가 없으면 EmptyStackException을 날려주니 pop을 수행하기 전에 isEmpty를 통해 데이터가 남아 있는지 확인해야 해요.

peek도 마찬가지로 맨 위에 데이터를 추출하지만, 스택에서 지워지진 않아요.

Stack<Integer> stack = new Stack();	
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

// peek은 스택에 남겨두기 때문에 이건 무한루프가 돌아요
//	while(!stack.empty()){
//		System.out.println(stack.peek());
// 	}

while(!stack.isEmpty()){
	System.out.println(stack.pop());
}

search

스택 안에 해당 요소가 몇 번째 인덱스에 있는지 찾아줘요. 못찾으면 -1을 반환해요. 내부 소스 코드를 lastIndexOf를 사용해요. 이말은 맨 끝을 기준으로 데이터를 찾는다는 의미죠. 따라서 가장 뒤를 0으로 기준잡아서 반환한다는 사실을 아실 수 있어요.

Stack<Integer> stack = new Stack();	
stack.push(1);
stack.push(1);
stack.push(1);
System.out.println(stack.search(1)); // 0 반환!
System.out.println(stack.search(2)); // -1 반환!

자바에서의 Queue

add vs. offer

둘 다 큐에 데이터를 추가하는 것은 같아요. 다만 add의 경우 저장공간이 부족하면 IllegealStateException을 날리는 반면, offer는 false만 반환해요.

Queue는 인터페이스에요. 그래서 실제로 구현체는 LinkedList를 선언해줘야 해요.

// Queue는 인터페이스에요. 따라서 구현체인 LinkedList로 선언해야 해요.
Queue<Integer> queue = new LinkedList();
queue.add(1);		// 둘이 같아요
queue.offer(2);		// 둘이 같아요
queue.add(3);
queue.offer(4);

peek vs. poll

스택과 마찬가지로 peek은 데이터를 보존한채로 가장 처음에 들어간 데이터를 반환해요. 그리고 poll은 pop처럼 데이터를 빼낸 다음에 반환해요.

여기서 스택과 조금 차이가 있는데, 데이터를 꺼내는 poll이나 peek은 데이터가 존재하지 않으면 null을 반환해요.

그리고 이랑 비슷한 메서드인 remove와 element가 존재하는데 각각 poll과 peek이랑 같은 기능이긴 하나, 둘 다 NoSuchElementException을 발생시키는 차이가 있어요.


// peek은 큐에 남겨두기 때문에 이렇게 쓰면 안되요!
//	while(!queue.empty()){
//		System.out.println(queue.peek());
// 	}

// 이렇게 쓰셔야 해요!
while(!queue.isEmpty()){
	System.out.println(queue.poll());
}

// 이 상태에서 remove와 element를 쓰면 예외가 발생해요!
// queue.remove();
// queue.element();

두 자료구조의 사례

스택의 사용 예
1. 수식 계산(후위 연산)
2. 수식 괄호 검사
3. Undo/Redo

큐의 사용 예
1. 최근 사용 문서
2. 인쇄 작업 대기 목록
3. 버퍼buffer

우선순위 큐(Priority Queue)

큐의 구현체중 하나에요. 이 자료구조는 기존과 달리 특별하게 동작해요. 힙 트리를 활용해 데이터를 추가하자마자 정렬해서 이후 데이터를 추출할 때 우선순위가 높은 것부터 꺼내요. 예를 들면 우선순위를 오름차순으로 지정한다면, [3,2,1,4,5] 순으로 넣었을 때 [1,2,3,4,5] 순으로 데이터를 꺼내올 수 있어요.

// 구현체만 PriorityQueue로 설정해주면 알아서 되요!
Queue<Integer> pq = new PriorityQueue<Integer>();

디큐(Deque, Double-ended Queue)

한쪽 끝으로만 추가/삭제가 가능한 큐와 달리, Deque는 양방향으로 추가/삭제가 가능해요. Deque의 부모는 Queue고, 구현체로는 ArrayDeque와 LinkedList가 있어요.

// 모두 허용해요.
Queue<Integer> dq1 = new ArrayDeque<>();
Queue<Integer> dq2 = new LinkedList<>();
Deque<Integer> dq3 = new LinkedList<>();
Deque<Integer> dq4 = new ArrayDeque<>();
/*
Deque<Integer> dq5 = new Deque{
	// Deque는 인터페이스라 이렇게 사용하려면
    // 따로 메서드를 선언해줘야 해요
}<>();
*/