Stack

==========================================================================
이 글은 이론적으로 아는 것을 직접 설명 및 구현을 해 봄으로써 제 자신의
실력을 다지기 위한 글 입니다. 물론 정확한 이론. 용어도 아님을 밝힙니다.
이 글을 직.간접적으로 사용함으로써 발생되는 모든 불이익을 책임지지 않습니다.

문의점, 오류, 잘못된 용어들은 저의 홈페이지 Work 게시판을 이용하여 주시고
이상의 사항에 대하여는 최대한 덧글 ( 코멘트 ) 를 이용해 주십시오.

본 글은 저의 홈페이지인 http://ggaman.com 과
싸이월드의 (JPSC) JAVA program study club 에서 보실수 있습니다.

homepage : http://ggaman.com , e-mail n MSN : chan at ggaman.com

20030825 - Chan
==========================================================================


Stack ( 이하 스택 ) 이란?

스택이란 자료구조의 하나로 입력과 출력이 한 군데 있으므로 바구니와 같이 비교하곤 한다.
( 어떤 책에서는 크리스마스 산타클로스 할아버지의 선물 자루에 비교를 하기도한다. )

보통 그림을 그린다면 아래와 같이 위가 뚫린 칸이 있는 세로 구조물(?)을 그리곤한다.



입력과 출력은 제일 위의 뚫린 곳을 통해서 데이터를 빼거나 넣게 된다.
입력과 출력이 한군데에 있으므로해서 가장 처음 들어간 자료가 제일 아래에 위치하게 된다.
( 그림에서는 1번 칸에 들어 간다. )

위의 그림에서는 총 3개의 자료를 넣어서 현재 3번까지 자료가 들어 있다.
여기서 자료를 하나 뽑아 내면 제일 위에 있는 3번의 자료가 빠져 나온다.

즉 제일 나중에 넣었던 자료가 제일 처음 빠져 나오는것이다.
( 제일 처음 들어간 자료는 제일 마지막에서야 나올수 있다. )
( FILO : First In Last Out    라고 부른다. )




용어 설명 ( 공식적인 용어가 아님을 밝힌다. )

bottom : 스택의 바닥을 뜻한다.
top : 현재 자료가 들어 있는 위치를 말한다.
size : 스택의 꼭대기를 뜻한다.
POP :  스택에서 현재 포인터에 있는 자료를 꺼낸다.
           ( 현재 포인터에 있는 자료를 꺼내면 현재 포인터는 한칸 아래 ( 즉 2 ) 를 가르킨다.
PUSH : 스택에 자료를 넣는다. ( 자료가 들어가면 현재 포인터가 한칸 위를( 즉 4 ) 가르킨다.      
오버플로우 : 스택이 가득 찼을때 ( 즉 현재 포인터가 5을 가르킬때 ) PUSH 작업을하면
                   더이상 스택에 자료를 넣지 못하는 현상을 뜻한다.
언더플로우 : 스택에 자료가 하나도 없을때 ( 즉 현재 포인터가 0을 가르킬때 ) POP 작업을 하면
                   스택에 더이상 자료가 없기 때문에 자료를 꺼내지 못하는 현상을 뜻한다.




구현 방법 :

자료를 뺄때는 자료가 있는지 확인하고 자료를 넣는다. ( 언더 플로우 예방 )
단 자료를 빼고 난 뒤에는 현재 포인터를 하나 줄여 준다.

자료를 넣을때는 스택이 가득 찼는지 확인하고 자료를 넣는다. ( 오버 플로우 예방 )
단 자료를 넣고 난 뒤에는 현재 포인터를 하나 더해 준다.



사용하는 곳 :

스택은 가장 최근에 들어온 자료가 가장 마지막에 나가야 함으로
주로 프로그램 내에서 함수를 호출 할때 사용된다.
( 함수 호출이라 함을 함수를 호출한 위치를 저장하기도 하지만 )
( 각종 언어에서 함수 호출시 그 안의 지역 변수 부분에 쓰인다. )

아래는 C 에서 사용하는 지역 변수에서 어떤 식으로 같은 이름의 변수가
지역에서 동작하는지 보여주는 예이다.

아래 예는 정확하지 않을수도 있음을 다시한번 밝힌다.



위의 예에서는 main 에서 a를 잡고 main - a 가 있는 상태에서
함수 func1 에서 다시 a를 잡고 다시 main - a가 있고 func1 - a 가 있는 상태에서
함수 func2 에서 다시 같은 이름의 a를 잡는 예제이다.

보다 시피 func2 까지 왔을때 a = 7 이라고 했을때 스택의 가장 위쪽에 있는 a를 찾고
그곳에 7을 할당하게 되어 있다.

그렇기 때문에 func1과 main에 있는 a는 숨겨지게 되어 있다.

static 변수를 사용한다면 그것은 프로그램이 끝나기 전까지 유지되므로
프로그램이 끝나기 전까지 스택에서 사라지지 않게 된다.

물론 위의 예제에서 func2위에 int b 가 들어 갔을때 a 라는 값을 이용할때는
스택의 현재 위치에서 아래로 내려가면서 같은 이름의 자료를 찾게 된다.
( 즉 func2 에서의 a 라는 값이 사용되게 되어 있다. )