Stack 알고리즘

스택 알고리즘을 구현해 보자.

우선 스택에 대해 간단히 알아보자면, 어떤 데이터를 사용할 때 데이터를 저장해놓고 쓰는 일이 생기기 마련이다. 근데 이 데이터를 저장한 반대 순서로 꺼내어 써야할 경우가 있다. 예를 들어 브라우저의 뒤로가기 기능같은거 말이다. 제일 마지막에 탐색했던 페이지부터 제일 처음 탐색했던 페이지 순으로, 즉 저장된 역순으로 데이터를 뽑아서 쓰고 있다. 그냥 아무대나 데이터를 순서없이 막 집어넣고 일일이 찾아서 뽑아내도 되지만 어느게 제일 최근것인지 오래된것인지 찾으려면 시간이 많이 걸리지 않는가? 이때 우리는 스택을 사용할 수 있다.

스택자료구조는 데이터를 순서대로 저장한다. 그리고 데이터를 불러 쓸때는 저장 순서의 역순으로 사용할 수 있게 해준다. 우리는 그냥 불러 쓰기만 하면 그것이 저장의 역순이다. 물론 그렇게 코딩을 해야겠지만 ㅡㅡ;

스택은 push 함수와 pop 함수로 나뉠 수 있다. 스택의 사용은 push와 pop 이라고 기억해놓자. push는 데이터를 자료구조에 처 넣는 함수이다. 그리고 pop은 데이터를 하나씩 불러오는 함수이다. 물론 우리가 구현해야 할 함수다. 다만 스택자료구조를 사용할때 보통 push/pop이라는 이름을 쓴다. 이 이름이 싫다면 insert 머 이렇게 쓰던지...;;

우선 스택이 링크스리스트 구조의 변형이라는 것을 알것이다. 머? 링크드리스트를 모르겠다고? ;; 안타깝게도 나의 블로그에는 링크드리스트를 따로 설명하지 않았으니 검색해 볼 수 있도록!
우선 구조체를 선언하자.

typedef struct _Node{
	struct _Node *next;
	int data;
}Node;

자 이제 Node형 데이터를 만들 수 있게 되었다. 이제 push 함수를 만들어보자.

bool push(Node **stack, int data){
	Node *newNode = new Node;
	if(!newNode)return false;

	newNode->data = data;
	newNode->next = *stack;
	*stack = newNode;
	return true;
}

자 만들어 졌다. 우선 함수 외부에서 stack이라는 포인터를 넘겨받는다. 이 stack포인터가 스택자료들을 탐색하는 역할을 하는 놈이 될것이다. 우선 새 노드를 만들고 이 노드가 제대로 만들어져 Null이 아니라면 if문은 실행되지 않을 것이다.(나도 몰랐는데 가끔 저렇게 해도 메모리 할당에 실패하는 경우가 있다고 한다. 그래서 if 문으로 예외처리를 해준것임. 역시 저렇게 하는데는 이유가 있구나;)

그런 다음 새 노드에 넘겨받은 data를 집어 넣고. 새 노드가 가리키는 노드를 현재 stack이 가리키는 놈으로 대체, 그 다음에 stack 포인터가 새로운 노드를 가리킨다. 그리고 제대로 일이 끝나면 true를 반환. 이 함수를 호출하면 새 노드는 무조건 링크드리스트의 가장 앞에 들어가게 된다. stack 포인터도 가장 앞쪽을 가리키겠지. 이제 뽑아 쓸때는 stack포인터를 이용해서 가장 앞쪽부터 뽑아쓰면 된다.

pop함수를 만들어 보자.

bool pop(Node **stack, int data){
	Node *temp;
	if(!(temp=*stack))return false;

	data = temp->data;
	*stack = temp->next;
	delete temp;
	return true;
}

보통은 pop함수를 쓸때 반환형을 뽑아 쓸 데이터형으로 한다. 그래서 int pop(Node **stack) 이렇게 보통 쓰는데 여기서는 뽑아올 데이터를 인자로 받아온 포인터변수 *data에 저장해서 밖으로 가져간다. 왜냐하면 예외처리 때문이다. 만약 stack이 Null인 상태. 즉 아무 데이터도 저장되지 않은 상태에서 실수로 pop을 호출했을때 false를 넘겨줘야한다. 아니면 제대로 pop 되었을 때 true를 넘겨줘야 제대로 pop의 처리 유무를 확인 할 수 있는데 반환형을 뽑아올 데이터로 해버리면 데이터는 뽑을 수 있지만 이게 옳게 작동했는지는 확인 할수가 없지 않은가. 그래서 위와 같이 코딩하게 된것이다.

역시 데이터를 뽑아올 노드의 데이터를 외부에서 받아온 변수에 집어넣고 stack포인터가 자신이 가리키는 노드의 다음노드를 가리키게 한후. temp를 지움으로써 데이터도 뽑아오고 필요없는 노드도 메모리를 해제하는 일을 수행하게 된다.

이런 일련의 과정을 객체지향프로그래밍으로 처리 할 수도 있다. 다음과 같은 클래스가 나올것이다.

class Stack{
public:
	Stack();
	~Stack();
	void push(int data);
	int pop();
protected:
	typedef struct _Node{
		struct _Node *next;
		int data;
	}Node;

	Node *stack;
};

Stack::Stack(){
	stack = NULL;
	return;
}

Stack::~Stack(){
	while(stack){
		Node *temp = stack->next;
		delete stack;
		stack = temp;
	}
	return;
}

void Stack::push(int data){
	Node *newNode = new Node;
	newNode->data = data;
	newNode->next = stack;
	stack = newNode;
	return;
}

int Stack::pop(){
	Node *temp = stack;
	int data;

	if(stack==NULL)
		throw StackError(E_EMPTY);

	data = stack->data;
	stack = stack->next;
	delete temp;
	return data;
}

위의 StackError 함수는 외부에서 정의했다고 가정하자.
이렇게 클래스로 Stack을 정의하면 사용하는 입장에서는 더욱 편하게 stack을 사용할 수 가 있다.
구조체도 클래스 안에 삽입되어 독립적으로 처리되었다.

+ C++코드에서 에러처리문제는?