[Java/자바] 스택(Stack)과 큐(Queue)

스택(Stack)과 큐(Queue)를 설명하기 앞서 간단하게 알아봅시다.

Stack은 LIFO(Last In First Out) 구조로 되어 있으며, 쉽게 해석하면 "후입 선출" 입니다.

즉, 마지막(최근)에 넣은 것을 먼저 뺀다는 말이죠.

 

Queue는 FIFO(First IN First Out) 구조로, Stack과 반대로 "선입 선출" 입니다.

아르바이트하면서 냉장고에 재고 채워넣을 때 선입선출이란말 자주 들어보셨죠 ?

즉, 먼저 넣은 것(오래된 것)을 먼저 뺀다는 말입니다. 

 

스택(Stack)과 큐(Queue) 비교 코드

import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;

class StackQueueEx {
	public static void main(String[] args) {
		Stack st = new Stack();
		Queue q = new LinkedList();	 // Queue인터페이스의 구현체인 LinkedList를 사용
		
		// Stack에 값 넣기
		st.push("0");
		st.push("1");
		st.push("2");

		// Queue에 값 넣기
		q.offer("0");
		q.offer("1");
		q.offer("2");

		System.out.println("= Stack =");
		while(!st.empty()) {
			System.out.println(st.pop());
		}

		System.out.println("= Queue =");
		while(!q.isEmpty()) {
			System.out.println(q.poll());
		}
	}
}

출력 결과

위 코드를 보면 Stack은 값을 꺼냈을 때 넣은 순서의 반대로 값을 얻습니다. ( 후입선출 )

Queue는 먼저 넣은 "0"부터 꺼내여 넣은 순서대로 값을 얻습니다. ( 선입선출 )  

 

자 여기 까지 간단하게 스택과 큐에 대한 개념을 알아봤으며 이제 각 클래스 별로 알아봅시다.

---

스택(Stack)

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

 

스택 선언하기

import java.util.Stack;

Stack stack = new Stack();

Stack의 메서드

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

 

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

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

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

 

큐 선언하기

import java.util.Queue;
import java.util.LinkedList;

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

 

Queue의 메서드

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

 

이 메서드를 보면 서로 비슷해보이는데 뭔 차이지 싶을겁니다.

자세히 정리해보자면 다음과 같습니다.

	예외 발생	값 출력
추가	add()	offer()
삭제	remove()	poll()
읽기	element()	peek()

두 비슷한 메서드들은 문제가 발생했을 시 예외를 발생시키느냐, null 또는 false를 반환하느냐의 차이입니다.

큐에 값을 추가하는데 큐가 꽉 찼을 시 add()는 예외를 발생시키고, offer는 추가 실패를 의미하는 false를 반환합니다.

 

---

PriorityQueue(우선순위 큐)

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

PriorityQueue는 null은 저장할 수 없으며, null을 저장할 시 NullPointerException이 발생합니다.

 

PriorityQueue는 저장공간을 배열을 사용하며, 각 요소를 "힙(heap)"이라는 자료구조의 형태로 저장합니다.

힙(heap)은 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징을 가집니다.

 

PriorityQueue의 선언

import java.util.PriorityQueue;
import java.util.Queue;

Queue pq = new PriorityQueue();

 

import java.util.PriorityQueue;
import java.util.Queue;

class PriorityQueueEx {
	public static void main(String[] args) {
		Queue pq = new PriorityQueue();
		pq.offer(3); 
		pq.offer(1);
		pq.offer(5);
		pq.offer(2);
		pq.offer(4);

		System.out.println(pq); // pq의 내부 배열을 출력

		Object obj = null;

		// PriorityQueue에 저장된 요소를 하나씩 꺼낸다.
		while((obj = pq.poll())!=null) 
			System.out.println(obj);
	}
}

poll로 값을 가져오면 위 처럼 숫자가 작은 것이 우선순위를 가져, 1 2 3 4 5 순으로 출력됩니다.

 

pq에 offer로 값을 저장하고 출력하면 다음과 같은 배열을 가지는데, 입력한 값 순서와 좀 많이 다르게 출력이 되었습니다.

그 이유는 PriorityQueue의 동작과정을 보면 아래와 같습니다.

 

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] 의 배열을 갖게 됩니다.

---

Deque(Double-Ended Queue)

Deque는 양쪽 끝에 추가,삭제가 가능합니다. ( 스택과 큐를 하나로 합쳐놓은 것과 같다. )

Deque의 조상은 Queue이고, 구현체로는 ArrayDeque, LinkedList 등이 있습니다.

 

Deque의 선언

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

Deque deque = new LinkedList();
Deque deque = new ArrayDeque();

 

 

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

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

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 리턴

 

---

Stack과 Queue의 활용 

 

Stack의 활용

1. 수식계산
2. 수식괄호검사
3. undo(실행 취소) - Ctrl + z
4. redo(되돌 리기) - Ctrl + y
5. 역순 문자열 만들기 - 가장 나중에 입력된 문자부터 출력한다.
6. 후위 표기법 계산수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
7. 웹 브라우저 방문기록 (뒤로 가기) - 가장 나중에 열린 페이지부터 다시 보여준다.

Queue의 활용

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용합니다.

1. 최근사용문서
2. 버퍼(buffer)
3. 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
4. 은행 업무
5. 콜센터 고객 대기시간
6. 프로세스 관리
7. 너비 우선 탐색(BFS, Breadth-First Search) 구현
8. 캐시(Cache) 구현

 

 

---

참고자료
자바의 정석3
https://developerbee.tistory.com/148
https://cocoon1787.tistory.com/795