코딩테스트 합격을 위한 [스택, 큐] 정리

요약

stack

- 후입 선출 구조 (Last In First Out)

- 일반적으로 queue 보다 성능이 좋지 않음.

- 짝 맞추기, 되돌리기, DFS, 재귀 유형에서 활용

Deque<Integer> s = new ArrayDeque<>(); // 스택 선언

[삽입]
s.push(5); // 값 삽입

[삭제]
s.pop(); // 값 삭제
s.clear(); // 모든 값 삭제

[조회]
int a = s.peek(); // 스택의 최상단에 있는 원소 가져오기
s.size(); // 스택 크기 조회 (스택에 담긴 원소 개수)
s.contains(); // 스택에 해당 원소가 존재하는지 조회 (true/false)
s.isEmpty(); // 스택이 비었는지 검사 (true/false)

 

Queue

- 선입 선출 구조 (First In First Out)

- BFS/투 포인터/Queue 문제에서 활용

 

Queue<Integer> q = new ArrayDeque<>(); // 큐 선언

[삽입]
q.offer(5); // 값 삽입

[삭제]
q.poll(); // 값 삭제
q.clear(); // 모든 값 삭제

[조회]
int a = q.peek(); // 큐에 최상단에 있는 원소 가져오기
q.size(); // 큐의 크기 조회
q.contains(); // 큐에 해당 원소가 존재하는지 조회 (true/false)
q.isEmpty(); // 큐가 비었는지 검사 (true/false)

문제 모음

 

문제 이름	문제 태그	문제 사이트	해설
유효한 괄호 (leetcode)	#짝 맞추기(스택)	https://leetcode.com/problems/valid-parentheses/description/
괄호 회전하기 (프로그래머스)	#짝 맞추기(스택) #유효한 괄호 응용 version	https://campus.programmers.co.kr/tryouts/139162/challenges
daily tempuratures (leetcode)	#Monotonic stack	https://leetcode.com/problems/daily-temperatures/description/
주식가격 (프로그래머스)	#Monotonic stack	https://campus.programmers.co.kr/tryouts/139163/challenges
기능개발 (프로그래머스)	#Monotonic stack	https://campus.programmers.co.kr/tryouts/139164/challenges
탑 (백준 2493번)	#Monotonic stack	https://www.acmicpc.net/problem/2493
두 큐 합 같게 만들기 (프로그래머스)	#큐의 이동 구현	https://campus.programmers.co.kr/tryouts/139161/challenges