스택은 삽입과 삭제 연산이 **후입선출 LIFO(Last-in First-out)**로 이뤄지는 자료구조다. 후입선출은 삽입과 삭제가 한 쪽에서만 일어나는 특징이 있다.
새 값이 스택에 들어가면 top이 새 값을 가리킨다. 스택에서 값을 빼낼때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있어 결과적으로 가장 마지막에 넣었던 값이 나오게 되는 것이다.
스택은 깊이 우선 탐색 (DFS), 백트래킹 종류의 코딩 테스트에 효과적이다. 후입선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하다.
큐는 삽입과 삭제 연산이 **선입선출(FIFO: First-in First-out)**로 이뤄지는 자료구조다. 스택과 다르게 먼저 들어온 데이터가 먼저 나간다. 그래서 삽입과 삭제가 양방향에서 이뤄진다.
새 값 추가는 큐의 rear에서 이뤄지고, 삭제는 큐의 front에서 이뤄진다.
큐는 너비 우선 탐색(BFS)에서 자주 사용하ㄴ다.