Stack
1. 개요
우선 이 문서에는 메모리 영역으로서의 스택과, 자료 구조로서의 스택에 대한 설명이 혼용되어 있으니 주의 바람.후입 선출(後入先出/Last In First Out—LIFO)[1] 특성을 가지는 자료 구조(Data Structure)를 일컫는다. 메모리에 새로 들어오는 데이터의 위치가 메모리 말단(일명 '탑 포인터')이고[2], 써먹기 위해 내보내는 데이터 역시 메모리 말단을 거친다. 스택의 추상 자료형(Abstract Data Type—ADT)을 살펴보면, 입력 연산은 푸시(Push), 출력 연산은 팝(Pop)이라고 부른다. 조회 연산은 피크(Peek)라고 하는데, 탑 포인터가 가리키는 데이터를 조회(확인)만 할 뿐, 탑의 순번(順番/인덱스—Index)은 변화시키지 않는 연산을 의미한다.
스택의 역사를 짚어 보면 1946년 앨런 튜링(Alan Turing)까지 거슬러 올라간다. 당시 앨런 튜링은 서브루틴을 호출하는 과정을 베리(bury), 되돌아오는 과정을 언베리(unbury)라고 불렀는데, 이 것을 스택의 기원이라고도 한다. 스택은 콜 스택(Call Stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료 구조에도 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이 외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 개발자들이 즐겨 이용하는 질의응답 서비스 사이트인 스택 오버플로의 명칭 또한 여기서 유래했다.[3]
스택은 힙 영역 메모리에서 일반적인 데이터를 저장하는 스택과 스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택이라는 두 가지 의미로 사용될 수 있므로 유의해야 한다.
이것도 종류를 나눌 수 있는데,
Ascending stack VS Descending stack
Empty stack VS Full stack
으로 종류가 나뉜다.
2. 구현
스택은 후입 선출(Last In First Out) 개념이다. 선입 선출인 큐와 비교된다. 구현은 큐나 링크드 리스트와 같은 다른 자료형에 비해 쉬운 편이다.배열을 이용해서 구현할 때를 예로 들어보자. 처음으로 스택을 위한 배열을 하나 잡아 놓고, index값을 0으로 잡는다.[4] index가 0이면 스택이 비어 있는 것이고, 스택에 뭔가를 집어넣을 때는 index의 자리에 집어넣고 index를 하나 올리면 된다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것이다. 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.
연결 리스트로 구현하는 방법은 보다 단순하다. 메모리상에 아이템을 위한 공간을 할당하고 새로운 아이템이 추가될 때마다 포인터로 연결하기만 하면 된다. 아래 그림에서 좌측 ADT는 스택의 연산을 지원하기 위해 1부터 5까지 각 요소가 접시 쌓듯 차곡차곡 놓이겠지만, 실제로 연결 리스트로 구현하게 된다면 물리 메모리상에는 순서와 관계없이 여기저기에 무작위로 배치되고 포인터로 가리키게 될 것이다.
3. 응용
구현이 쉬운 녀석이 응용할 건덕지도 매우 많다. 예를 들어서 함수가 함수를 호출하거나 자기 자신을 호출하는 것도[5] 스택에 기반을 두고 있다.비전공자가 가장 와닿는 영역은 undo. 그러니까 Ctrl + Z. 가장 최근에 실행한 명령어를 취소해야 하기 때문에 마지막에 들어간 자료가 먼저 나오는 스택 구조가 효율적이다.
대부분의 현대 CPU는 어셈블리어에 스택 영역을 제어하는 명령이 있다. 한 프로그램이 사용하는 스택 영역은 기본적으로 크기가 고정되어 있다.[6] 실행되거나 기다리고 있는 여러 함수 등 각 분기점에서, 함수에서 사용되는 변수와 같은 정보를 이러한 명령어를 통해 추가하고 삭제한다. 이를 이해하지 못하고 스택 영역 변수나 메모리를 함부로 사용하면 잘못된 데이터가 씌워져 이상한 값을 출력하거나 문제를 일으킬 수 있다.
이를 좀 더 쉽게 설명해 보자. 어떤 함수든 호출되는 순간 스택에 그 함수를 위한 영역(스택 프레임 stack frame)이 할당되는데, 어떤 함수 foo()가 호출된 상태에서 foo()가 다시 다른 함수 bar()를 호출하는 상황을 생각해 보자. 우선 스택 내부 foo()에 해당되는 프레임에 데이터가 쌓여 있을 것이다. bar()가 호출되면 우선 bar가 받는 인수들이 푸시되고, 그 다음 bar의 리턴값을 받을 공간이 푸시된다. 그 위로 bar에 해당하는 새로운 스택 프레임이 할당되고, 그 프레임 내부에 bar의 내부 변수들이 푸시된다.
그런 뒤 bar에 해당하는 연산이 종료되고 bar의 스택 프레임 내부의 값들이 하나씩 빠져나오면서 끝으로 출력 데이터가 리턴값을 받기 위한 공간으로 들어오게 된다. 다시 말해 함수가 호출될 때마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다. 이 개념을 잘 이해하면 재귀가 연산 속도에서 불리한 점이 발생함을 알 수 있다. 재귀도 일반 함수 호출과 다를 것 없이 한번 재귀 호출이 이루어질 때마다 계속 스택을 쌓아나가므로 최종 결괏값을 되돌려받으려면 쌓인 스택을 전부 다시 빼내야 하기 때문이다. 따라서 재귀 알고리즘을 사용할 때는 반드시 재귀 알고리즘이 필요한지 설계를 먼저 정확히 하는 것이 중요하다.
휴렛팩커드(HP)의 공학용 계산기들은 RPN 방식 계산을 항상 지원하는데, 전통적으로 여기에 필요한 숫자를 4개 크기 스택에 담아왔다(X, Y, Z, T; X가 항상 top인데, 계산기 특성상 2줄 이상 표기 시 보통 반대로 아래부터 위로 보여주는 전통을 지녔다). 이 스택을 거의 항상 계산기 주인이 보고 써먹을 수 있었다.
4. 기타
스택을 흔히 크기를 고정하여서 사용하기 때문에, 이를 다 사용하면 넘치게 된다. 이에 대한 적당한 대처 방안이 준비되어 있지 않으면 다른 메모리 영역을 침범할 수 있게 된다. 이런 현상 또는 이를 이용한 해킹 기법이 스택 오버플로이다.많은 컴퓨터 과학, 공학 학부에서는 배열이나 리스트로 스택의 구현에 집중을 많이 하는데 LIFO의 추상적 개념을 잘 이해하는 것도 중요하다. 스택이라는 자료 구조는 프로세스를 구성하는 4개의 요소 중 한 부분이며 함수의 호출에 관여한다.
[1]
여기서 Last니 First니 하는 것은 스택에 데이터가 드나드는(출입하는) 순서를 말한다. 풀어 쓰면 '나중에 들어온 데이터가 먼저 나간다.' 선입 후출(先入後出/First In Last Out—FILO)이라고도 하지만 어차피 의미는 같다.
[2]
Top Pointer. 그냥 탑(Top)이라고도 한다. 후입 선출이라는 특성상 가장 먼저 빠져나갈 데이터의 위치이기도 하다.
[3]
<파이썬 알고리즘 인터뷰> p.242, 책만, 2020
[4]
변수 이름을 top이라고 설정하기도 하고, 초깃값을 -1로 잡은 후 전위 연산을 통해 구조를 만들 수도 있다.
[5]
재귀 함수는 함수 내에서 자기 자신을 계속해 호출하기 때문에 종료 조건을 잘 설정해 주지 않으면 빠져나오지 못해 프로그램에 심각한 문제가 생긴다. 그러한 문제와 가독성의 이유 때문에 많이 쓰지 않는 편이다. 대부분의 재귀 함수는 반복문으로 치환하여 사용하는 것이 가능하며, 많은 때에 쓰기도 알아보기도 쉬운 반복문이 더 효율적이다. 하지만
하노이의 탑과 같은 몇몇 문제에서는 재귀 함수를 이용하여 해결하는 것이 더 간단해서 재귀 함수가 보편적으로 사용된다.
[6]
이 스택은 정적 할당되므로 런타임 환경에서 변경하는것이 불가능하며 컴파일 시 이 스택 크기를 지정하여야 한다. 예를 들어 MSVC의 기본 스택 크기는 1MB이며
/F 옵션을 통해 이 크기를 변경할 수 있다.