[코테 합격자 되기] 06/07장 스택과 큐

# 스택

- 스택의 개념

LIFO(Last In First Out)

가장 최근에 들어온 원소가 가장 먼저 나오는 자료구조

 

- 스택을 언제 써야 하는가?

가장 최근에 들어온 원소를 활용해야 하거나

가장 최근에 들어온 원소 순서대로 활용해야 하는 경우에 스택을 써야 한다

 

- ADT?

ADT(Abstract Data Type)는 추상 데이터 타입의 약어로

세부 사항을 숨기고 사용자에게 필요한 기능만 명시한 것이다

 

- 스택의 ADT

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/stack.cpp

 

- 스택의 예시

1) 함수 호출

 

2) 이전 페이지로 가기

 

3) 괄호 짝 맞추기

해당 문제의 경우에

닫힌 괄호를 가장 최근의 열린 괄호와 매칭하는 것이 핵심이다

참고 코드: https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/parenthesesBalanced.cpp

 

---

 

# 큐

- 큐의 개념

FIFO(First In First Out)

가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조

 

- 큐의 ADT

front는 가장 먼저 들어온 원소

rear는 가장 최근에 들어온 원소

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/STL/queue.cpp

 

- 큐의 예시

1) 줄 서기

 

2) 요세푸스 문제

 

해당 문제는 큐를 활용하여

제거할 인원은 pop 하고

제거하지 않을 인원은 뒤로 push를 하여 순환되는 느낌을 만드는 것이 핵심이다

 

K가 2라는 가정하에

아래와 같이 동작하고 O(N * K)의 시간복잡도를 가진다

 

참고 코드:

https://github.com/dremdeveloper/codingtest_cpp/blob/main/Algorithm_with_DataStructure/queue_josephuse.cpp

 

# 정리

스택은

"가장 최근 원소"

DFS, 백트래킹에서 활용

 

큐는

"들어온 순서대로 나가"고 "순환"하도록 구현할 수도 있다

BFS에서 활용