C++ Stack 만들기 (version.3.2 - LinkedList Stack)

Stack 만들기 version 3.2

 

LinkedList로 만든 Stack version 3.1에 Garbage collector와 Destructor, preprocessor directives 등의 기능을 보완하여 만들어 보겠다

 

Stack 구현 로직은 3.1 버전과 같다.

https://suldenlion.tistory.com/82

 

바로 메인 함수를 보도록 하겠다.

#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();
	Stack *b = a;
	a->push(10);
	a->push(20);
	a->push(30);
	int x = a->pop();
	a->push(40);
	for (int i = 100; i < 120; i++) {
		a->push(i);
	}
	printf("%d\n", x);
	printf("%d\n", a->pop());
	a->print();
	
	delete a;*/
	//delete b;
}

Stack을 만들어 사용하는 부분이 될 것이다. 

 

다음은 Stack의 헤더 파일이다. 이전 버전과 달리 약간의 변동사항이 있다.

#ifndef _STACK_H
#define _STACK_H

#include <stdio.h>

class Node {
public:
	int data;
	Node *next;
	Node(int x) {
		data = x;
		next = NULL;
	}
};

class Stack {
	Node *top;
	void stackEmptyError();
public:
	Stack();
	~Stack();
	void push(int x);
	int pop();
	int peek();
	void print();
};

#endif

 

바로 #ifndef (if not define) 매크로의 사용이다. 

헤더 파일의 중복 정의를 피하기 위한 전처리기 명령어(preprocessor directives)이다. 

예를 들어, 스택 헤더 파일을 include하는 파일이 있을 때, #include "Stack.h" 를 실수로 두 번이상 코드를 친다면 전처리기기가 헤더안의 내용을 재정의 해버려서 오류가 나게 된다.

Symbol Table과 관련이 있는 내용인데, 이해가 정확하게 된게 아니라서 다음 내용들에 오류가 있을수 있다. 헤더에 정의된 내용이 Symbol Table에 담기는데 중복된 #include 지시문이 사용된다면 Symbol Table에 오류를 준다. 그리고 이 Symbol Table은 전처리기(C Preprocessor)가 참조하는 테이블이다. 결론은 헤더파일 중복으로 인해 문제가 생기므로 그러한 문제들을 예방하기 위해 모든 헤더파일에 #ifndef ~ #endif 문을 선언하는것이 바람직하다고 한다.

+ 라이브러리의 #include <stdio.h> 같은 경우는 여러번 호출해도 오류가 나지 않는다. → 위와 같은 처리가 라이브러리 소스 코드 내에서 되어 있기 때문.

 

그리고 Stack 소스코드 파일을 보겠다.

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

// scope resolution operator ::
Stack::Stack() 
{
	top = NULL;
}

Stack::~Stack()
{
	Node *tmp = top;
	while (tmp != NULL) {
		Node *p = tmp;
		tmp = tmp->next;
		delete p;
	}
}

void Stack::print()
{
	printf("[");
	Node *tmp = top;
	while (tmp != NULL) {
		printf("%d", tmp->data);
		if (tmp->next != NULL) {
			printf(",");
		}
		tmp = tmp->next;
	}
	printf("]\n");

}

void Stack::push(int x) 
{
	Node *tmp = new Node(x);
	tmp->next = top;
	top = tmp;
}

int Stack::pop()
{
	if (top == NULL) stackEmptyError();
	int x = top->data;
	Node *p = top;
	top = top->next;
	delete p;
	return x;
}

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

	return top->data;
}

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

 

Destructor와 pop 함수 내의 delete 문을 통해 Garbage collect 작업에 신경을 써주었다. 

C나 C++ 같은 경우에는 Java와 달리 Garbage collection 기능에 있어 IDE 내에서 쓰레기값들을 자동적으로 수거해 가지 않기 때문에 일일히 힙 영역에서 참조하고 있던 값들과 그 참조값에 딸린 값들을 delete를 통해 처리해 주어야 한다.

 

pop()을 보면, 리턴할 top의 값을 보관하고 top을 가리킬 임시 포인터 노드 p를 선언한다. 그리고 top 값을 그 다음에 위치한 노드가 되게 하고, top을 가리키던 노드를 delete 시켜준다.

이런식으로 garbage를 수거해가는데 프로그램이 엄청 큰 경우 이런 garbage 처리가 상당히 고역이라 한다.

 

다음은 Destructor ~Stack을 보겠다.

스택을 깔끔하게 수거해 가야하기 때문에, top에 위치한 노드부터 하나씩 traverse하여 참조된 영역을 delete 시켜줘야 한다.

 

 

순서대로 노드를 tmp에 담아 없앨 노드를 *p로 지정하고 tmp는 그다음 노드를 가리키게 하며 p를 delete 해주면 된다.