C++ Stack 만들기 (version.1)

C++와 C language를 어느 정도 잘 다룰 필요가 있다고 생각되어 자료구조 구현을 해볼 것이다.

 

Stack이란 Data Structure 공부를 하게 되면 처음 접하게 되는 친구이다.

 

Last In First Out 방식의 Collection 객체이며 push, pop등으로 연산한다.

 

바로 test.cpp라는 이름의 main함수를 만들어 보겠다.

 

#include <stdio.h>
#include "Stack.h"

void main() 
{
	/*Stack a;
	a.push(10);
	a.push(20);
	a.push(30);
	int x = a.pop();
	a.push(40);
	printf("%d\n", x);
	printf("%d\n", a.pop());*/

	Stack *a;
	a = new Stack();

	a->push(10);
	a->push(20);
	a->push(30);
	int x = a->pop();
	a->push(40);
	printf("%d\n", x);
	printf("%d\n", a->pop());

	delete a;
}

 

C++에는 두가지 방식으로 데이터를 할당하여 사용할 수 있다.

주석을 달아놓은

이 부분은 자동 할당(Automatic allocation)으로 Stack을 만들어 쓴 것인데, 함수를 호출할때나 데이터를 참조할 때 "."을 사용하는 것이 특징이다.

 

다른 방식으로는

Java의 스타일과 같이 동적 할당(Dynamic Allocation)을 하여 Heap영역에서 메모리를 관리하여 쓰는 것이다. "->"로 객체의 member function들을 불러오는게 특징이고 자바와 달리 Garbage Collector 기능이 잘 되어있지 않기 때문에 delete 명령어로 garbage를 회수하여 준다.

 

 

Stack을 정의할 헤더 파일을 만들어 보겠다.

#define MAX		(100)

class Stack {
	int s[MAX];
	int top;
	void stackEmptyError();
public:
	Stack();
	void push(int x);
	int pop();
	int peek();
};

스택에서 사용할 객체는 사이즈 100 짜리 배열을 사용하도록 하겠다. 배열안에 숫자가 그대로 있으면 보기 좋지 않기에 매크로 값으로 MAX라는 이름을 하나 define하여 100만큼 설정해 준다. 매크로의 이름과 설정할 값 사이에는 충분한 여백을 두는게 관습이라고 한다.

 

Stack 객체를 보자면 배열 s와 스택의 꼭대기를 위한 top, 스택이 비었을때 exception 처리를 할 stackEmptyError() 메서드가 private으로 정의되어 있다. (public, private 같은 접근 지정자가 없으면 무조건 private)

그리고 생성자의 Stack()과 push(), pop(), peek() 각각의 함수를 정의한다.

 

헤더 파일로 추상화가 되었다면 실제로 구현할 Stack.cpp 파일을 만들어 보겠다.

#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>

// scope resolution operator ::
Stack::Stack() 
{
	top = -1;

	for (int i = 0; i < MAX; i++) s[i] = 0;
}

void Stack::push(int x) 
{
	if (top >= MAX-1) {
		printf("Overflow!!!\n");
		exit(-1);
	}
	top++;
	s[top] = x;
}

int Stack::pop()
{
	if (top == -1) stackEmptyError();

	top--;
	return s[top+1];
}

int Stack::peek()
{
	if (top == -1) stackEmptyError();

	return s[top];
}

void Stack::stackEmptyError()
{
	printf("Stack Empty!!!\n");
	exit(-1);
}

Stack.cpp를 사용하기 위해서는 미리 정의해둔 Stack.h 헤더파일을 include 시켜야 한다.

그리고 printf문을 위한 stdio.h와 exit()를 위한 stdlib.h도 include 시켜두겠다.

 

먼저 Stack 생성자를 만들것이다.

Stack::Stack() { } 에 "::"와 같은 낯선 기호가 있는데, scope resolution operator라 불린다. Stack에 속한 Stack() Constructor 혹은 Method 들 이라는 것을 뜻한다. 

스택이 처음 생성될 때는 비어있으므로 top 은 -1로 세팅해준다. 그리고 배열은 0으로 초기화 시켜준다.

 

다음은 push() 함수를 만들겠다.

push를 하다가 생길 수 있는 문제로는 overFlow가 있는데 top 값이 MAX-1 이상인 경우 프로그램을 exit 해주는 것으로 Boundary condition을 정해 둔다.

그렇지 않은 경우에는 push를 할 수 있으므로 top값을 1씩 증가시켜주며 배열에다 값을 추가시켜준다.

 

다음은 pop() 함수이다.

push에 overFlow가 있다면 pop에는 스택이 비어있을때 값을 꺼내려하는 경우인 underFlow가 있을 수 있다. 그래서 top이 -1인 경우일때는 stackEmptyError()를 띄워주고 프로그램을 종료시킨다.

스택이 비어있지 않은 경우에는 top을 1씩 줄여주고 1줄이기 전의 배열 해당 값을 리턴시켜준다.

 

peek() 함수는 스택 맨 위의 값을 지우거나 하지 않고 값을 리턴해주기 때문에 empty인 경우가 아니라면 배열의 top위치에 있는 요소를 리턴시켜준다. 

 

 

C++ 의 걸음마를 떼 보았다. 누군가 이글을 참조한다면 도움이 되길 바라며 틀린 부분에 대한 지적 또한 감사히 받겠다.