3. 스택(Stack) & 큐(Queue) & 덱(Deque)

1. 스택(Stack)

• 용도 : 웹 브라우저 뒤로 가기, 실행 취소(Undo), 괄호 짝 맞추기, DFS(깊이 우선 탐색) 등

 

1.1. 구현 클래스

Deque<Integer> stack = new ArrayDeque<>();

 

 

1.2. 메서드

구분	메서드	설명	시간 복잡도
삽입	push(E e)	데이터를 맨 위에 쌓는다.	O(1)
삭제	pop()	맨 위의 데이터를 삭제하며 반환한다.	O(1)
조회	peek()	맨 위의 데이터를 반환한다.	O(1)
검사	isEmpty()	스택이 비어있는지 확인한다.	O(1)

 

1.3. 주의할 점

EmptyStackException : 스택이 비어있는데 pop()이나 peek()을 호출하면 예외가 발생하여 프로그램이 죽기때문에 !stack.isEmpty()로 항상 먼저 체크해야한다.

 

---

2. 큐(Queue)

• 용도 : 프린터 인쇄 대기열, BFS(너비 우선 탐색), 프로세스 스케줄링 등.

 

2.1. 구현 클래스

// 가장 널리 사용됨
Queue<Integer> queue = new LinkedList<>();

// LinkedList보다 조금 더 빠를 수 있음
Queue<Integer> queue = new ArrayDeque<>();

 

 

2.2. 메서드

구분	메서드(안전형)	메서드(예외형)	설명	시간 복잡도
삽입	offer(E e)	add(E e)	데이터를 맨 뒤에 넣는다.	O(1)
삭제	poll()	remove()	맨 앞의 데이터를 삭제하며 반환한다.	O(1)
조회	peek()	element()	맨 앞의 데이터를 반환한다.	O(1)

 

 

2.3. 주의할 점

ArrayList 클래스로는 큐를 구현하지 않는다. 삭제 시 시간 복잡도가 O(N)으로 늘어나기때문이다. 반드시 LinkedList나 ArrayDeque을 써야한다.

 

---

 

3. 덱(Deque)

• 특징 : 스택의 성질과 큐의 성질을 모두 가진 형태다.
• 용도 : 스택/큐 기능을 동시에 써야할 때 사용한다.최댓값/최솟값 찾기, 앞뒤로 데이터를 붙여야하는 문자열 문제 등.

3.1. 구현 클래스

// 가장 일반적인 추천 방식
Deque<Integer> deque = new ArrayDeque<>();

// 리스트의 기능이 필요할 때 사용
Deque<Integer> deque = new LinkedList<>();

 

3.2. 메서드

구분	메서드	설명	시간 복잡도
앞쪽(Front)	offerFirst(E e)	맨 앞에 데이터 추가	O(1)
	pollFirst()	맨 앞에서 데이터를 삭제하고 반환한다.	O(1)
	peekFirst()	맨 앞 데이터를 확인한다.	O(1)
뒤쪽(Rear)	offerLast(E e)	맨 뒤에 데이터를 추가한다.	O(1)
	pollLast()	맨 뒤에 데이터를 삭제하고 반환한다.	O(1)
	peekLast()	맨 뒤에 데이터를 확인한다.	O(1)

 

3.3. 주의할 점

Deque는 Queue의 인터페이스를 상속한다. 그래서 offer(), poll()만 쓰는거라면 큐처럼 동작한다.

push()와 pop()를 쓰면 스택처럼 동작하기때문에 헷갈리지 않게 덱 전용 메서드 First/Last를 명시적으로 쓰는 것이 가독성에 좋다.