스택 자료구조의 본질과 진정한 의미

1. 스택의 실생활 예시??

스택(Stack)이란 선형 자료구조 중 하나로, 위 그림과 같이 데이터를 적재(push)하고, 나중에 다시 데이터를 가져올 때는 최근에 적재한 데이터를 가져오는(pop) 자료 구조를 말한다. A, B, C 순서대로 데이터를 넣으면 반드시 C, B, A 순서대로 데이터를 처리한다. 이를 선입후출(Last In, First Out, LIFO)라 한다.

 

흔히 스택을 처음 배울 때, 아래와 같은 실생활 비유를 들어 스택을 받아들인다. 나도 그랬다.

 

 

스택과 비슷한 구조를 실생활에서 찾는 것은 그리 어렵지 않다. stack이라는 말 그대로, 무언가를 쌓아올리는 것이기 때문이다. 처음 스택을 배울 때는 이런 이미지를 그려보는 것이 도움이 된다. 그러나 조금만 더 깊게 들어가면 위 예시들은 컴퓨터 과학에서 말하는 Stack 자료구조와는 완전히 별개라는 것이 드러난다. 

 

자료구조란 그 구조를 토대로 데이터를 처리하겠다는 의미다. 안타깝게도 실생활의 스택의 예시들은 자료를 쌓아올린 순서대로 처리하기 위해 만든 구조가 아니다. 책을 위로 쌓아 올린다고 가장 위에 있는 책만을 읽는 사람이 누가 있을까? 아무도 없을 것이다. 책은 표지를 통해 자신이 어떤 녀석인지 알려준다. 굳이 따지면 책은 인덱싱이 있는 자료구조에 가깝지 스택이 아니다. 

 

다른 예시도 마찬가지다. 옷을 곱게 개어 쌓아올린다고 내일 아침 가장 위에 있는 옷만을 먼저 입어야 하는 사람은 없다. 동전을 쌓아올린다고 가장 위에 있는 동전부터 쓰겠다는 사람도 없다. 실생활 예시라고 든 대부분의 스택 구조들은 물리적인 면에서만 스택 자료구조와 공통점이 있을 뿐이다. 즉, 실생활 예시의 대부분은 저장의 효율을 위해 예쁘게 쌓아올린 것들이지, 처리 순서와는 관련이 없다.

 

스택과 흔히 같이 언급되는 또 다른 자료구조가 큐(Queue)다. 큐의 실생활 예시는 정말로 자료구조에서 말하는 큐의 처리 방식과 동일하다. 인간의 논리와 흡사하다. 먼저 온 것을 먼저 처리한다. 공정과 질서를 중시하는 인간의 특성 상 큐 자료구조의 실생활 예시는 어렵지 않게 찾을 수 있다.

 

2. 컴퓨터에서 스택의 쓰임새

달리 말하면, 스택이라는 자료구조는 의외로 실생활에서 찾아보기 힘든 자료구조다. 예시로 드는 것 대부분은 무언가를 쌓아올린 저장 상태를 말하는 것일 뿐, 실제로 그 순서대로 처리하겠다는 의미로 쌓은 것이 아니기 때문이다.

 

자료구조 시간에서 자료구조를 ADT로 정의해 배운다. ADT는 추상 자료형의 약자로, 그것의 본질은 자료구조를 정의할 때 중요한 것은 그것의 처리 기능 및 명세지, 저장하는 데이터의 타입이나 저장 형태가 아니라는 것이다. 즉, 일상에서 말하는 스택(Stack)은 형태만 동일할 뿐, 실제로 스택처럼 처리하진 않는다는 점에서 컴퓨터 과학에서 말하는 스택과 하등 관계가 없는 것이다. 밀도 있게 효율적으로 저장한 상태 중 스택의 저장 상태와 비슷하다는 이유로 스택이라 할 수는 없다.

 

이렇게 일상에서 스택은 찾아보기 힘들지만, 컴퓨터에서 스택은 매우 흔하면서도 아주 중요하게 다뤄지는 구조다. 

 

 

위 그림은 프로그램이 메모리에 적재되어 실행되는 상태의 프로세스의 스택 구조를 보여준다. 프로세스는 아주 크게 보면 데이터 영역과 처리 영역으로 구분된다. 처리 영역은 명령어의 집합이다. 데이터는 명령어가 다루고 처리하는 대상 데이터들이 모여있는 영역인데, 이들은 다시 여러 종류의 데이터로 구분된다.

 

데이터는 종류가 많다. 초기화된 전역 데이터도 있고, 초기화되지 않은 데이터, 함수에서 사용하는 로컬 데이터, 동적으로 런타임에 결정되어 만들어지는 데이터도 있다. 모두 메모리 자원을 효율적으로 사용하기 위해 분류된 것이다.

 

여기서 중요한 것은 함수 스택, 콜 스택이다. 프로그램 내에서 함수가 호출되면 운영체제는 스택 포인터 레지스터, 스택 프레임 등 여러 장치를 동원해 해당 함수만이 독자적으로 사용할 수 있는 데이터 공간을 마련해준다. 그리고 그 공간들이 스택처럼 저장되고 처리된다. 만약 함수가 재귀되거나 중첩되어 또 다른 함수를 호출한다면 새로운 스택 프레임이 할당되어 위로 쌓인다. 먼저 함수 스택에 쌓인 프레임의 처리 우선순위는 뒤로 밀려난다. (LIFO)

 

이 과정은 논리적으로는 무한하다. 물론 지나치게 함수들을 중첩하면 스택 오버플로우가 발생한다. 프로세스에 허용된 스택 메모리를 다 소진했다는 것이다. 재귀 문제를 풀 때 이 부분을 주의해야 한다.

 

이 내용은 기초적인 운영체제 과목, 혹은 프로그래밍 언어 과목에서 다뤄지는 부분으로, 스택의 쓰임새 중에서 가장 유명하면서도 그 본질을 나타내는 예시일 것이다. 물론 이 외에도 그래프에서 깊이 탐색, 이진 트리에서 순회, 계산기 프로그램 구현 등 스택은 컴퓨터에서 자주 등장한다.

 

3.  어째서 스택이 사용되어야 하나

실생활에 그닥 등장하지 않는 것이 정작 컴퓨터에서 자주 등장한다는 것은 참 의아하다. 그러나 이것이 컴퓨터와 실생활 사이의 본질적인 차이를 드러내준다.

 

표면적으로 스택은 나중에 쌓은 것을 먼저 처리하겠다는 의미다. 실생활의 관점에서 보면 너무나 비합리적인 방식이다. 무언가를 역순으로 처리한다는 방식은 흔하지 않기 때문이다. 사람은 작업을 순서대로 처리하는 것을 좋아한다. 예를 들어, 5! (팩토리얼)을 계산하라고 하면 대부분의 사람들은 1*2*3*4*5 순서대로 곱해나간다. 5*4*3*2*1 순서대로 풀지는 않는다. 설령 계산 결과가 같다고 해도 거꾸로 하면 뭔가 비합리적으로 보인다.

 

사람 본능이 그렇다. 본능적으로 인간은 눈 앞에 있는 문제부터 처리하기를 원한다. 물론 인간은 지능이 있기 때문에 보다 크고 거시적인 문제를 상상할 수 있는 능력이 있지만 습득하기 쉬운 기술이 아니다. 문제의 본질을 상상하는 능력은 별도의 직관을 요구하기 때문이다. 게다가 풀기도 어렵다. 큰 문제일수록 추상화된 상태이기 때문이다.

 

스택 구조의 본질은 상상이 필요하다. 애초에 스택처럼 거꾸로 역산하는 문제에는 어떤 것들이 있을까? 예를 들어, 공부 계획 같은 것은 스택과 관련이 있을까? 공부 계획은 보통 역산을 요구한다. 어떤 목표가 있으면 그것을 잘게 쪼갠다. 수능 수학 1등급 맞기라는 목표가 있다면, 그 목표를 수행하기 위해 필요한 공부량과 시간 자원을 파악하고 그것을 날짜별로 분배할 것이다. 큰 문제에서 작은 문제로 분할한 것 같다.

 

하지만 공부 계획은 스택에서 말하는 역산이 아니라 우선순위에 따라 데이터를 순차적으로 정렬하는 것에 가깝다. 처리는 정렬된 데이터(계획표에 있는 하루 단위 수학 공부량)를 순차적으로 가져와서 처리한다. 또한 push 단계가 생략되어 있다는 점에서 이미 스택의 본질을 벗어났다.

 

스택에서 가장 먼저 push되는 데이터는 도대체 정체가 뭘까? 스택에서 가장 먼저 쌓이는 데이터는 처리 단계에서 가장 우선순위가 낮다. 마지막에 처리된다. 그런데도 가장 먼저 발견되는 데이터이며, 그래서 가장 먼저 적재되는 데이터다. 마무리 단계에서 처리되어야 하는데도 가장 먼저 인식되고, 가장 먼저 스택에 적재된다.

 

이런 식으로 해결되는 문제 구조는 아래 그림과 비슷하다.

 

 

정확한 그림은 아니지만, 많은 프로그램이 위와 같은 실행 구조를 가진다. 모듈과 의존성을 관리하기 위한 객체지향 설계도 크게 보면 다르지 않다. 컴퓨터는 상위 모듈이 다른 모듈의 기능(함수)을 호출한다. 상위 모듈은 하위 모듈이 제공하는 기능(솔루션)을 바탕으로 자신의 차원에서 문제를 해결한다. 프로그래밍이란 결국 input -> 처리 -> output 의 연쇄작동이다. 이 구조는 계층적이고 중첩된다. 하위 솔루션들이 해결된다고 자동으로 전체 문제가 풀리는 것이 아니다. 결국 그 모듈을 호출한 최상위 모듈(main)이 하위 솔루션들이 해결한 정보를 바탕으로 자신의 문제를 해결해야 모든 문제의 해답을 얻을 수 있다.

 

따라서 가장 먼저 시작하는 main 함수 혹은 상위 모듈은 문제 해결의 진입점이다. 가장 먼저 전체 문제를 포괄적으로 해석 및 해결하는 모듈로부터 문제 해결의 프로세스가 시작된다. 거기서 제어가 순차적으로 흘러가면서 하위 모듈을 호출한다. 그러면 하위 솔루션이 실행된다. 하위 솔루션이 문제를 해결해야만 다음 프로세스를 진행할 수 있기 때문에 하위 모듈을 호출하는 것은 생략할 수 없다. (병렬 처리는 잠시 생략하자) 그렇게 모든 하위 문제들이 해결되고나면 최종 해결 프로세스인 첫 main 함수로 되돌아와야 한다. 

 

즉, 스택 자료구조의 이상한 처리 방식은 그 배후에 위와 같은 문제 해결 및 분해 메커니즘이 숨어 있는 것이다.

 

 

깊이 우선 탐색(DFS) 알고리즘에서 중요한 것은 스택을 사용한다는 점이다. 깊이 우선 탐색 알고리즘은 사실상 main 함수에서 시작해 하위 모듈을 호출해나가는 프로그램의 제어 흐름 구조 및 그것을 위한 프로세스의 콜 스택 구조와 다를 것이 없다. 원리가 똑같다. 다만 그래프에서 노드는 보통 데이터(혹은 그것을 가리키는 포인터)가 저장되는 반면, 콜 스택은 노드가 함수(처리)를 상징한다는 점이 다를 뿐이다. 

 

스택에서 말하는 거꾸로, 혹은 역산한다는 말의 본질은 분할(division)이 아니라 분해(decomposition)에 가까운 방식을 말한다. 공부 계획에서 역산은 큰 목표에 부여된 할당량을 D-Day에서 남은 시간만큼 단순 분할한다. 나눗셈이다. 계획표는 분할된 것을 우선순위 및 순서에 따라 재정렬할 뿐이다. 문제의 규모만 다를 뿐, 같은 차원에 속한다.

 

그러나 컴퓨터에서 프로그램이란 문제를 분해한다. 계층적이고 추상적으로 분해한다. main 함수의 내용은 처음부터 큰 문제의 솔루션 그 자체다. 그러나 세부사항을 숨긴다. 세부적인 솔루션은 하위 모듈이 처리해야 한다. 제어흐름이 넘어간다. 그러나 결국 그것을 호출한 최상위 모듈로 차근차근 돌아와야 한다. 왜냐하면 그것이 최종 솔루션을 담고 있기 때문이다.

 

물론 스택이 반드시 문제 해결 프로세스에서 데이터를 tracking 하는데만 사용되는 것은 아니다. 데이터 단순 적재의 용도로도 충분히 사용할 수 있다. 사용자의 히스토리를 저장하고 최근 저장된 것을 우선적으로 사용하고 싶을 때 그렇다.

 

그러나 알고리즘적으로 스택이 사용되는 경우, 계층적 분해하고 분해된 하위 문제를 처리해나가고 나중에 최종 솔루션으로 되돌아오는 구조의 문제에서는 스택이 활용된다.

 

계산기 프로그램도 마찬가지다. 연산자에 우선순위가 있다. *, / 는 +, - 보다 더 우선순위가 높다. ()는 임의적으로 우선순위를 높여준다. 우선순위가 높다는 것은 겉으로 들으면 마치 그것이 더 중요한 일부분처럼 들린다. 그러나 우선순위가 높은 것들은 계층적으로 하위 문제에 속한다. *, /, () 문제들을 전부 풀고나면 계산 문제는 아주 간단한 +, - 문제다. 이것이 최종 솔루션 계층에 속한다. 사칙연산은 트리로 만들 수 있다.

 

계산기에서 스택을 사용하는 이유도 계산이 이렇게 계층적으로 솔루션이 분해된 구조이기 때문이다. *와 같이 우선순위가 높은, 즉 하위 처리를 만나게 되면 그 처리를 먼저 해야 한다. 제어 흐름을 넘겨야 한다. 처리한 뒤 결과를 +, -가 속한 상위 프로세스에 넘겨야 한다. 따라서 일단은 스택에 쌓아야 한다.

 

Operator 스택은 계층적인 처리를 상징한다. +보다는 *를, * 보다는 또 어떤 우선순위가 높은 연산을 하라는 것이다. 만약 Operator 스택에 쌓인 처리보다 우선순위가 낮은, 즉 계층적으로 높은 처리 단계가 들어온다면 제어 흐름이 위로 복구될 타이밍이라는 뜻이므로 더 이상 하위 연산을 호출하지 않는다. 바로 그때가 해당 차원의 문제를 처리해 결과를 계산하는 타이밍인 것이다.