스택과 큐

스택

스택은 삽입과 삭제 연산이 후입선출 last in first out 로 이뤄진 자료구조 입니다. 후입선출은 삽입과 삭제가 한쪽에서만 이뤄진다는 특징이 있습니다.

 

 

그림을 보면 새로운 값이 스택에 들어가게 되면 top이 새 값을 가르키게 됩니다. 스택에서 값을 빼낼때 pop은 top이 가르키는 값을 스택에서 빼게 됩니다. 아래는 스택용어 입니다.

 

스택 용어

- 위치 

top : 삽입과 삭제가 일어나는 위치를 뜻합니다.

 

- 연산

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

peek : top 위치에 있는 데이터를 단순 확인만 하는 연산입니다.

pop : top 위치에 있는 데이터를 삭제 하고 삭제한 데이터를 확인하는 연산입니다.

 

 

스택은 깊이 우선 탐색(DFS : Depth first search), 백트래킹 종류의 코딩 테스트에서 효과적이므로 알아 두어야 합니다. 

후입선출은 개념 자체가 재귀함수 알고리즘과 원리가 일맥상통 합니다.

 

 

 

큐

큐는 삽입과 삭제 연산이 선입선출 first in first out 로 이뤄지는 자료구조 입니다. 

삽입과 삭제가 양방향에서 이뤄집니다. 

 

 

새 값의 추가는 rear에서 이뤄지고 삭제는 front에서 이뤄집니다. 큐의 용어는 아래와 같습니다.

 

큐 용어

- 위치

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

front : 큐에서 가장 앞 데이터를 가르키는 영역입니다.

 

- 연산

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

poll : front부분에 데이터를 삭제하고 확인하는 연산입니다.

peek : 큐의 맨앞 front에 있는 데이터를 확인할때 사용 하는 연산입니다.

 

큐는 너비우선탐색(BFS : Breadth First Search)에서 자주 사용됩니다.

 

 

 

우선순위 큐

 

우선순위 큐는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 입니다. 큐 설정에 따라 front에는 최대값 또는 최소값이 위치 하게 됩니다. 우선순위큐는 일반적으로 힙을 이용해 구현 하는데 힙은 트리 종류중 하나 입니다.