스택
스택(stack)은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조다.
후입 선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
스택 용어
위치
- top : 삽입과 삭제가 일어나는 위치를 뜻한다.
연산
- push : top 위치에 새로운 데이터를 삽입하는 연산이다.
- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산이다.
- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.
스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.
큐
큐(queue)는 삽입과 삭제 연산이 선입선출(FIFO)로 이뤄지는 자료구조이다.
스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이루어진다.
큐 용어
- rear : 큐에서 가장 끝 데이터를 가리키는 영역이다.
- front : 큐에서 가장 앞의 데이터를 가리키는 영역이다.
- add : rear 부분에 새로운 데이터를 삽입하는 연산이다.
- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산이다.
- peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산이다.
큐는 너비 우선 탐색(BFS)에서 자주 사용하므로 잘 알아두어야 하는 개념이다.
- Do it! 알고리즘 코딩테스트 자바 편
