스택, 큐

📖 Stack

스택은 삽입,삭제 연산이 후입선출(Last-In-First-Out)구조를 가진 선형 자료구조 입니다.

특징

가장 나중에 삽입된 자료로 부터 삭제되는 구조를 가지고 있으며, 자료의 양과는 별개로 한번의 연산에 한개의 데이터만 삽입,삭제할 수 있습니다. 또한 스택이 가르키는 위치는 한개로 여러개의 위치를 가지지 않습니다.

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

🤔 사용하면 좋은 점

스택은 DFS(깊이 우선 탐색), 백트래킹 종류의 코딩 테스트에 효과적입니다. 이유는 후입선출의 개념이 위와 같은 재귀 함수 알고리즘 원리와 동일하기 때문입니다.

📖 Queue

큐는 삽입,삭제 연산이 선입선출(First-In_First-Out)로 이루어지는 자료구조 입니다.

특징

• front : 큐에서 가장 앞 데이터를 가르키는 위치
• rear : 큐에서 가장 끝 데이터를 가르키는 위치
• add : rear 부분에 새로운 데이터를 삽입하는 연산
• poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
• peek : front 부분에 있는 데이터를 확인하는 연산

🤔 사용하면 좋은 점

큐는 BFS(너비 우선 탐색)에 자주 사용됩니다. 스택과 동일한 이유로 꼭 알아야합니다.

Priority Queue

일반 큐와 마찬가지로 요소가 한쪽 끝에 추가되고 다른 쪽 끝에서 FIFO(First-In-First-Out)순서로 제거됩니다. 다른점은 우선 순위 대기열이라는 것이 있으며 우선 순위가 가장 높은 요소는 항상 대기열 맨 앞에 있습니다. 우선 순위 값은 정수, 문자열, 객체와 같은 비교 가능한 유형입니다. (응급실 우선 순위 대기열과 비슷한 구조)

이러한 특징으로 인해 일부 알고리즘에서 사용됩니다.

• 다익스트라 알고리즘(가중 그래프에서 두 노드 사이의 최단 경로를 찾는 알고리즘) : 해당 자료 구조를 이용하여 소스 노드로부터의 거리로 노드를 저장하고 각 단계에서 최소 거리로 노드를 추출합니다.

• 허프만 코딩(주파수를 기반으로 심볼에 가변 길이 코드를 할당하는 압축 기술) : 해당 자료 구조를 이용하여 주파수가 낮은 노드가 루트에 더 가깝고 코드가 더 긴 이진 트리를 구축합니다.

• 이벤트 기반 시뮬레이션(시스템을 개별 시점에서 발생하는 일련의 이벤트로 모델링하는 시뮬레이션 기법) : 해당 자료 구조를 사용하여 타임스탬프가 있는 이벤트를 저장하고 각 단게에서 가장 빠른 스탬프가 있는 이벤트를 처리합니다.

우선 순위에 알맞게 삽입하려면 새 요소를 위한 공간을 만들기 위해 이동해야 하므로 시간 및 공간 복잡성 측면에서 비용이 많이 드는 것이 단점입니다.