Stack
스택(Stack)은 삽입과 삭제 연산이 후입선출(LIFO:Last-in First-out)로 이루어지는 자료구조이다.
새로운 값이 들어가면 top이 새로운 값을 가리키다. 스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있으므로 결과적으로 가장 마지막에 넣었던 값이 나오게 되는 것이다.
스택 용어
- 위치
top : 삽입과 삭제가 일어나는 위치를 뜻한다.- 연산
push : top 위치에 새로운 데이터를 삽입하는 연산이다.
pop : top 위치에 현제 있는 데이터를 삭제하고 확인하는 연산이다.
peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.
스택은 DFS(깊이 우선 탐색),백트래킹 종류의 코딩테스트에 효과적이므로 반드시 알아두어야 한다. 후입선출의 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.
Queue
큐(Queue)는 삽입과 삭제 연산이 선입선출(FIFO:Fisrt-in First-out)로 이루어지는 자료구조이다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이루어진다.
큐 용어
- rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
- add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
큐는 BFS(너비 우선 탐색)에서 자주 사용하므로 역시 스택과 함께 잘 알아 두어야 한다.
우선순위 큐(priority queue)는 값이 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다. 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다. 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다.
