스택과 큐 - 어느 쪽에서 꺼내나

책상에 서류가 쌓여 있다. 처리하려고 한 장을 집을 때, 위에서 집느냐 밑에서 빼느냐로 전혀 다른 두 그릇이 된다.

같은 더미, 꺼내는 자리만 다르다

서류는 늘 위에 얹힌다. 넣는 자리는 하나뿐이다. 갈리는 건 꺼낼 때다.

위에서 집으면 방금 얹은 것이 나온다. 제일 오래된 서류는 맨 밑에 깔려 영영 안 나올 수도 있다. 이게 스택이다.

밑에서 빼면 제일 오래 기다린 것이 나온다. 들어온 순서가 그대로 처리 순서가 된다. 이게 큐다.

담는 그릇도 같고 넣는 방법도 같은데 꺼내는 자리 하나가 다르다. 그런데 이 하나가 쓰임을 완전히 갈라놓는다.

늦게 온 것부터: 스택

스택이 하는 일은 둘뿐이다. 얹기와 걷기. 중간을 뒤지는 기능은 아예 없다. 언제나 꼭대기만 만진다.

기능이 적어서 약해 보이지만, 이 제약이 곧 쓸모다. **“방금 한 일을 되돌린다”**는 문제가 정확히 이 모양이기 때문이다.

• 편집기의 되돌리기 - 마지막에 한 일부터 취소한다
• 괄호가 맞는지 검사 - 열린 괄호를 얹어두고, 닫는 괄호가 나오면 꼭대기와 맞춰본다
• 웹 브라우저의 뒤로 가기 - 마지막에 본 페이지로 돌아간다

앞 글에서 본 두 그릇 어느 쪽으로도 만들 수 있다. 꼭대기만 만지므로 배열이면 맨 뒤가 꼭대기이고 밀 일이 없다. 연결리스트라면 맨 앞이 꼭대기다. 어느 쪽이든 얹기도 걷기도 O(1)이다.

함수 호출이 곧 스택이다

스택을 배우면 늘 나오는 예가 있는데, 사실 이건 예가 아니라 지금 돌고 있는 프로그램 그 자체다.

함수가 함수를 부르면 부른 쪽은 “돌아올 자리”를 남기고 기다린다. 그 기다리는 자리가 쌓인다.

a()가 b()를 부르고 b()가 c()를 부르면 세 개가 쌓인다. c()가 끝나면 꼭대기가 걷히고 b()로 돌아온다. 마지막에 부른 것이 먼저 끝난다 - 스택 그대로다.

그래서 스택 오버플로라는 이름이 붙었다. 재귀가 끝나는 조건을 잘못 적으면 걷히지 않고 계속 쌓이다가 정해진 자리를 넘는다. 에러 이름이 자료구조 이름인 이유가 이거다.

먼저 온 것부터: 큐

큐는 반대다. 뒤로 넣고 앞에서 뺀다. 매표소 줄과 같아서, 오래 기다린 쪽이 먼저 나온다.

스택이 “되돌리기”의 모양이라면 큐는 **“차례대로 처리하기”**의 모양이다.

• 프린터에 보낸 문서들
• 서버에 들어온 요청을 순서대로 처리하기
• 너비 우선 탐색 - 가까운 곳부터 훑는다(뒤에 그래프 편에서 다시 나온다)

여기서 중요한 성질이 하나 나온다. 큐는 순서를 보장한다. 먼저 온 요청이 뒤로 밀리지 않는다는 건 공정성이기도 하고, 대기 시간의 상한이 있다는 뜻이기도 하다.

큐는 빠르기 차이를 흡수한다

큐가 실무에서 도처에 있는 진짜 이유는 순서가 아니라 다른 데 있다. 넣는 쪽과 꺼내는 쪽의 속도가 다를 때 그 차이를 받아주는 웅덩이가 되기 때문이다.

요청은 초당 100개가 들어오는데 처리는 초당 60개밖에 못 한다고 하자. 큐가 없으면 넘치는 40개는 그 자리에서 실패한다. 큐가 있으면 일단 쌓아두고 처리가 따라잡을 시간을 번다.

이게 스레드 풀이 작업 큐를 들고 있는 이유이고, 메시지 큐로 서비스를 잇는 이유이기도 하다. 둘 다 “받는 쪽이 느려도 보내는 쪽이 안 막히게” 하려는 것이다.

다만 웅덩이는 무한하지 않다. 들어오는 속도가 계속 더 빠르면 큐는 그냥 길어지기만 한다. 대기 시간이 늘고 메모리가 찬다. 큐는 순간의 몰림은 흡수하지만 지속적인 부족은 못 메운다.

배열로 큐를 만들면 밟는 함정

큐를 배열로 만들면 자연스럽게 이렇게 짜게 된다. 뒤에 붙이고, 앞에서 뺀다.

그런데 앞에서 빼는 게 문제다. 앞 글에서 본 대로 배열은 맨 앞을 빼면 뒤를 전부 앞으로 당겨야 한다. 꺼낼 때마다 O(n)이 든다. 큐인데 꺼내기가 비싼 이상한 그릇이 된다.

그래서 실제 구현은 당기지 않고 시작점만 옮긴다. 앞이 비면 그 자리는 버려두고 “이제 여기부터”라고 표시만 바꾼다. 그러다 끝에 닿으면 앞의 빈자리로 돌아가 다시 채운다. 배열을 고리처럼 쓰는 것이라 원형 큐라고 부른다.

이런 사정 때문에 큐는 연결리스트가 제 몫을 하는 몇 안 되는 자리이기도 하다. 양 끝만 만지니 걸어갈 일이 없어서, 앞 글에서 본 연결리스트의 약점이 드러나지 않는다.

양쪽이 열린 것: 덱

스택과 큐를 나란히 놓고 보면 자연스러운 질문이 나온다. 양쪽에서 다 넣고 뺄 수 있으면 안 되나.

된다. 그게 덱이고, 실제로 표준 라이브러리들이 스택과 큐를 따로 안 두고 덱 하나로 둘 다 시키는 경우가 많다. 자바의 ArrayDeque, 파이썬의 collections.deque가 그렇다.

기능이 더 많은데 왜 스택과 큐를 따로 배우나 싶을 수 있다. 제약이 곧 뜻이기 때문이다. “이건 스택이다”라고 말하는 순간 중간을 안 건드린다는 약속이 생기고, 읽는 사람이 코드를 덜 의심해도 된다. 덱으로 만들어놓고 스택처럼 쓰는 것과 스택이라고 이름 붙이는 것은 기계에게는 같고 사람에게는 다르다.

실무에서: 세 자리에 같은 모양이 있다

이 둘은 직접 만들 일이 거의 없다. 대신 이미 만들어진 것 안에서 알아보는 게 실무의 쓸모다.

장애를 읽을 때. 스택 트레이스는 이름 그대로 스택을 위에서부터 찍어놓은 것이다. 맨 위가 터진 자리, 아래로 내려갈수록 그걸 부른 쪽이다. 이 순서를 알면 로그가 다르게 읽힌다.

밀린 것을 볼 때. 큐 길이는 가장 정직한 지표에 든다. 큐가 길어지고 있다면 처리 속도가 유입 속도를 못 따라간다는 뜻이고, 응답 시간이 나빠지기 전에 먼저 나타난다.

순서를 약속할 때. “이 작업들은 들어온 순서대로 처리된다”는 보장이 필요한지 아닌지가 설계를 가른다. 순서를 포기하면 여러 대가 나눠 처리할 수 있고, 순서를 지키려면 그만큼 병렬이 줄어든다. 큐를 쓴다는 건 그 교환을 고른 것이다.

정리

• 스택과 큐는 담는 그릇이 아니라 꺼내는 규칙이다. 같은 더미에서 위를 집느냐 밑을 빼느냐다.
• 스택은 되돌리기의 모양이다. 함수 호출이 그대로 스택이고, 그래서 스택 오버플로라는 이름이 붙었다.
• 큐는 차례대로의 모양이고, 실무에서는 빠르기 차이를 받아주는 웅덩이로 더 자주 쓰인다.
• 큐를 배열로 만들면 앞에서 빼는 값이 문제라 당기지 않고 시작점만 옮긴다.
• 기능이 적은 게 약점이 아니다. 제약이 곧 읽는 사람에게 주는 약속이다.

다음 글은 여기서 못 한 일을 하는 그릇이다. 스택도 큐도 “중간에서 하나 찾기”는 못 하는데, 이름만 대면 자리를 계산해서 곧장 집는 방법이 있다.