어떻게 쌓기와 줄서기, 스택과 큐

접시처럼 쌓는다, 스택

앞 레슨에서는 데이터를 한 줄로 늘어놓는 방법을 보았다. 이번에는 늘어놓는 대신 위로 차곡차곡 쌓아 보자.
접시를 쌓는 모습을 떠올리면 된다. 새 접시는 늘 맨 위에 올리고, 꺼낼 때도 맨 위부터 꺼낸다. 그러니 마지막에 올린 접시가 가장 먼저 손에 잡혀요.

접시를 눌러 위로 쌓고, 꺼내기를 눌러 보자. 늘 맨 위, 곧 마지막에 올린 것부터 나와요.

꺼낼 때마다 방금 올린 것이 먼저 나왔다. 나중에 넣은 것이 먼저 나온다는 것, 이것이 스택의 약속이에요.
넣는 곳도 빼는 곳도 맨 위 한 군데뿐이라 규칙이 아주 단순하다. 넣는 동작을 푸시, 꺼내는 동작을 팝이라고 부른다. 이 단순한 규칙이 어디에 쓸모가 있는지는 조금 뒤에 다시 만난다.

줄을 선다, 큐

이번에는 쌓는 대신 옆으로 줄을 세워 보자. 버스를 기다리는 줄을 떠올리면 된다. 새로 온 사람은 맨 뒤에 서고, 버스가 오면 맨 앞부터 탄다.
그러니 먼저 온 사람이 먼저 들어간다. 쌓기와는 정반대예요. 이렇게 뒤로 들어와 앞으로 나가는 줄서기를 큐라고 한다.

사람을 눌러 줄 맨 뒤에 세우고, 내보내기를 눌러 보자. 늘 맨 앞, 곧 먼저 온 사람부터 나가요.

내보낼 때마다 가장 오래 기다린 사람이 먼저 나갔다. 먼저 넣은 것이 먼저 나온다는 것, 이것이 큐의 약속이다.
뒤로 들어와서 앞으로 나가니 들어온 순서가 그대로 지켜진다. 그래서 새치기 없이 공평한 차례가 보장돼요. 스택은 나중에 온 것이 먼저, 큐는 먼저 온 것이 먼저다.

스택은 되돌리기에 쓴다

글을 쓰다가 실수해서 되돌리기를 누르면 방금 한 일이 먼저 취소된다. 그 전에 한 일은 그다음에 취소된다.
프로그램이 한 동작을 차례로 쌓아 두었다가, 맨 위의 마지막 동작부터 하나씩 꺼내 취소하는 것이다. 바로 스택이에요. 브라우저의 뒤로 가기 버튼도 지나온 페이지를 쌓아 두는 같은 원리이고, 프로그램 안에서 함수를 부를 때도 컴퓨터는 부른 순서를 스택에 쌓아 둔다.

동작을 눌러 쌓고, 되돌리기를 눌러 보자. 마지막에 한 동작부터 차례로 취소돼요.

되돌리기를 누를 때마다 가장 최근의 동작부터 사라졌다. 순서를 거꾸로 되감아야 할 때는 스택만큼 잘 맞는 것이 없다. 마지막에 넣은 것을 먼저 꺼내는 약속 자체가 곧 되감기이기 때문이에요.
그렇다면 순서를 거꾸로가 아니라 들어온 그대로 지켜야 할 때는 무엇을 쓰면 될까?

큐는 대기열에 쓴다

여러 사람이 프린터 한 대에 인쇄를 맡기면 어떻게 될까? 먼저 보낸 문서가 먼저 인쇄되고, 나중에 보낸 문서는 뒤에서 기다린다. 이것이 인쇄 대기열이다.
은행 번호표도 마찬가지다. 먼저 뽑은 번호가 먼저 불려요. 들어온 순서대로 공평하게 처리하는 것, 바로 큐가 하는 일이다.

문서를 눌러 인쇄 대기열에 넣고, 인쇄를 눌러 보자. 먼저 맡긴 것부터 차례로 처리돼요.

인쇄를 누를 때마다 가장 먼저 맡긴 문서가 나왔다. 순서를 그대로 지켜야 할 때는 큐만 한 것이 없다. 먼저 넣은 것을 먼저 꺼내는 약속이 곧 공평함이기 때문이다.
같은 데이터라도 꺼내는 규칙 하나로 쓰임새가 이렇게 달라져요. 이제 둘을 나란히 놓고 정리해 보자.

정리

한 줄로 모으면 이렇다. 스택은 접시 쌓기라서 나중에 넣은 것이 먼저 나온다. 큐는 줄서기라서 먼저 넣은 것이 먼저 나온다.
되돌리기와 뒤로 가기는 스택, 대기열과 번호표는 큐예요. 넣고 빼는 규칙 하나가 쓰임새를 정하는 셈이다. 스택은 나중 것이 먼저, 큐는 먼저 온 것이 먼저라는 한 줄만 챙기면 된다.

핵심을 차례로 눌러 되짚어 보자. (쌓기 스택 → 줄서기 큐 → 스택은 되돌리기 → 큐는 대기열)

이제 데이터를 쌓고 줄 세우는 두 가지 방법을 알았다. 넣는 곳과 빼는 곳을 정하는 것만으로 전혀 다른 도구가 되었다.
지금까지는 프로그램 안에서 데이터를 담는 그릇을 보았어요. 다음 레슨에서는 프로그램이 꺼져도 사라지지 않게, 아주 많은 데이터를 오래 보관하는 거대한 창고인 데이터베이스를 만난다.