[코테] 스택, 큐

스택

스택이란?

LIFO 구조 (Last In First Out), 혹은 FILO 구조라고 할 수도 있음

스택 문제의 단서

1. 가장 최근에 들어온 원소를 알 수 있다.
2. 가장 최근에 들어온 원소 순으로 나온다.

스택의 ADT

push() 스택의 맨 위에 원소를 추가한다.

pop()	스택의 맨 위 원소를 제거한다.
top()	스택의 맨 위 원소를 반환한다.
empty()	스택이 비어있으면 참을 반환한다.
size()	스택의 크기를 반환한다.

스택의 사용예시

1. 함수 호출 관리
2. 페이지 탐색
3. 괄호 짝 맞추기
4. DFS
5. 백 트래킹

큐

큐란?

FIFO 구조 (First In First Out), 혹은 LILO 구조라고 할 수도 있음

큐 문제의 단서

1. 들어온 순서대로 나갈 때 사용한다.

큐의 ADT

push() 큐의 맨 뒤에 원소를 추가한다.

pop()	큐의 맨 앞 원소를 제거한다.
front()	큐의 맨 앞 원소를 반환한다.
back()	큐의 맨 뒤 원소를 반환한다.
empty()	큐가 비어있으면 참을 반환한다.
size()	큐의 크기를 반환한다.

큐의 사용예시

1. 줄 서기
2. 요세푸스 문제
3. BFS

스택과 큐를 사용한 문제 예시

백준 4963번 섬의 개수: DFS를 쓰기 위해 스택을 활용한 문제

문제   

풀이

[백준] 4963번 섬의 개수 - C++

 

백준 1966번 프린터 큐: BFS를 사용하여 프린터 큐를 구현하는 문제

문제

풀이

Algorithm/Baekjoon/1966.cpp at main · Y0ngjun/Algorithm

 

출처 : 코딩테스트 합격자 되기 C++ 편 (박경록 저)