스택과 큐

스택

스택은 삽입과 삭제 연산이 후입선출 (LIFO)로 이뤄지는 자료구조이다.

후입선출은 연산이 한쪽에서만 일어나는 특징이 있다.

 

push : 데이터 삽입

pop : 데이터 삭제 후 확인

peek : 데이터 확인

 

스택은 깊이 우선 탐색 DFS, 백트래킹 종류의 코딩테스트에 많이 사용됨.

후입선출은 재귀함수와 원리가 비슷함.

 

 

 

큐

큐는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조이다.

 

rear : 큐의 가장 끝 데이터를 가리키는 영역

front : 큐의 가장 앞 데이터를 가리키는 영역

add : rear 부분에 새로운 데이터 삽입

poll : front 부분에 있는 데이터 삭제 후 확인

peek : front 부분에 있는 데이터 확인

 

큐는 너비 우선 탐색 BFS에서 많이 사용됨.

 

 

 

우선순위 큐

들어간 순서와 상관없이 우선순위가 높은 데이터 먼저 나오는 자료구조이다.

보통 heap을 이용해 많이 구현함.

큐 설정에 따라 front에 항상 최댓값 / 최솟값이 위치함.