스택(자료구조) (r0 버전으로 되돌리기)

[목차]

{{{+2 Stack}}}
== 개요 ==
후입선출(後入先出/Last In First Out—LIFO)[* 여기서 Last니 First니 하는 것은 스택에 데이터가 드나드는(출입하는) 순서를 말한다. 풀어 쓰면 '나중에 들어온 데이터가 먼저 나간다.' 선입후출(先入後出/First In Last Out—FILO)이라고도 하지만 어차피 의미는 같다.] 특성을 가지는 [[자료구조]](Data Structure)를 일컫는다. 메모리에 새로 들어오는 데이터의 위치가 메모리 말단(일명 '탑 포인터')이고[* Top Pointer. 그냥 탑(Top)이라고도 한다. 후입선출이라는 특성상 가장 먼저 빠져나갈 데이터의 위치이기도 하다.], 써먹기 위해 내보내는 데이터 역시 메모리 말단을 거친다. 스택의 추상자료형(Abstract Data Type—ADT)을 살펴보면, 입력연산은 푸시(Push), 출력연산은 팝(Pop)이라고 부른다. 조회연산은 피크(Peek)라고 하는데, 탑 포인터가 가리키는 데이터를 조회(확인)만 할 뿐, 탑의 순번(順番/인덱스—Index)은 변화시키지 않는 연산을 의미한다.

스택의 역사를 짚어 보면 1946년 [[앨런 튜링]](Alan Turing)까지 거슬러 올라간다. 당시 앨런 튜링은 서브루틴을 호출하는 과정을 베리(bury), 되돌아오는 과정을 언베리(unbury)라고 불렀는데, 이 것을 스택의 기원이라고도 한다. 스택은 콜 스택(Call Stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조에도 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소를 삽입하고자 할 때 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 개발자들이 즐겨 이용하는 질의응답 서비스 사이트인 [[https://stackoverflow.com/|스택 오버플로]]의 명칭 또한 여기서 유래했다.[* [[https://www.onlybook.co.kr/entry/algorithm-interview|<파이썬 알고리즘 인터뷰>]] p.242, 책만, 2020]

쉽게 말해 스택은 '쌓여있는 팬케이크'를 생각하면 된다.
우리가 [[팬케이크]](핫케이크)를 만들어 먹는다고 가정을 하자. 우리는 프라이팬에 [[버터]]를 두르고 팬케이크를 따끈따끈하게 구워내기 시작했으며 이제 팬케이크를 그릇 위에 옮길 것이다.
잘 구워진 팬케이크 하나, 살짝 탄 팬케이크 하나, 덜 익은 팬케이크 하나... 이렇게 팬케이크를 쌓던 도중, 우리의 팬케이크를 유심하게 지켜보던 아이가 '팬케이크'를 하나 달라고 한다. 그럼 어떻게 팬케이크를 줄 것인가?

당연히 사회통념적인 생각적으로 '쌓던 팬케이크 중에서 맨 위에 있는 팬케이크를 줄 것이다.'
우리는 팬케이크 굽는 것을 멈추고 그릇에 쌓여있던 팬케이크 중 막 구워진 가장 위에있는 팬케이크를 아이에게 줄 것이다.
이는 즉 위에서 설명하였던 Last In Fisrt Out(LIFO)가 된다. 가장 나중에 (그릇에)올라온 것이 가장 먼저 나가게 되는 것이다.

스택은 '''힙 영역 메모리에서 일반적인 데이터를 저장하는 스택'''과 '''스택 영역 메모리에서 프로그램의 각 분기점에 변수와 같은 정보를 저장하기 위한 스택'''이라는 두 가지 의미로 사용될 수 있므로 유의해야 한다.

이것도 종류를 나눌 수 있는데,
'''Ascending stack''' VS '''Descending stack'''
'''Empty stack''' VS '''Full stack''' 
[[http://www-mdp.eng.cam.ac.uk/web/library/enginfo/mdp_micro/lecture5/lecture5-4-2.html|으로 종류가 나뉜다. ]]
== 구현 ==
스택은 후입선출(Last In First Out) 개념이다. 선입선출인 [[큐(자료구조)|큐]]와 비교된다. 구현은 큐나 링크드 리스트와 같은 다른 자료형에 비해 쉬운편이다.

[[배열]]을 이용해서 구현할 때를 예로 들어보자. 처음으로 스택을 위한 배열을 하나 잡아 놓고, index 값을 0으로 잡는다.[* 변수 이름을 top이라고 설정하기도 하고, 초기값을 -1로 잡은 후 전위연산을 통해 구조를 만들 수도 있다.] index가 0이면 스택이 비어 있는 것이고, 스택에 뭔가를 집어넣을 때는 index의 자리에 집어넣고 index를 하나 올리면 된다. index가 초기 배열 크기 이상이면 스택이 꽉 찬 것이다. 스택에서 뭔가를 뺄 때는 index에 있던 값을 돌려주고 index를 하나 뺀다.

[[연결 리스트]]로 구현하는 방법은 보다 단순하다. 메모리 상에 아이템을 위한 공간을 할당하고 새로운 아이템이 추가될 때 마다 포인터로 연결하기만 하면 된다. 아래 그림에서 좌측 ADT는 스택의 연산을 지원하기 위해 1부터 5까지 각 요소가 접시 쌓듯 차곡차곡 놓이겠지만, 실제로 연결 리스트로 구현하게 된다면 물리 메모리 상에는 순서와 관계 없이 여기저기에 무작위로 배치되고 포인터로 가리키게 될 것이다.

[[파일:3-9-1.png|width=300]]

== 응용 ==
구현이 쉬운 녀석이 응용할 건덕지도 매우 많다. 예를 들어서 [[함수(프로그래밍)|함수]]가 함수를 호출하거나 [[재귀함수|자기 자신을 호출하는 것도]][* 재귀함수는 함수 내에서 자기 자신을 계속해 호출하기 때문에 종료조건을 잘 설정해주지 않으면 빠져나오지 못해 프로그램에 심각한 문제가 생긴다. 그러한 문제와 가독성의 이유 때문에 많이 쓰지 않는 편이다. 대부분의 재귀함수는 반복문으로 치환하여 사용하는 것이 가능하며, 많은 때에 쓰기도 알아보기도 쉬운 반복문이 더 효율적이다. 하지만 [[하노이의 탑]]과 같은 몇몇 문제에서는 재귀함수를 이용하여 해결하는 것이 더 간단해서 재귀함수가 보편적으로 사용된다.] 스택에 기반을 두고 있다.

비전공자가 가장 와닿는 영역은 [[undo]]. 그러니까 Ctrl + Z. 가장 최근에 실행한 명령어를 취소해야하기 때문에 마지막에 들어간 자료가 먼저 나오는 스택 구조가 효율적이다.

대부분의 현대 [[CPU]]는 [[어셈블리어]]에 스택 영역을 제어하는 명령이 있다. 한 프로그램이 사용하는 스택 영역은 기본적으로 크기가 고정되어 있다.[* 이 스택은 정적 할당되므로 런타임 환경에서 변경하는것이 불가능하며 컴파일시 이 스택 크기를 지정하여야 한다. 예를 들어 MSVC의 기본 스택 크기는 1MB이며 [[https://docs.microsoft.com/en-us/cpp/build/reference/f-set-stack-size?view=msvc-170|{{{/F}}}]] 옵션을 통해 이 크기를 변경할 수 있다.] 실행되거나 기다리고 있는 여러 함수 등 각 분기점에서, 함수에서 사용되는 변수와 같은 정보를 이러한 명령어를 통해 추가하고 삭제한다. 이를 이해하지 못하고 스택 영역 변수나 메모리를 함부로 사용하면 잘못된 데이터가 씌워져 이상한 값을 출력하거나 문제를 일으킬 수 있다.

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

그런 뒤 bar에 해당하는 연산이 종료되고 bar의 스택 프레임 내부의 값들이 하나씩 빠져나오면서 끝으로 출력 데이터가 리턴값을 받기 위한 공간으로 들어오게 된다. 다시 말해 함수가 호출될 때마다 스택에 값들이 쌓이고, 계산이 끝나면 다시 하나씩 빼면서 출력값이 가장 밑에 있던 리턴 공간으로 돌아오는 것이다. 이 개념을 잘 이해하면 재귀가 연산속도에서 불리한 점이 발생함을 알 수 있다. 재귀도 일반 함수 호출과 다를 것 없이 한번 재귀 호출이 이루어질 때마다 계속 스택을 쌓아나가므로 최종 결괏값을 되돌려 받으려면 쌓인 스택을 전부 다시 빼내야 하기 때문이다. 따라서 [[재귀함수|재귀 알고리즘]]을 사용할 때는 반드시 재귀 알고리즘이 필요한지 설계를 먼저 정확히 하는 것이 중요하다.
== 기타 ==
스택을 흔히 크기를 고정하여서 사용하기 때문에, 이를 다 사용하면 [[오버플로|넘치게 된다]]. 이에 대한 적당한 대처방안이 준비되어 있지 않으면 다른 메모리 영역을 침범할 수 있게 된다.--팬케이크가 그릇에 쌓이다 못해 넘어지면서 옆의 매운탕 그릇으로(...)-- 이런 현상 또는 이를 이용한 해킹 기법이 [[버퍼 오버플로|스택 오버플로]]이다.

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

[[분류:자료구조]]
스택(자료구조) (r0 버전으로 되돌리기)

캡챠
