스택과 큐

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

 

 

 

스택과 큐의 핵심 이론

스택

- 스택은 삽입과 삭제 연산이 후입선출로 이뤄지는 자료구조임

- 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있음

- 새 값이 스택에 들어가면 top이 새 값을 가리킴

- 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 되는 것임

- 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적임 !!

- 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통함

 

 

 

스택 용어

- 위치

• top : 삽입과 삭제가 일어나는 위치를 뜻함

- 연산

• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산

 

 

 

큐

- 삽입과 삭제 연산이 선입선출로 이뤄지는 자료구조

- 먼저 들어온 데이터가 먼저 나감

- 삽입과 삭제가 양방향에서 이뤄짐

- 새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄짐

- 너비 우선 탐색(BFS)에 자주 사용함

 

 

 

큐 용어

• rear : 큐에서 가장 끝 데이터를 가리키는 영역
• front : 큐에서 가장 앞의 데이터를 가리키는 영역
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산

 

 

 

우선순위 큐

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

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

- 우선순위 큐는 일반적으로 힙을 이용해 구현하는데 힙은 트리 종류 중 하나임