본문 바로가기
MISCELLANEOUSNESS

[Stack] 스택의 구현

by 회색뿔 2007. 9. 15.
 

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 될 때 전 데이터를 덮어쓰기 때문
반응형

'MISCELLANEOUSNESS' 카테고리의 다른 글

[UNIX/LINUX] FTP 기본 명령어  (0) 2007.09.15
[UNIX] UNIX 기본 명령어  (0) 2007.09.15
[Queue] 큐의 구현  (0) 2007.09.15

댓글0