자료구조(9) - 스택

 - 스택이란

               : 스택은 자료구조의 한 종류

               : 원소의 삽입과 삭제가 리스트의 한 쪽 끝에서만 이루어지는 구조.

               : 구조적 특징과 내부에 순서가 있음으로

                          : 후입선출 ( LIFO : Last In First Out )

                          : 선입후출 ( FILO : First In Last Out )

                 특징을 갖는다.

 

               : 그림이 사실 스택의 거의 모든 걸 담고있다.

               : 삽입과 삭제가 되는 곳이 한 곳( TOP POINTER )이기 때문에, 많은 표현이 TOP POINTER를 통해

                 이루어지게 된다.

                 예를들면 TOP POINTER = 0 일 경우, 스택은 비어있는 상태를 의미한다.

                            TOP POINTER >= n ( 단, n은 스택의 크기 ) 일 경우, 스택이 가득차 있는 상태이다.

                            TOP POINTER는 포인터이므로 원소가 추가될때 1증가된 후 그 공간에 원소를 삽입하게 된다.

 

                 과정을 나타내면 다음과 같다.

 

void puch(datam stack, n, top)
int data, stack[], n, top
{
	if(top >= n)
		printf("Stack is Full");
    else
    { top = top+1;
      stack[top] - data;}
}

 

                 top pointer의 값과 스택의 크기를 비교하고, 꽉 차지않았을 경우 pointer를 늘리고 그 자리에 값을 넣는다.

 

                 삭제의 과정은 다음과 같다.

void pop(item, stack, top)
int item, stack[], top;
{
	if(top == 0) then
    		printf("Stack is empty");
            else{
            item = stack[top];
            top = top -1;
            }
}

                 top이 0인지, 즉 스텍이 비어있는지 확인후 값을 빼내고, top을 낮추는 방법이다.

                 이때의 item값을 활용하면 삭제가 아닌 리턴값을 갖는 것으로 사용이 가능할것 같다.

                 저장공간이니 넣고, 뺴고 해야할테니 말이다.

 

 - 스택의 적용 분야

               : 시스템 스택에 함수 호출에 관련된 스택 프레임들을 저장했다가, 호출된 함수가 종료되면,

                 관련된 스택 프레임을 pop하여 저장되어진 복귀 주소로 복귀한다.

                 -> 함수안의 함수등이 발생할 경우를 생각하면 좋을 듯 하다.

               : 문자열을 역순으로 만들 수 있다.