스택과 큐는 모두
선형구조를 가진 자료구조 입니다.
하지만 스택은
하나의 입출구를 가지고 있어,후입선출, 마지막에 들어온 데이터가 가장 먼저나가는 구조를 가지는 반면
큐는
입구와 출구를 양 끝에 가지고 있어,선입선출, 먼저 들어온 데이터가 가장 먼저나가는 특징을 가지고 있습니다.
스택은 자료의 입출구인
top을 통해서만 접근이 가능하며, 스택의top에 데이터를 넣는push와pop메소드를 가집니다. 스택의 모든 삽입과 삭제연산은 top에서만 일어나므로시간복잡도는 O(1)로 고정됩니다.
추가로 스택이 비었는지 검사하는 isEmpty, 스택의 크기를 리턴하는 size등의 메소드들을 구현할 수 있습니다.
큐는 큐의 맨 앞으로 데이터가 빠져나가는 공간인
front와 큐의 맨 뒤로 데이터가 들어오는 공간인rear를 가집니다. 데이터를 추가하는EnQueue와 데이터를 제거하는DeQueue메서드 모두 양끝에서 데이터를 추가,삭제 해주면 되기 때문에 시간복잡도는O(1)로 고정됩니다.
스택은 쌓아 올리는 자료구조로 대표적으로 자바스크립트의
함수호출(콜스택)과재귀함수방식이 있으며,DFS 탐색과 브라우저에서는뒤로가기와 실행취소 작업에 활용될 수 있습니다.
큐는 줄을 세우는 자료구조로 대표적으로
이벤트루프의 TaskQueue를 생각해볼 수 있으며,BFS 탐색과프린트에서의 작업처리 방식, 버퍼링 현상에 활용할 수 있습니다.
우선순위 큐는 일반적인 큐와 달리 들어간 순서에 상관없이
우선순위가 높은 데이터가 가장 먼저 출력되는 구조를 말합니다.
우선순위 큐는 연견리스트로도 구현될 수 있으나 주로
힙을 통해 구현되는데,힙은 우선순위가 가장 높은 노드가 루트에 위치하는 트리구조입니다.
데이터 삽입 시에는, 가장 마지막 노드에 새로운 데이터가 삽입되고, 이후 부모노드와 우선순위를 비교하여 노드의 구조를 변경하는 작업을 반복합니다.
데이터 삭제의 경우, 우선순위가 가장 높은 루트노드가 바로 삭제됩니다. 삭제 이후, 가장 아래의 노드가 루트노드로 위치하고, 루트노드 부터 자식노드들과의 우선순위를 비교하여 노드의 구조를 변경합니다.
힙은 자료구조로
완전 이진 트리의 한 종류입니다.
단, 힙은 노드의 위치가 높을 수록 그 우선순위가 높다는 특징을 가집니다. 우선순위를 판별하는 값이 가장 큰 노드가 루트노드에 위치한다면
최대 힙, 가장 낮은 값의 데이터가 루트노드에 위치한다면최소 힙으로 부릅니다.
힙은 데이터 삽입과 삭제 연산 시, 부모 혹은 자식 노드와의 비교 연산을 반복하기 때문에 트리의 높이 만큼인 O(logN)의 시간복잡도를 가지게 됩니다.
힙 자료구조는 데이터의 저장과 삭제의 시간복잡도가 O(logN)을 가지고 있어, 연결리스트의 저장 삭제는 탐색시간을 포함하여 O(N)을 가지기 때문입니다.