본문 바로가기
inflearn/Do it! 알고리즘 코딩테스트 with C++

섹션1. 자료구조(Data Structure). 스택과 큐

by 슐리반 2023. 10. 1.

< 스택 >

  º  삽입과 삭제연산이 후입선출(나중에 들어온 데이터가 먼저 나가는 구조)로 이뤄지는 자료 구조
  º  top위치에서만 데이터 삽입, 삭제가 가능하다

 

<스택 용어 정리>

 º   위치 용어
  -> top : 삽입과 삭제가 일어나는 위치
 º   연산 용어
 ->  push : top위치에 새로운 데이터를 삽입하는 연산
 ->  pop : top위치에현재 있는 데이터를 삭제하고 확인하는 연산
 ->  top : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 º   스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩테스트에 효과적, 후입선출은 재귀 함수 알고리즘 원리와 일맥상통

Q1. Stack과 재귀함수가 왜 LastInFirstOut로 같을까?
 ->  Stack은 데이터 삽입과 삭제가 top에서만 일어남
Q2.  재귀함수는 왜 LIFO 일까?
 ->   제일 마지막에 실행된 함수가 가장 먼저 호출이 끝나고 제일 먼저 실행된 함수는 가장 마지막에 호출이 끝난다. 그래서 LIFO의 구조이다.

 

< 큐 >

  º   삽입과 삭제가 선입선출(가장 먼저 들어온 데이터가 가장 먼저 나간다)로 이뤄지는 자료구조이다.

  º   새 값 추가는 큐의 back에서 이뤄지고, 삭제는 큐의 front에서 이루어진다.

<큐 용어 정리>

 º   위치 용어
  ->  back : 큐에서 가장 끝 데이터를 가리킴
  ->  front : 큐에서 가장 앞의 데이터를 가리킴
 º   연산 용어
  ->  push : back 부분에 새로운 데이터를 삽입하는 연산
  ->  pop ; front부분에 있는 데이터를 삭제하고 확인하는 연산

  º    큐는 너비 우선 탐색에서 자주 사용한다
  º    DFS는 스택 또는 재귀함수(더 많이 씀)로 사용하지만,  BFS는 큐로 구현한다. 

정리) stack은 연산이 한쪽에서 이루어지고 큐는 연산이 양쪽에서 이루어진다.

 


<우선순위 큐>

  º     값이 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
  º     front를 max 또는 min값으로 항상 유지한다 -> 힙을 사용하여 구현 (힙은 트리종류 중 하나)