문재 해결을 위한 기본적 접근 방법 - 스택(Stack)

나중에 들어온 자료가 먼저 나오는 (Last In First Out: LIFO) 특성을 가지는 자료 구조.

스택의 기본 개념

스택에 자료를 넣을 때에는 넣고자 하는 자료가 항상 가장 위쪽에 놓이게 되고,
자료를 꺼낼 때에도 항상 가장 위쪽에 위치하고 있는 자료가 꺼내 진다.

 

*스택(Stack)의 이해

스택의 절차

*스택(Stack) - Push 절차

  1) 스택에 자료를 넣을 공간이 있는지 확인하다.

  2) (스택에 공간이 있을 경우) top위치 번호를 1증가시킨다.

  3) (스택에 공간이 있을 경우) 스택의  top위치 번호 위치에 자료를 넣는다.

*스택 – push 절차의 예

기능(function) : 스택의 최상단(top)에 자료를 넣음 입력(input) : 스택 s, 자료 x 출력(output) : 없음 push(s, x) begin    if( isFull(s) is equal “false”) //스택에 자료를 넣을 공간 확인     { s.top := s.top + 1; //스택에 공간이 있을 경우 top 위치 번호 1증가       s.data[s.top]:=x;     }    else     {       ERROR(“스택에 빈 공간이 없어 자료를 넣을 수 없습니다.”)     }    end;

*스택(Stack) - Pop 절차

  1) 스택에 자료가 있는지 확인한다.

  2) (스택에 자료가 있을 경우) 스택의 top위치 번호에 위치한 자료를 꺼낸다.

  3) (스택에 자료가 있을 경우) top위치 번호를 1감소시킨다.

*스택 - Pop 절차의 예

기능(function) : 스택의 최상단(top)에 자료를 넣음 입력(input) : 스택 s 출력(output) : 최상단(top)의 자료 x x pop(s) begin     if( isEmpty(s) is equal“false” ) //스택에 꺼낼 자료가 있는지 확인      { x := s.dataa[s.top]; //스택의 자료를 꺼내어 자료 변수에 저장        s.top := s.top – 1; //top위치 번호 1 감소        return x; //자료 변수 건네줌      }     else      {        ERROR(“스택이 비어 있어 자료를 꺼낼 수 없습니다.”)