ADT : Stack

Stack

top이라고 불리는 한 쪽 끝에서 삽입과 제거로 만들어지는 자료구조이다.

스택 S = (a0,...,an-1)을 가정하면 a0은 bottom, an-1은 top이다.

아래의 자료처럼 늦게 입력된 것이 가장 먼저 나가게 된다. (FILO)

System Stack

프로그램을 실행시킬 때 함수 호출을 다룬다.

함수가 호출 될 때마다 프로그램은 activation record 또는 stack frame이라고하는 구조를 만들어 시스템 스택 위에 놓습니다. (이전 stack frame에 대한 포인터, 주소를 반환, 지역변수, 매개변수)

함수가 스스로를 호출하는 재귀 함수를 처리할 때.

각 재귀 호출에 대해 새로운 stack frame을 만든다. 최악의 경우 모든 활용가능한 메모리를 소비할 수 있음.

 

Stack ADT 구현

 

1차원 배열을 스택으로 사용한다. 요소 i는 스택의 i-1 위치에 저장된다.변수 top은 항상 스택의 꼭대기 요소를 가르킨다. (top이 -1일 경우 비어있다는 뜻.)상세한 구현은 직접해보길 바란다.

template <typename T>

class Stack
{
Public:
	Stack(int stackCapacity = 10);
	bool IsEmpty() const; //해당 함수에 속한 객체의 멤버를 변경 할 수 없음, 접근은 가능.

	T& Top() const;

	void Push(const T& item);
	void Pop();

private:
	T* stack;
	int top;
	int capacity;

	template <class T>
	Stack <T> ::Stack(int stackCapacity) : capacity(stackCapacity)
	{
		if (capacity < 1) throw "Stack capacity must be > 0";
		stack = new T[capacity];
		top = -1;
	}
};