[JAVA] Stack과 Queue + Deque, 우선순위 큐(PriorityQueue )

Stack과 Queue

자바에서는 Stack과 Queue를 제공한다. 우선 자바에서 제공하는 Stack과 Queue를 알아보기 전에 Stack과 Queue 자료구조에 대해서 알아보도록 하자.

 

 

 

 

스택(Stack)

[자료구조] - 스택(Stack)

 

 

 

 

큐(Queue)

https://ttl-blog.tistory.com/631

[자료구조] - 큐(Queue)

 

 

 

 

스택과 큐의 구현

스택의 경우에는 데이터를 순차적으로 추가하고, 순차적으로 삭제한다. 따라서 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.(실제로 Vector로 구현되어 있다.)

 

 

큐의 경우에는 항상 첫 번째 데이터부터 삭제해야 하므로, 배열 기반의 컬렉션 클래스를 사용한다면, 값을 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다. 그래서 큐는 LinkedList로 구현하는 것이 더 적합하다.

 

 

 

 

---

 

Stack

Stack을 살펴보자. 자바에서 제공하는 Stack의 메서드는 다음과 같은 것들이 있다.

메서드	설명
boolean empty()	Stack이 비어있는지 알려준다.
Object peek()	Stack의 맨 위(가장 마지막에 들어온 값) 객체를 반환한다. pop()과 달리 Stack에서 객체를 삭제하지는 않고 단순히 조회만 한다. (비어있는 경우 EmptyStackException이 발생한다.)
Object pop()	Stack의 맨 위에 저장된 객체를 꺼낸다. (비었을 때는 EmptyStackException이 발생한다.)
Object push(Object item)	Stack에 객체를 저장한다.
int search(Object o)	Stack에서 주어진 객체를 찾아서 그 위치를 받환한다. 못찾으면 -1을 반환한다. (배열과 달리 위치는 0이 아닌 1부터 시작한다. 즉 가장 맨 위(가장 마지막에)에 있는 요소가 1이다.)

 

사용

Stack<Integer> stack = new Stack<>();
stack.push(10);
stack.push(20);
stack.push(30);
stack.push(40);


System.out.println(stack.search(10));//4
System.out.println(stack.search(40));//1
System.out.println(stack.peek());//40

 

---

 

Queue

Queue는 LinkedList를 사용하여 구현할 수 있다.

메서드	설명
boolean isEmpty()	Queue가 비어있는지 알려준다.
boolean add(Object o)	객체를 Queue에 추가한다. 성공하면 true를 반환하며, 저장공간이 부족하다면 illegalStateException이 발생한다.
boolean offer(Object o)	객체를 Queue에 추가한다. 성공하면 true, 실패하면 false를 반환한다.
Object remove()	Queue에서 객체를 꺼내 반환한다. 비어있으면 NoSuchElementException이 발생한다.
Object poll()	Queue의 객체를 꺼내서 반환한다. 비어있으면 null을 반환한다.
Object element()	삭제없이 요소를 읽어온다. peek()와 달리 Queue가 비어있으면 NoSuchElementException이 발생한다.
Object peek()	삭제없이 요소를 읽어온다. Queue가 비어있으면 null을 반환한다.

 

사용

Queue<Integer> queue = new LinkedList<>();
System.out.println(queue.isEmpty());
queue.add(10);
queue.offer(20);
queue.offer(30);

System.out.println(queue.peek());//10
System.out.println(queue.poll());//10
System.out.println(queue.poll());//20

 

 

---

 

Deque

자바에서 Deque는 Queue 인터페이스를 상속받은 인터페이스이며, Queue와 마찬가지로 LinkedList를 통해 구현될 수 있다.

 

우선 Deque는 Double Ended Queue의 줄임말고, 큐의 양 사이드에서 엘리먼트의 삽입과 삭제가 가능한 자료구조이다.

덱은 스택처럼 사용할 수도 있고, 큐처럼 사용할 수도 있는데, 그중에서도 특히 한쪽으로만 입력이 가능하도록 설정한 덱을 스크롤(scroll)(입력제한덱)이라 하고, 한쪽으로만 출력이 가능하도록 설정한 덱을 셸프(shelf)(출력제한덱)라고 한다

 

Deque의 메소드는 다음과 같은데 그림으로 알아보자.

 

삽입

https://soft.plusblog.co.kr/24

 

삭제

https://soft.plusblog.co.kr/24

 

조회

https://soft.plusblog.co.kr/24

 

 

 

 

사용

Deque<Integer> queue = new ArrayDeque<>();
Deque<Integer> queue2 = new LinkedList<>();

다음과 같이 LinkedList나 ArrayDeque로 사용될 수 있으며, 설명에 따르면 ArrayDeque로 사용 시 Stack으로 사용하면 Stack보다 빠르고, Queue로 사용하면 LinkedList보다 빠를 수 있다고 한다.

(그럼 스택이랑 큐는 대체 왜쓰냐!!! ㅠㅠ)

 

---

 

우선순위 큐(PriorityQueue)

PriorityQueue는 먼저 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다. 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적입니다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다.
출처 - https://coding-factory.tistory.com/603

 

사용 방법은 다음과 같다.

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

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

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

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

 

 

 

📔 Reference

[JAVA의 정석 기초편 - 남궁성]

 

[Java] PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

 

[Java(자바)] Deque(덱/데크) 자료구조