[자료구조] 스택(stack)

 

스택이란?

가장 먼저 저장한 자료가 가장 나중에 호출되고, 가장 나중에 저장한 자료가 가장 먼저 호출되는 구조.

구멍이 하나밖에 없는 프링글스 원통 병과 같다. 

스택 구조

 

사용 예시

- 웹 브라우저 뒤로가기

- 배열 역순 출력

- 활성화 레코드

 

 

스택 응용 : 활성화 레코드(activation record)

함수를 호출할때 생성되어 함수의 저장과 복귀를 돕는 것. 스택 프레임(stack frame)이라고도 한다.

 

구현에 필요한 요소 :

- 복귀 주소

- 매개 변수

- 지역 변수

 

실행 순서 :

1. '가' 함수 호출, 스택에 복귀주소, 매개변수, 지역변수 순으로 저장

2. '가' 함수에서 '나' 함수 호출, 스택에 복귀주소, 매개변수, 지역변수 순으로 저장

3. '나' 함수에서 '다' 함수 호출, 스택에 복귀주소, 매개변수, 지역변수 순으로 저장

3. '다' 함수의 실행을 완료한 후 복귀주소를 통해 '나' 함수로 복귀

4. '나' 함수의 실행을 완료한 후 복귀주소를 통해 '가' 함수로 복귀

 

즉, 가장 먼저 호출되어 저장된 함수가 가장 나중에 복귀하게 된다.

 

활성화 레코드 원리

 

 

스택 구현

특징 : 배열을 동적으로 할당하여 프로그램 실행중에 배열의 크기를 바꿀 수 있도록 한다.

 

구현에 필요한 요소:

template <class T>

class Stack
{
 private:
   T *stack;			//스택 원소를 위한 배열
   int top;			// 가장 최근 원소의 위치
   int capacity;		//스택 배열의 크기
   
 public:
   Stack (int stackCapacity);		//스택 배열의 크기를 매개변수로 받는 생성자
   
   bool IsEmpty() const; 		//스택이 공백인지 확인하는 함수
   
   T& Top() const;			//가장 위의 요소(가장 최근 요소)를 리턴하는 함수
   
   void Push (const T& item)		//새로운 요소를 받아 가장 위에 저장하는 함수
   
   void Pop();				//가장 위의 요소(가장 최근 요소)를 삭제하는 함수
};

 

생성자 세부정보 :

template <class T>
Stack<T>::Stack (int stackCapacity): capacity(stackCapacity)
{
   if(capacity < 1) throw "Stack capacity must be > 0";	//배열 용량 < 1이면 예외 발생시킴
   stack = new T[capacity];		//새 요소 동적 할당
   top = -1;				//공백인 스택을 의미할 때 top == -1이라 간주할것임
}

 

함수 세부정보 :

template <class T>
inline bool Stack<T> :: IsEmpty() const 
{
   return top == -1		//공백인 스택이면 True, 아니면 False
};


template <class T>
inline T& Stack<T>::Top() const
{
   if (IsEmpty()) throw "Stack is empty";	//공백인 스택이면 예외 발생시킴
   return stack[top];				//가장 최근의 요소를 리턴함
}


template <class T>
void Stack<T> :: Push (const T& x)
{
   // 스택 용량이 다 찼는지 검사
   if (top == capacity-1)
   {
      ChangeSizeID(stack, capacity, 2*capacity);//스택의 용량을 2배로 늘리는 함수
      capacity *= 2;
   }
   stack[++top] = x;			//새로운 요소를 맨 위에 저장
}


template <class T>
void Stack<T>::Pop()
{
   if (IsEmpty()) throw "Stack is empty, Cannot delete.";//공백인 스택이면 예외 발생시킴
   stack[top--].~T();		//소멸자 호출하여 해당 요소의 메모리 삭제
}

 

 

참고 자료:

C++ 자료구조론/이석호 역/인피니티북스/2007/2판