[자료구조] 스택과 큐

스택과 큐는 배열에서 발전된 형태의 자료구조 입니다. 

스택과 큐는 구조는 비슷하지만 처리 방식은 살짝씩 다른데요. 두 자료구조에 대해 알아보도록 하겠습니다.

 

 

스택

스택은 삽입과 삭제 연산이 후입 선출 (먼저 들어온게 가장 나중에 나감) 로 이뤄지는 자료구조 입니다

후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있습니다. 

스택 용어

 

위치

top : 삽입과 삭제가 일어나는 위치

 

연산

push : top 위치에 새로운 데이터를 삽입하는 연산.

pop :  top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산

peek :  top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

 

활용

깊이 우선 탐색(DFS) , 백트래킹 종류의 코딩데스트 

후입선출 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문에 

코딩 테스트에서 많이 나오는 문제 유형이라 반드시 알아두어야 하는 자료구조 입니다.

 

큐

큐는 삽입과 삭제 연산이 선입선출(먼저 들어온게 먼저 나가는 구조)로 이뤄지는 자료구조 입니다. 

스택과 다르게 먼저 들어온 데이터가 먼저 나갑니다. 그래서 삽입과 삭제가 양방향에서 이루어 집니다.

큐 용어

rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.

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

add  : rear 부분에 새로운 데이터를 삽입하는 연산

poll :  front 부분에 있는 데이터를 삭제하고 확인하는 연산

peek :  큐의 맨 앞 (front) 에 있는 데이터를 확인할 때 사용하는 연산

 

활용

너비우선 탐색(BFS) 

 

우선순위 큐

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

큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치

일반적으로 힙을 이용해 구현