[C++] 정수형 스택 STACK 구현 코드 (with 후위계산법)

위와 같은 stack 을 코드로 구현해 볼 거다.

정수만 들어가는 stack을 intStack 클래스로 정의한다.

필요한 멤버함수가 들어 있는 intStack 클래스를 intStack.h 헤더파일에 정의해준다.

#pragma once
#include <iostream>
using namespace std;
typedef int element;
constexpr auto STACK_SIZE = 5;

class intStack {
	element top;
	element buf[STACK_SIZE];

public:
	intStack() : top(-1) {
		cout << "I made Stack!" << endl;
		for (int i = 0; i < STACK_SIZE; i++)
		{
			buf[i] = -1;
		}
		printStack();
	}
	
	void printStack() const {
		for (int i = 0; i < STACK_SIZE; i++)
		{
			cout << "[" << buf[i] << "]" << endl;
		}
		cout << endl << endl;
	}

	bool chkFull() const {
		if (top >= STACK_SIZE - 1)
			return true;
		else
			return false;
	}

	bool chkEmpty() const {
		if (top == -1)
			return true;
		else 
			return false;
	}

	void push(element tmp) {
		if (chkFull() == true)
			cout << "STACK IS FULL, YA" << endl << endl;
		else {
			buf[++top] = tmp;
			cout << "Let me push this bro " << tmp << endl;
		}
	}

	element pop() {
		element poppy = buf[top];

		if (chkEmpty() == true) {
			cout << "STACK IS EMPTY, HUH" << endl << endl;
			return 0;
		}
		else {
			cout << "Let's pop this shit " << buf[top] << endl;
			buf[top--] = -1;
			return poppy;
		}

	}

};

 

직접 push와 pop 명령을 할 메인 함수가 들어있는 메인 코드를 아래와 같이 써준다. 

나는 push와 pop의 극한을 보기 위해 넘쳐흐르고 바닥이 텅텅빌 때까지 push와 pop을 써줬다.

 

#include <iostream>
#include "intStack.h"
using namespace std;

int main()
{
	intStack steak;
	steak.push(12);
	steak.printStack();
	steak.push(23);
	steak.printStack();
	steak.push(34);
	steak.printStack();
	steak.push(45);
	steak.printStack();
	steak.push(56);
	steak.printStack();
	steak.push(67);
	steak.printStack();

	steak.pop();
	steak.printStack();
	steak.pop();
	steak.printStack();
	steak.pop();
	steak.printStack();
	steak.pop();
	steak.printStack();
	steak.pop();
	steak.printStack();
	steak.pop();
	steak.printStack();

	return 0;
}

 

그렇게 해서 실행결과를 다음과 같이 얻을 수 있었다. 

 

중2병에 걸린 미국 말투로 작성해봤다. 내 마음이다.

이렇게 C++로 STACK을 구현해봤다. 

 

그럼 왜 stack이 중요하고, 왜 필요한가?

예시를 통해 중요성을 알 수 있다.

우리가 흔히 문서 작성을 하거나 코드 작성을 하다가 잘못 타이핑해서 뒤로 돌아갈 때 ctrl + z를 사용하는 것도 stack의 구조를 이용한 동작이다. 

ctrl + z 키로 최근에 수정한 내용을 pop( ) 해버리는 것이다.

 

그리고 서브루틴 호출 관리와 이후 리턴할 명령 수행 지점을 저장할 때 사용된다.

이게 무슨 말이냐. 위처럼 C++ 코드를 작성하다보면 함수 A에 갔다가 함수 B에 갔다가 함수 C에 갔다가 다시 함수 A로 돌아오는 등의 동작이 발생할 수 있다.

예를 들어서, 

int main( ) {

......

funcA( );

....

}

funcA() {

......

funcB( );

....

}

funcB() {

......

funcC( );

....

}

funcC(){

......

}

이런 식으로 얽히고 섥힌 함수 관계를 차근차근 풀어보자.

main( )함수 내에서 구문을 실행하다가 

-> funcA( ); 를 호출해서 funcA()에 가서 구문을 실행하다가

-> funcB( ); 를 호출해서 funcB()에 가서 구문을 실행하다가

-> funcC( ); 를 호출해서 funcC()에 가서 구문을 실행하고 함수가 끝나면

-> 다시 funcB( )에서 funcC( ); 다음 구문들을 실행하고 함수가 끝나면

-> funcA( )에서 funcB( ); 다음 구문들을 실행하고 함수가 끝나면

-> main( )에서 funcA( ); 다음 구문들을 실행하고 함수가 끝나서 프로그램이 종료된다.

 

이런 복잡한 호출을 관리하기 위해서 운영체제는 main()함수를 수행하다가 funcA( );를 만났을 때 아직 실행하지 못한 명령어들 중 처음 명령어가 저장된 메모리 주소를 stack에 기억해놓는다.

main( )함수 내에서 funcA( ) 다음 명령어 주소

 그다음에 funcA( )에 가서 funcB( )를 만나고 아직 수행하지 못한 funcA( )의 명령어들을 또 stack에 저장해놓는다.

funcA( ) 함수 내에서 funcB( ); 다음 명령어 주소

main( )함수 내에서 funcA( ); 다음 명령어 주소

동일하게 funcB( )에 가서도 funcC( )를 호출하느라 수행하지 못한 나머지 명령어 주소를 기억해 놓는다.

funcB( ) 함수 내에서 funcC( ); 다음 명령어 주소

funcA( ) 함수 내에서 funcB( ); 다음 명령어 주소

main( )함수 내에서 funcA( ); 다음 명령어 주소

funcC( )에서 함수를 모두 수행하고 funcB( )의 나머지 구문을 수행하기 위해 저장해 놓은 메모리 주소로 돌아가고 funcB( ) 함수를 모두 수행해서 끝나면 pop( )으로 저장했던 주소를 삭제한다.

funcB( ) 함수 내에서 funcC( ); 다음 명령어 주소

funcA( ) 함수 내에서 funcB( ); 다음 명령어 주소

main( )함수 내에서 funcA( ); 다음 명령어 주소

같은 방식으로 funcA( )로 돌아와서 마저 명령을 수행 후 pop( )을 통해 메모리를 삭제한다.

funcA( ) 함수 내에서 funcB( ); 다음 명령어 주소

main( )함수 내에서 funcA( ); 다음 명령어 주소

최종적으로 main( )함수로 명령어 주소를 보고 돌아와서 마저 수행하고 프로그램을 종료하면서 pop( )을 통해 저장했던 명령어 주소를 삭제한다.

main( )함수 내에서 funcA( ); 다음 명령어 주소

이렇게 stack은 모두 비워지고 나도 stack을 왜 쓰는 지 이해가 조금은 갈 것이라고 생각한다.

 

이 외에도, stack은 연산자들 간 우선순위에 의해 계산 순서가 결정되는 수식을 계산할 때,

인터럽트 처리, 컴파일러, 재귀호출 관리 등에 사용된다.

 

이 중에 후위계산법 (postfix 계산법)을 STACK으로 구현하면 연산하기 편하다. 

예시를 들어보겠다.

4+7*9 를 계산하고 싶다. 이 표현식은 중위표현식이다.

STACK으로 계산을 편리하게 하려면 후위표현식으로 쓰는 게 좋다.

후위표현식으로 쓰면 4+79* --> 479*+ 이렇게 표현할 수 있다.

이걸 STACK으로 계산하는 코드는 아래와 같다.

먼저, STACK 클래스를 정의해줬다. 위에서 정의한 것과 큰 차이가 없이 STACK 사이즈 정도가 바꼈다.

#pragma once
#include <iostream>
using namespace std;
typedef int element;
constexpr auto STACK_SIZE = 10;

class postfixstack {
	element top;
	element buf[STACK_SIZE];

public:
	postfixstack() : top(-1) {
		cout << "I made Stack!" << endl;
		for (int i = 0; i < STACK_SIZE; i++)
		{
			buf[i] = -1;
		}
		printStack();
	}
	
	void printStack() const {
		for (int i = 0; i < STACK_SIZE; i++)
		{
			cout << "[" << buf[i] << "]" << endl;
		}
		cout << endl << endl;
	}

	bool chkFull() const {
		if (top >= STACK_SIZE - 1)
			return true;
		else
			return false;
	}

	bool chkEmpty() const {
		if (top == -1)
			return true;
		else 
			return false;
	}

	void push(element tmp) {
		if (chkFull() == true)
			cout << "STACK IS FULL, YA" << endl << endl;
		else {
			buf[++top] = tmp;
			cout << "Let me push this bro " << tmp << endl;
		}
	}

	element pop() {
		element poppy = buf[top];

		if (chkEmpty() == true) {
			cout << "STACK IS EMPTY, HUH" << endl << endl;
			return 0;
		}
		else {
			cout << "Let's pop this shit " << buf[top] << endl;
			buf[top--] = -1;
			return poppy;
		}

	}

};

 클래스는 바뀐게 없으니 자세히 볼 필요 없고, 연산을 위한 메인 함수를 아래와 같이 짤 수 있다.

#include <iostream>
#include <cstring>
#include "postfixstack.h"
using namespace std;



int main()
{
	postfixstack  steak;
	const char* soosik = "479*+";
	int length = strlen(soosik);

	for (int i = 0; i < length; i++) {
		if (soosik[i] != '+' && soosik[i] != '-' && soosik[i] != '*' && soosik[i] != '/') {
			int num = soosik[i] - '0';  //문자열에서 숫자로 만들기
			steak.push(num);
		}
		else {
			int num2 = steak.pop();
			int num1 = steak.pop();
			switch (soosik[i])
			{
				case '+': steak.push(num1 + num2); break;
				case '-': steak.push(num1 - num2); break;
				case '*': steak.push(num1 * num2); break;
				case '/': steak.push(num1 / num2); break;
			}
		}
		steak.printStack();
	}

	cout << "The result is : " << steak.pop() << endl;

	return 0;
}

 

실행결과는 다음과 같다.

 

이 글을 보는 모두가 디버깅 잘 되시길 바랍니다.