[Stack] 스택의 구현

 

stack 이란

stack 구조는 한 쪽끝은 막혀 있고 한 쪽 끝은 뚫려 있는 구조이다. 사실은 실제로 이런 구조가 있는 것이 아니라 이렇게 사용을 한다. 처음 전산학을 공부할 때 스택 스택해서 이런 구조가 실제적으로 존재 하는 줄 알았다.^^

한쪽 끝이 막혀 있는 구조이므로 막히지 않은 쪽에서 자료의 삽입과 삭제가 발생한다. 일상생활에서 스택구조를 보이는 것은 택시의 동전꼽이,책을 쌓을때 등등의 구조에서 볼수 있다.

배열을 사용해서 스택구조를 구현할 수 있다.

stack[6]

아래 그림은 3 개의 데이터가 미리 스택에 삽입된 상태이다. 스택구조에서는 한쪽 끝의 제일 위에서 삽입과 삭제가 발생하므로 제일 끝을 가르키는 변수가 존재하고 이를 보통 top 이란 변수명으로 사용한다.

삽입시

4 번째 위치에 데이터를 삽입하면 되므로 , top 변수를 하나 증가후 새로은 데이터를 삽입.

 top=top+1;
stack[top]=data;

삭제시

3 번째 데이터를 임시변수로 top 변수를 1 감소 하면 되므로

 

data=stack[top]; 
// stack top 에 있는 자료를 data 로 top=top-1; 

overflow ,underflow 검사

• overflow: 자료를 꽉찬 경우 데이터를 삽입하려고 할 때
• underflow: 자료가 빈 경우 데이터를 삭제 하려고 할 때

스택뿐만이 아니라 , 자료의 삭제,삽입 동작에서는 삽입시 데이터를 넣을 공간이 있나, 삭제시에는 가져올 자료가 있나를 검사한후 동작을 취해야 한다. 위의스택에서는 top 값이 5 이면 데이터를 더 이상 넣을 구간이 없는 경우이고 , top 값이 0 이면 빼내올 데이터가 없는 경우이다.

스택에서의 넣는(insert) 동작을 push 라 하고 , 빼는(delete) 동작을 pop라 한다.

push

if (top >=5)
{ 
printf("스택이 넘칩니다"); 
exit(0);//강제 종료 
} 
top=top+1; 
stack[top]=top; 

pop 동작

if (top <=0) 
{ 
printf("스택에 빼낼 데이터가 없습니다"); 
exit(0); 
} 
data=stack[top]; 
top=top-1; 

자주 묻는 질문

1. 스택의 초기 상태는 1 번째 부터 데이터를 넣는다고 하면 top 값을 0 으로 만들고 시작하면 되고 ,
2. 삭제시에 데이터를 지우지 않고 top 값만 감소하는 이유는 다시 새로운 데이터가 push 될 때 전 데이터를 덮어쓰기 때문