스택과 큐는 배열에서 발전된 형태의 자료구조이다. 스태과 큐는 구조는 비슷하지만 처리 방식은 다르다.
스택
스택은 삽입과 삭제 연산이 후입선출(Last in First out)로 이뤄지는 자료구조. 후입선출은 삽입과 삭제가 한 쪽에서만 일어난다.
스택용어
top: 삽입과 삭제가 일어나는 위치를 뜻한다.
push: top에 위치에 새로운 데이터를 삽입하는 연산이다.
pop: top위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
peek: top위치에 있는 데이터를 단순 확인하는 연산이다.
*스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이다. 후입선출 개념은 재귀 함수 알고리즘 원리와 일맥상통하다.
큐
삽입과 삭제 연산이 선입선출(First in First out)로 이뤄지는 자료구조. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 삽입과 삭제가 양방향에서 이뤄진다.
새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄진다.
큐 용어
rear: 큐에서 가장 끝 데이터를 가리키는 영역
front: 큐에서 가장 앞의 데이터를 가리키는 영역
add: rear부분에 새로운 데이터를 삽입한느 연산
poll: front부분에 있는 데이터를 삭제하고 확인하는 연산
peek: 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산
큐는 너비 우선 탐색(BFS)에서 자주 사용된다.
우선순위 큐
값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조. 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현하는데 힙은 트리 종류 중 하나이다.
