스택(자료구조)

Stack

1 개요

후입선출(後入先出, Last In First Out; LIFO)의 자료구조.[1] 데이터 저장소에서 새로 들어오는 데이터의 위치가 저장소의 끝 부분(Top 혹은 Top pointer라고 한다)이고, 써먹기 위해 내보내는 데이터 역시 저장소의 끄트머리에서 나간다. 입력은 push, 출력은 pop이다. peek는 Top의 위치에 있는 데이터를 확인하는 것을 말한다.

쉽게 설명하자면, 스택은 일종의 바닥이 막힌 상자라고 보면 된다. 나중에 넣은 물건이 위에 있으므로 먼저 꺼낼 수 밖에 없다.

이것도 종류를 나눌 수 있는데, 캠릿브지 대학의 강자의료에 따르면,
Ascending stack VS Descending stack
Empty stack VS Full stack
으로 종류가 나뉜다.

2 구현

매우 쉽다. 큐처럼 메모리 누수로 인해 머리 빠개질 일도 없고, 메모리상에 표현하는 방식도 단순히 배열을 사용하는 것부터 동적인 메모리 활용을 위해 연결 리스트를 기초 구조로 하는 경우도 있다. C++ 등지에서는 기초 자료 구조로 덱을 사용한다.

배열을 이용해서 구현할 경우를 예로 들어보자. 일단 스택을 위한 배열을 하나 잡아 놓고, index 값을 0으로 잡는다. index가 0이면 스택이 비어 있는 것이고, 스택에 뭔가를 집어넣을 때는 index의 자리에 집어넣고 index를 하나 올리면 된다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것. 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다. 참 쉽죠?

3 응용

구현이 쉬운 녀석이 응용할 건덕지도 매우 많다. 예를 들어서 함수가 함수를 호출하거나 자기 자신을 호출하는 것도[2] 스택에 기반을 두고 있다. 인텔 X86계열 CPU의 경우 아예 어셈블리어에 스택 영역을 제어하는 명령이 있다.[3] 그러나, 재귀함수가 스택 오버플로우 같은 경우로 답이 없을 경우는 스택을 쓸 수도 있다.

4 기타

스택 문서에도 나와 있지만, 매직 더 개더링에서 체인 시스템에 대응하는 "스택" 시스템도 여기서 이름을 따온 것으로 추정된다. 역시 공돌이...

스택을 일반적으로 크기를 고정하여서 사용하기 때문에, 이를 다 사용하면 넘치게 된다. 이에 대한 적당한 대처방안이 준비되어 있지 않으면 다른 메모리 영역을 침범할 수 있게 된다. 이런 현상 또는 이를 이용한 해킹 기법이 스택 오버플로이다.

여담으로, 게임 상에서 중첩되는 효과를 보고 '스택'이라고 칭하는 경우가 있는데, 자료구조에서 스택과의 공통점은 뭔가 계속 쌓인다는 것밖에 없다(...). LIFO도, peek를 할 필요도 없는데 이 개념은 오히려 카운터가 더 적절하다. 그러나 게임상에서 카운터는 '무언가의 대항마'라는 뜻을 가지고 있기도 하기에 일부러 스택이라는 단어를 쓴 것으로 추정된다.

추가로 많은 컴퓨터과학,공학 학부에서는 배열이나 리스트로 Stack의 구현에 집중을 많이하는데 LIFO의 추상적인 개념을 잘 이해하는것도 중요하다. 스택이라는 자료구조는 프로세스를 구성하는 4개의 요소중 한 부분이며 함수의 호출에 관여한다.

어떤 함수든 호출되는 순간 스택에 그 함수를 위한 영역 (스택 프레임 stack frame) 이 할당되는데, 어떤 함수 foo()가 호출된 상태에서 foo()가 다시 다른 함수 bar()를 호출하는 상황을 생각해 보자. 우선 스택 내부 foo()에 해당되는 프레임에 데이터가 쌓여 있을 것이다. bar()가 호출되면 우선 bar가 받는 인수들이 푸시되고, 그 다음 bar의 리턴값을 받을 공간이 푸시된다. 그 위로 bar에 해당하는 새로운 스택 프레임이 할당되고, 그 프레임 내부에 bar의 내부 변수들이 푸시되게 된다.

그런 뒤 bar에 해당하는 연산이 종료되고 bar의 스택 프레임 내부의 값들이 하나씩 빠져나오면서 최종적으로 출력 데이터가 리턴값을 받기 위한 공간으로 들어오게 된다. 다시 말해 함수가 호출될때마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다. 이 개념을 잘 이해하면 재귀가 연산속도에서 불리한점이 발생함을 알 수 있다. 재귀도 일반적 함수 호출과 다를 것 없이 한번 재귀 호출이 이루어질때마다 계속 스택을 쌓아나가므로 최종 결과값을 되돌려받으려면 쌓인 스택을 전부 다시 빼내야 하기 때문이다. 따라서 재귀 알고리즘을 사용할 때는 반드시 재귀알고리즘이 필요한지 설계를 먼저 정확히하는것이 중요하다.
  1. ↑ 여기서 Last니 First니 하는 것은 스택에 들어온 순서를 말한다. First In Last Out이라고도 하지만 어차피 의미는 같다.
  2. ↑ 이를 재귀함수라고 한다. 재귀함수는 함수 내에서 자기 자신을 계속해 호출하기 때문에 종료조건을 잘 설정해주지 않으면 빠져나오지 못해 프로그램에 심각한 문제가 생긴다. 그러한 문제와 가독성의 이유 때문에 많이 쓰지 않는 편인데, 거의 대부분의 재귀함수는 반복문으로 치환하여 사용하는 것이 가능하며 많은 경우 쓰기도 알아보기도 쉬운 이 편이 더 효율적이다. 그리고 하노이의 탑과 같은 문제는 재귀함수를 이용하여 해결하는 것이 보편적이다.
  3. ↑ 사실 현대 프로세서들은 거의 전부 스택 관련 명령을 가지고 있다.