[코딩테스트 합격자 되기 스터디] 2주차 - 스택 / 큐

스택의 개념

• LIFO (Last In First Out) , 가장 최근에 들어간 원소가 가장 먼저 나오는 자료구조
• 코딩테스트에서 특정 문제가 스택 문제인 지 알아야 한다
  • 스택은 "가장 최근에 들어온 원소"를 봐야할 때 사용
    • 추후 DFS / 백트래킹에서 사용

스택의 ADT (설계도)

• ADT (Abstract Data Type) : 추상 데이터 타입. 세부 사항을 숨기고 사용자에게 필요한 기능만 명시함
• push (삽입 연산) , pop (꺼내는 연산) , isFull (가득 찼는지 확인) , isEmpty (비었는지 확인) 와 같은 연산과 top ( 최근에 삽입한 데이터의 위치를 저장하는 변수) 을 정의

스택의 사용 예시

• 함수 호출 : 함수 호출 시 현재 함수의 실행 상태(context) 를 저장, 새로운 함수로 제어 이동
• 이전 페이지로 가기 : 페이지를 전환할 때 마다 스택에 push , 이전 페이지로 갈 때 pop
• 괄호 짝 맞추기

---

큐의 개념

• FIFO (First In First Out) , 가장 먼저 들어간 원소가 가장 먼저 나오는 자료구조
• 큐는 "들어온 순서대로" 나갈 때 사용한다.
  • 추후 BFS 에서 사용

큐의 ADT

• push (삽입 연산) , pop (꺼내는 연산) , isFull (가득 찼는지 확인) , isEmpty (비었는지 확인) 와 같은 연산들과 front (가장 먼저 push 된 원소의 위치, 큐의 앞) , rear (가장 최근에 push 된 원소의 위치, 큐의 뒤) 변수를 정의

큐의 사용 예시

• 줄서기
• 요세푸스 문제

---

[참고 강의]

코딩테스트 합격자 되기 - C++ [ https://inf.run/t92e1 ]