『Do it! 알고리즘 코딩 테스트 with JAVA 강의』를 듣고 정리한 글입니다.
스택과 큐
스택과 큐는 배열에서 발전된 형태의 자료구조이다. 스택과 큐는 구조는 비슷하지만 처리 방식이 다르다.
스택
- 스택은 삽입과 삭제 연산이 후입선출(LIFO, Last-in First-out)이 이뤄지는 자료구조이다.
- 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
- 스택은 깊이 우선 탐색(DFS, Depth First Search), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다.
- 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.
// Java의 스택
Stack<Integer> stack = new Stack<>();
스택 용어
위치
- top: 삽입과 삭제가 일어나는 위치
연산
- push : top 위치에 새로운 데이터를 삽입하는 연산
- peek : top 위치에 현재 있는 데이터를 단순 확인하는 연산
- pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
큐
- 삽입과 삭제 연산이 선입선출(FIFO, First-in First-out)로 이뤄지는 자료구조
- 스택과 다르게 먼저 들어온 데이터가 먼저 나가므로, 삽입과 삭제가 양방향에서 이뤄진다.
- 너비 우선 탐색(BFS, Breadth First Search)에서 자주 사용한다.
// Java의 큐
Queue<Integer> myQueue = new LinkedList<>();
큐 용어
- reer : 큐에서 가장 끝 데이터를 가리키는 영역
- front : 큐에서 가장 앞의 데이터를 가리키는 영역
- add : reer 부분에 새로운 데이터를 삽입하는 연산
- poll : front 부분에 있는 데이터를 삭제하고 확인하는 연산
- peek : 큐의 맨 앞(front)에 있는 데이터를 확인할 때 사용하는 연산
우선순위 큐
- 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
- 큐 설정에 따라 front에 항상 최댓값 또는 최솟값이 위치한다.
- 일반적으로 힙(Heap)을 이용해 구현하는데, 힙은 트리 종류 중 하나이므로 여기서는 개념만 알고 뒤에서 다룬다.
// Java의 우선순위 큐
PriorityQueue<Integer> myQueue = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if(first_abs == second_abs) { // 절댓값이 같은 경우 음수 우선
return o1 > o2 ? 1 : -1;
}
return first_abs - second_abs; // 절댓값 작은 데이터 우선
});
Reference
[지금 무료] Do it! 알고리즘 코딩테스트 with JAVA 강의 - 인프런