stack에 저장된 data 항목들 중에 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제된다. 그래서 stack을 후입 선출 리스트(Last- In-First-Out List)라고 부른다.
새로운 함수가 호출되면, return 될 때 어디로 돌아가야 할지를 알아야 하고, 넘어온 parameter에 대해서도 저장해 놓아야 하며, 함수 안에서 선언된 변수들도 저장해야 한다.
함 수 호출시 이러한 정보를 묶어서 stack에 집어넣는다. 함수 수행도중 또 다른 함수가 불리면, 해당 함수의 정보도 stack에 넣는다. 만일 함수내부수행이 끝나서 return이 되면, 해당 함수에 관련된 자료는 필요가 없게 되어 stack에서 꺼낸다.
stack의 구조상 다음 꺼낼 차례는 방금 return 된 함수를 호출한 함수이다. 그러므로 호출한 함수의 정보를 읽어 함수내부의 그 다음 줄을 계속 수행할 수 있다.
이런 식으로 stack에 넣고(push) 빼는(pop)일련의 작업들을 하면서 프로그램이 돌아가게 된다.
책 에서 보면 stack영역에 저장되는 변수의 내용은 local변수 혹은 지역변수라고 하는 스코프를 벗어나면, 사라진다고 하는데 위에서 설명한 것처럼 return 된 함수의 내용을 stack에서 꺼내 버리기 때문에 없어지는 것이다. 하지만, 필요에 의해서 malloc 또는 new를 이용하거나, static으로 선언한 경우에는 이러한 호출stack에 data를 저장하지 않는다. 따로 그 변수만을 위한 메모리의 공간을 할당하여, 함수들이 호출이 되든 return이 되든 data가 유지될 수 있도록 한다. 이러한 할당 공간을 heap이라고 부른다.
<stack의 구조>
Heap 은 여러개의 노드들 가운데서 가장 큰 키 값을 가지는 노드나 가장 작은 키 값을 가지는 노드를 빠른 시간내에 찾아내도록 만들어진 자료 구조이다. heap은 완전 이진 트리의 하나로서 각각의 노드는 유일한 키 값을 가진다. Heap은 다른 말로 Priority Queue라고 한다.
Priority Queue는 값들의 콜렉션으로부터 가장 큰 값을 신속하게 찾거나 제거할 필요가 빈번하게 발생하는 상황에서 유용하게 사용할 수 있다. 즉, 중요도에 따라 수행할 작업들을 정리하고, 가장 급박한 것을 골라 수행한다.
