[Data Structure] 스택오버플로우로 알아보는 stack과 recursion

스택오버플로우라는 사이트가 있다.

이 사이트는 기적과도 같은 곳이다.

전세계 모든 개발자들이(영어를 못해도) 그저 찾아뵙고 주기적으로 문안인사 올리는 곳이랄까..

심지어 개발자를 꿈꾸는 나조차 거의 주기적으로 찾아뵙고 인사 올리고 있으니..

암턴 거기에 있는 Stack이 오늘 다룰 이 Stack이다.

 

그래서 말나온김에 Stack overflow 라는 의미가 어떤 것인지 살펴보자.

stack은 자료 구조의 한 종류인데,

이 stack에서 원래 할당된 메모리 공간보다 많은 데이터가 들어갈 경우 이를 받아들이지 못하고 오류가 발생하는 것을 의미한다.

stack의 크기를 초과해서 계속해서 데이터를 쌓아버리게 되면 stack overflow라는 에러를 내면서 프로그램이 약간 자신의 본분을 다 하지 못하게 되어버리는 상황인 것이다. 

이것이 [스택 오버 플로우] 다. 

두둥.. No하면 어떻게 되나요..

stack; First In Last Out

나중에 들어온 것이 먼저 나가는 구조를 가지고 있다.

예제로 들어보면,

1. 접시가 쌓여있을 경우 - 누가 중간을 툭 쳐서 가뿐히 내던지는 묘기를 선보이지 않는 한 항상 나중에 쌓인 접시가 먼저 나가는 구조다.(last in first out) 당연히 제일 먼저 쌓였던 접시는 제일 나중에 나가게 된다.(first in last out)

2. 프링글스를 먹는 경우 - 프링글스를 기이한 방법으로 먹지 않는 이상 자연스럽게 가장 나중에 포장(?)된 것들을 먼저 입속으로 집어 넣게된다.

3. 엑셀에서 ctrl+z 하는 경우 - 실행취소하여 이전 단계로 돌아가고 싶을 때 가장 나중에 한 작업이 먼저 나온다.

4. 브라우저에서 뒤로가기 하는 경우 - 마지막으로 봤던 브라우저가 뒤로가기하면 먼저 나온다.

입력은 push, 출력은 pop으로 하고, peek이라는 top위치 데이터를 가질 수 있다.

 

함수가 함수를 호출하거나 자기 자신을 호출하는 것도 스택 기반이라고 한다.

 

재귀함수는 함수 내에서 자기 자신을 계속해 호출하는 함수를 말하는데,

종료 조건을 설정해주지 않으면 계~속 해서 본인을 호출하기 때문에 주의해야 한다.

재귀가 스택 기반이라고 하는것은 아래처럼 설명할 수 있다.

함수(A)라는 것이 호출되면 스택에 일단 A가 쌓인다.
그런데 함수 A를 실행하는 중에 a값을 넣어 함수를 실행하라고 한다.

그럼 실행중이던 함수가 끝나기 전, 함수(a)를 넣어 다시 실행하고

함수 a는 A위에 쌓인다.