[알고리즘/Algorithm]C++ Stack Class, 스택 클래스

스택에 관하여

안녕하세요. Air8입니다. 오늘의 얘기는 Stack에 관하여입니다.

Stack을 어디서 들어본 적이 있으신가요? 냉장고에 음료수를 일렬로 넣어두고 마실려고 할 때면 가장 마지막에 넣어놨던 애를 꺼내어 마십니다. 이런게 스택(Stack)입니다. 좀 더 나아가서 핸드폰으로 예를 들어보면 어플을 주구장창 아무렇게나 실행을 해봅니다. 가장 최종적으로 띄워진 화면은 제일 마지막에 실행시킨 어플리케이션이 보이겠죠?

 

소프트웨어 엔지니어분들에게 말씀드리면 프로그램에서 함수의 호출리스트도 콜스택(Call-Stack)이라고 부릅니다. 프로그램 흐름을 보면 어떤 함수가 호출되고 그 안에서 또 함수가 호출되고 호출되고 호출되고... 함수를 빠져 나올때에는 가장 마지막에 호출된 함수부터 먼저 빠져나갑니다. 그래서 호출 스택이라고해서 Call Stack이라고 부릅니다.

 

마지막으로 들어간 것이 처음으로 빠져나가는 것을 Last-In First-Out(LIFO) 후입선출 방식이라고 합니다.

 

 

클래스 설명

[클래스] Stack

[속성] - top : int - data[] : int

[연산] + Stack(void) + push(int e) + pop() : int + display() + peek() : int + size() : int + isEmpty(): bool + isFull() : bool

void push(int e)	e(정수형) 를 맨 위에 추가
int pop()	비어있지 않으면 맨 위에 있는 요소를 삭제하고 반환
void display()	모든 요소들을 출력
int peek()	비어있지 않으면 맨 위에 있는 요소를 삭제하지 않고 반환
int size()	요소들의 개수를 반환
bool isEmpty()	비어있으면 true 아니면 false를 반환
bool isFull()	가득 차 있으면 true 아니면 false를 반환

코드(배열을 이용)

void error(const char* message)
{
	printf("Error: %s \n", message);
	exit(1);
}
const int MAX_STACK_SIZE = 20;
class Stack
{
private :
	int top;
	int data[MAX_STACK_SIZE];
public:
	Stack()
	{
		top = 1;
	}
	void push(int e)
	{
		if (isFull())
			error("Full");
		data[++top] = e;
	}
	int pop()
	{
		if (isEmpty())
		{
			error("Empty");
		}
		return data[top--];
	}
	void display() {
		printf("[Size = %d] ", top + 1);
		for (int i = 0; i <= top; ++i)
		{
			printf("%3d", data[i]);
		}
		printf("\n");
	}
	int peek() {
		if (isEmpty())
		{
			error("Empty");
		}
		return data[top];
	}
	int size() { return top; }
	bool isEmpty() { return top == 1; }
	bool isFull() { return top == MAX_STACK_SIZE - 1; }
};

활용

Stack testStack;				// 선언
testStack.push(314); 			// 맨 처음 스택에 314추가
testStack.push(1414); 			// 두번째 스택에 1414 추가
testStack.push(777); 			// 세번째 스택에 777추가
testStack.push(100); 			// 네번째 스택에 100추가 

testStack.display(); 			// 출력 : [Size = 4] 314 1414 777 100
int rtn = testStack.pop();		// 내번째 스택 100 제거 rtn = 100
int size = testStack.size();	// 사이즈 반환 size = 3
int GetPeek = testStack.peek();	// 상위 스택 반환 GetPeek = 777
rtn = testStack.isEmpty();		// 비어있는지 확인 rtn = false;
testStack.pop();				// 세번째 스택 777 제거
testStack.pop();				// 두번째 스택 1414 제거
testStack.pop();				// 첫번째 스택 314 제거
rtn = testStack.isEmpty();		// rtn = true