[자료구조] Stack(스택), Stack Overflow
피드백과 정보 정정 댓글은 환영입니다 :)
오랜만에 티스토리에 글 쓰러 와보았다! 마지막 게시물에 1월 초인것을 보아하니 반성해야 될 감이;; 갑자기 스택에 대한 내용을 쓰기로 결심한 이유는 바로~
지금 작업하고 있는 코드에서 스택 오버플로우 에러가 너무 많이 나서... 아마 이유는 과도한 재귀 함수 호출인 것 같아서...
본질부터 꿰뚫어보고자 기초 지식을 쌓기로 하였답니다 ㅎㅎ
1) Stack이란?
스택은 후입선출의 구조를 갖는 자료구조이다. 우리가 부추전을 여러장을 구워 쌓아놓았을 때, 가장 먼저 먹을 수 있는 전은 가장 위에 있는, 즉 이제 막 구워진 전인 것처럼 나중에 넣은 값이 가장 먼저 나오는 LIFO(Last In First Out) 구조라는 이야기이다. 이렇게 스택에 접근할 수 있는 요소는 제한적이며, 선입선출의 구조를 가진 Queue와는 반대되는 개념이라 할 수 있다.
2) Stack의 기본 연산
스택의 기본 연산에는 크게 세가지가 존재한다.
(1) Push: 스택에 데이터를 넣는 연산 (포인터인 top이 가리키는 자리 위에 메모리를 생성하여 데이터를 가장 위에 위치)
(2) Pop: 스택의 가장 윗부분 데이터를 삭제 후 반환
(3) Stack Top: 스택의 가장 윗 데이터를 반환 (삭제 X)
Push 연산의 경우 컴퓨터에 할당된 스택 영역이 다 차게 되면 Stack Overflow 에러가 발생하게 된다. 이를 활용한 해킹 방식도 있다고 하는데, 자세한 내용은 여기를 참고해보자! Pop 연산의 경우, 스택에 저장된 데이터가 없다면 가장 윗부분 데이터를 삭제 후 반환이 불가능해지며, 이를 underflow라고 일컫는다. 마지막으로 Stack Top 연산은 데이터를 삭제하지 않는 단순 반환 메서드라는 점이 중요하다.
3) Linked List를 통한 스택의 구현
단순 배열에서 스택을 구현하기 위해서는 인덱스를 활용하는 방식을 활용할 수 있다. 연결 리스트를 활용하고자 한다면 포인터를 활용하여 삽입되는 아이템과 그 이전 기준 가장 최근에 삽입된 데이터를 반복적으로 연결해주면 된다. (Python의 경우 스택 모듈이 별도로 존재한다.)
4) Stack의 활용
스택이 가장 많이 활용되며 익숙한 영역은 'ctrl+z' 커맨드일 것이다. 가장 최근에 실행한 명령어를 취소하는 것이기 때문에 Stack에서 가장 최근 데이터를 Pop한다고 생각하면 된다. 또한, 재귀함수나 함수간의 상호 호출도 스택을 기반으로 한다.
5) 재귀함수와 Stack Overflow
def factorial(n):
if n==1:
return 1
else:
return n*factorial(n-1)위와 같이 팩토리얼 값을 계산하는 재귀함수가 있다고 해보자! 해당 함수는 팩토리얼 값을 구하기 위해 수많은 임시값들을 스택에 hold하고 있어야 한다.
위와 같이 n=4일때, factorial(4) 의 값을 얻기 위해서는 factorial(1)의 값에 도달할 때까지 임시 값들이 메모리에 할당되어야 하며, 마지막 함수가 호출되어서야 값이 최초 함수에 차례대로 전달되게 된다. 따라서 재귀를 사용할 때는 스택 오버플로우 에러가 발생하지 않도록 유의해야 한다.
6) 메모리 공간
위와 같이 재귀함수를 과도하게 실행할때 스택 오버플로우 에러가 종종 생기는 이유는 코드를 실행할 때 운영체제로부터 할당되는 메모리 공간이 제한되어 있기 때문이다. 코드를 실행할 때 할당되는 메모리 공간은 크게 4가지가 존재한다.
1) Code: 실행하는 프로그램 코드
2) Data: 전역 변수, 정적 변수
3) Heap: 사용자의 동적할당 (위부터 채워지는)
4) Stack: 함수 호출시 생성되는 지역변수, 매개변수 (아래부터 채워지며, 함수 종료시 자동 소멸)
이중 스택과 힙은 같은 공간을 공유하는데, 이 과정에서 두 영역이 상대 공간을 침범하게 되면 Heap Overflow, 혹은 Stack Overflow가 발생하게 되는 것이다.
7) 꼬리 재귀 (Tail Recursion)
다시 재귀함수로 돌아와서! 결국 재귀함수의 문제는 최종 값이 반환되고 나서야 최초 호출 함수의 값을 반환할 수 있다는 것이다. 따라서 우리는 최종 호출이 끝나고 나서 다시 연산을 하지 않고, 그 상태로 결과만 바로 반환되도록 하는 꼬리 재귀 함수를 구현할 수 있어야 한다.
def factorial(n, total):
if n==1:
return total
else:
return factorial(n-1, n*total)
#초기 total 값은 1
four = factorial(4, 1)위의 코드가 기존 팩토리얼을 꼬리 재귀로 구현한 것이다. 해당 함수의 경우 total이라는 변수를 추가시켜 중간 과정의 값을 별도로 전달하게끔 했고, 결과적으로 n=1에 도달하게 되면 그간 전달받아 계산해온 값을 바로 반환할 수 있게 된다. 즉, 최종값 리턴 후 그 값이 최초의 함수로 전달되는 별도의 과정이 생략된 것이다.
8) ...
작년 2학기에 어떤 과목을 수강하면서 과제로 꼬리 재귀 관련 문제가 나온 적이 있었다. 그때 과제로 엄청나게 많은 양의 재귀가 이루어질 때 이를 효과적으로 해결할 수 있는 방법을 코드로 고안하는 것이 주어졌는데, 그때는 '에이 누가 이렇게 많이 재귀를 쓰는 코드를 쓰나' 했는데 그게 나였다 헤헤 지금 있는 코드들... 꼬리 재귀로 바꿔서 고안하면 조금 나아지려나 하는 희망을 품어보며... 사실 시스템 내에서 할당된 스택의 크기를 늘리면 되긴 하지만 뭔가 재귀에 진 것 같은 느낌이 들어서 ㅎㅎ; 이번달 내로 이겨주겠다 재귀 자식...