[DS] 스택 - Stack (개념 및 배열로 스택 구현하기)

이미지 출처 : Pixabay

스택은 후입선출(LIFO, Last-In, First-Out)의 원리에 따라 삽입과 삭제를 수행하는 자료구조입니다.

실생활에서 접시를 쌓아 둔 것과 비교할 수 있습니다. (접시를 층층이 쌓아 둘 때, 가장 먼저 쌓아 둔 접시는 맨 아래에 위치하게 되고, 나중에 쌓은 접시는 가장 위에 위치하게 되어 접시를 사용할 때 먼저 사용됩니다.)

스택은 구현이 쉬운 편이며 상당히 많은 분야에서 응용됩니다. 다음 그림은 스택이 어떻게 동작하는지를 나타낸 것입니다.

스택의 동작

C++에서 배열을 사용하여 간단히 스택을 구현하겠습니다.

이전에, 예외 처리를 위해 커스텀 예외 처리 클래스를 구현하였습니다.

#ifndef RUNTIME_EXCEPTION_H
#define RUNTIME_EXCEPTION_H

#include <iostream>
using std::ostream;
#include <string>
using std::string;

class RuntimeException {
private:
	string error_message_;
public:
	RuntimeException(const string& error_message) { error_message_ = error_message; }
	string error_message() const { return error_message_; }
};

inline ostream& operator <<(ostream& out, const RuntimeException& exception) {
	return out << exception.error_message();
}

#endif

위에서 작성한 RuntimeException 클래스를 상속받아 StackFullException 클래스 및 StackEmptyException 클래스를 정의합니다.

#include "runtime_exception.h"

class StackFullException : public RuntimeException {
public:
	StackFullException(const string& error_message) : RuntimeException(error_message) {}
};

class StackEmptyException : public RuntimeException {
public:
	StackEmptyException(const string& error_message) : RuntimeException(error_message) {}
};

 그리고 Stack 클래스를 정의한 후 다음 두 핵심 함수를 작성합니다 : 

push(object) : 객체 object를 스택의 최상위에 삽입합니다. 만약 스택이 가득 차 있다면 오류를 반환합니다.
pop() : 스택의 최상위에 있는 객체를 스택에서 제거하고 해당 객체를 반환합니다. 만약 스택이 비어있다면 오류를 반환합니다.

작성된 Stack 클래스는 다음과 같습니다.

template <typename Object>
class Stack {
private:
	Object * stack_array_;
	int size_;
	const int kStackCapacity = 100;

public:
	Stack() {
		size_ = 0;
		stack_array_ = new Object[kStackCapacity];
	}
	~Stack() {
		delete[] stack_array_;
	}
	int size() const {
		return size_;
	}
	bool IsEmpty() const {
		return (size_ == 0);
	}
	void Push(Object &object) throw(StackFullException) {
		if (size_ == kStackCapacity) {
			throw StackFullException("Stack is full!\n");
		}
		stack_array_[size_++] = object;
	}
	Object Pop() throw(StackEmptyException) {
		if (size_ == 0) {
			throw StackEmptyException("Stack is empty!\n");
		}
		return stack_array_[--size_];
	}
	Object& Top() throw(StackEmptyException) {
		if (size_ == 0) {
			throw StackEmptyException("Stack is empty!\n");
		}
		return stack_array_[size_ - 1];
	}
};

여기서 멤버 함수 Pop()이 객체의 실제 복사본을 반환하는 반면 Top()은 스택의 최상단 객체에 대한 참조(&Object)를 반환하도록 작성되었습니다. Top() 함수를 레퍼런스 반환 함수로 작성하여 스택의 최상단에 있는 원소를 lvalue 속성을 가지게 반환하는 것은 해당 원소의 변경을 허용하겠다는 의미입니다. 만일 데이터의 무결성을 위하여 해당 원소의 변경을 허용하지 않고자 할 경우, Top()함수를 상수 멤버 함수로 변경하고 상수 참조를 반환(const Object& Top() const)하도록 선언하면 됩니다. Pop() 함수는 객체를 스택에서 삭제하기 때문에 참조자를 반환하는 것은 의미가 없습니다. 따라서 Pop() 함수는 참조자가 아닌 객체의 복사본을 반환하도록 작성하는 것이 바람직합니다.