스택과 큐는 데이터를 넣고 빼는 규칙이 정해져 있는 선형 자료구조다. 둘 다 여러 값을 순서대로 보관한다는 점은 비슷하지만, 어떤 값을 먼저 꺼내는지가 다르다. 스택은 나중에 들어온 값이 먼저 나오고, 큐는 먼저 들어온 값이 먼저 나온다.
이 차이는 코딩 테스트에서 꽤 중요하다. 같은 데이터를 다루더라도 스택을 쓰면 최근 상태로 되돌아가는 흐름을 만들기 쉽고, 큐를 쓰면 들어온 순서대로 차례차례 처리하는 흐름을 만들기 쉽다.
스택
스택은 후입선출 구조다. 영어로는 LIFO, Last In First Out이라고 한다. 접시를 쌓아두고 맨 위 접시부터 꺼내는 모습을 떠올리면 이해하기 쉽다. 새 데이터는 항상 맨 위에 쌓이고, 꺼낼 때도 맨 위 데이터부터 꺼낸다.
스택에서 삽입과 삭제가 일어나는 위치를 top이라고 한다. push는 top에 새 데이터를 넣는 연산이고, pop은 top에 있는 데이터를 꺼내는 연산이다. peek은 데이터를 제거하지 않고 top의 값만 확인할 때 사용한다.
스택은 DFS, 백트래킹, 괄호 검사처럼 “최근에 들어온 상태를 먼저 처리해야 하는 문제”에서 자주 사용된다. 재귀 호출도 내부적으로는 스택과 비슷한 방식으로 동작한다. 함수가 호출될 때마다 실행 정보가 쌓이고, 가장 나중에 호출된 함수가 먼저 끝난다.
push(1) -> [1]
push(2) -> [1, 2]
pop() -> 2
남은 값 -> [1]큐
큐는 선입선출 구조다. 영어로는 FIFO, First In First Out이라고 한다. 줄을 서서 기다릴 때 먼저 온 사람이 먼저 처리되는 것과 같다. 새 데이터는 뒤에 들어가고, 꺼낼 때는 앞에서부터 꺼낸다.
큐에서는 데이터를 넣는 뒤쪽을 rear, 데이터를 꺼내는 앞쪽을 front라고 부른다. add 또는 offer는 rear에 데이터를 넣는 연산이고, poll은 front의 데이터를 꺼내는 연산이다. peek은 front의 값을 제거하지 않고 확인할 때 사용한다.
큐는 BFS, 작업 대기열, 메시지 처리처럼 “들어온 순서대로 처리해야 하는 문제”에 잘 맞는다. 특히 BFS에서는 현재 위치에서 갈 수 있는 후보를 큐에 넣고, 먼저 발견한 후보부터 순서대로 탐색한다.
add(1) -> [1]
add(2) -> [1, 2]
poll() -> 1
남은 값 -> [2]정리하면 스택은 최근 상태를 되돌아보는 구조이고, 큐는 순서를 보장하며 처리하는 구조다. 문제를 풀 때 “가장 최근에 넣은 것을 먼저 봐야 하는가, 아니면 먼저 들어온 것을 먼저 처리해야 하는가”를 기준으로 선택하면 된다.