스택 자료구조의 개요와 구현

이번 글에서는 스택이 어떤 자료구조인지 알아보고, C++로 구현해 봅니다.

목차

1. 스택이란

2. 스택의 기본 연산 구현

3. 스택의 추가 연산 구현

작성하면서 참고한 자료

C++ 자료구조론, Horowitz 외

http://www.yes24.com/Product/Goods/2656393

C++ 자료구조론 (2판) - YES24

---

스택이란

스택(stack)은 톱(top)이라고 하는 한쪽 끝에서 모든 삽입(push)과 삭제(pop)가 일어나는 순서 리스트입니다. 제일 마지막으로 삽입된 원소가 가장 먼저 삭제되기 때문에 후입선출(LIFO: Last-In-First-Out) 리스트라고도 부릅니다.

 

스택 자료구조의 기본적인 연산으로는 원소 삽입, 원소 삭제, 스택이 비었는지 검사 등이 있습니다.

스택의 기본 연산 구현

스택 자료구조를 구현하는 가장 쉬운 방법은 1차원 배열을 사용하는 것입니다. 톱이 배열의 가장 마지막 원소를 가리키면, 삽입과 삭제 연산을 매우 쉽게 구현할 수 있게 됩니다.

 

우선 구현해야 할 Stack 클래스와 테스트를 위한 main 함수는 다음과 같습니다.

#include <iostream>
using namespace std;

template <class T>
class Stack
{
public:
	Stack(int stackCapacity = 10);
	// 처음에 크기가 stackCapacity인 빈 스택을 생성

	bool IsEmpty() const;
	// 스택의 원소 수가 0이면 true, 아니면 false를 반환

	T& Top() const;
	// 스택의 톱 원소를 반환

	void Push(const T& item);
	// 스택의 톱에 item을 삽입

	void Pop();
	// 스택의 톱 원소를 삭제

private:
	T* stack;
	// 스택 원소를 위한 배열

	int top;
	// 톱 원소의 위치

	int capacity;
	// 스택 배열의 크기
};

int main()
{
	Stack<char> charStack(5);
	
	cout << charStack.IsEmpty() << endl;
	charStack.Push('A');
	charStack.Push('B');
	charStack.Push('C');
	charStack.Push('D');
	charStack.Push('E');
	charStack.Push('F');
	charStack.Pop();
	cout << charStack.Top() << endl;

	return 0;
}

 

생성자(constructor)는 다음과 같이 구현할 수 있습니다.

template <class T>
Stack<T>::Stack(int stackCapacity) : capacity(stackCapacity) {
	if (capacity < 1) throw "Stack capacity must be > 0";
	stack = new T[capacity];
	top = -1;	// 스택이 비어 있음을 나타냄
}

 

IsEmpty()와 Top()은 다음과 같이 구현할 수 있습니다.

template <class T>
bool Stack<T>::IsEmpty() const {
	return top == -1;
}

template <class T>
T& Stack<T>::Top() const {
	if (IsEmpty()) throw "Stack is empty";
	return stack[top];
}

 

Push()의 구현은 다음과 같습니다. 이전 글에서 보여드린 바 있는, 동적 배열의 크기를 바꾸는 함수 ChangeSize()를 사용합니다.

template <class T>
void ChangeSize(T*& a, const int oldSize, const int newSize) {
	if (newSize < 0) throw "New length should not be lower than 0";
	T* temp = new T[newSize];
	int number = min(oldSize, newSize);
	copy(a, a + number, temp);
	delete[] a;
	a = temp;
}

template <class T>
void Stack<T>::Push(const T& item) {
	if (top == capacity - 1) {
		ChangeSize(stack, capacity, capacity * 2);
		capacity *= 2;
	}
	stack[++top] = item;
}

 

Pop()의 구현은 다음과 같습니다.

template <class T>
void Stack<T>::Pop() {
	if (IsEmpty()) throw "Stack is empty. Cannot delete.";
	stack[top--].~T();	// T에 대한 소멸자
}

 

지금까지 구현한 내용으로 테스트를 해 보면 다음을 얻습니다!

스택의 추가 연산 구현

이제, 다음과 같은 함수를 추가해 보려 합니다.

1. 스택을 출력하는 함수 Print()

2. 스택을 두 개의 스택으로 분할해서 하나는 밑으로부터 반을, 또 다른 하나는 나머지 원소를 포함하도록 하는 함수 Split()

3. 두 개의 스택을 하나로 합병해서 두 번째 스택의 모든 원소를 첫 번째 스택의 톱에 설치하는 함수 Merge()

 

우선 Print()의 구현입니다.

template <class T>
void Stack<T>::Print() {
	for (int i = 0; i <= top; i++) {
		cout << stack[i] << endl;
	}
}

 

다음으로 Split()의 구현입니다.

template <class T>
Stack<T>& Stack<T>::Split() {
	if (top < 1) throw "Not enough elements to split.";
	capacity = capacity / 2 + 1;
	Stack<T>* stack2 = new Stack<T>(capacity);
	int number = top / 2 + 1;
	for (int i = number; i <= top; i++) {
		stack2->Push(stack[i]);
	}
	for (int i = number; top >= number; i++) {
		Pop();
	}
	return *stack2;
}

 

마지막으로 Merge()의 구현입니다.

template <class T>
void Stack<T>::Merge(const Stack<T>& stack2) {
	ChangeSize(stack, capacity, capacity + stack2.capacity);
	capacity += stack2.capacity;
	for (int i = 0; i <= stack2.top; i++) {
		Push(stack2.stack[i]);
	}
}

 

전체 코드입니다.

#include <iostream>
using namespace std;

template <class T>
class Stack
{
public:
	Stack(int stackCapacity = 10);
	// 처음에 크기가 stackCapacity인 빈 스택을 생성

	bool IsEmpty() const;
	// 스택의 원소 수가 0이면 true, 아니면 false를 반환

	T& Top() const;
	// 스택의 톱 원소를 반환

	void Push(const T& item);
	// 스택의 톱에 item을 삽입

	void Pop();
	// 스택의 톱 원소를 삭제

	void Print();
	// 스택을 출력

	Stack<T>& Split();
	// 스택을 두 개로 분할

	void Merge(const Stack<T>& stack2);
	// 두 스택을 하나로 합병

private:
	T* stack;
	// 스택 원소를 위한 배열

	int top;
	// 톱 원소의 위치

	int capacity;
	// 스택 배열의 크기
};

int main()
{
	Stack<char> charStack(5);
	
	cout << charStack.IsEmpty() << endl;
	charStack.Push('A');
	charStack.Push('B');
	charStack.Push('C');
	charStack.Push('D');
	charStack.Push('E');
	charStack.Push('F');
	charStack.Pop();
	cout << charStack.Top() << endl;

	charStack.Print();
	Stack<char> charStack2 = charStack.Split();
	cout << "Splitted charStack:" << endl;
	charStack.Print();
	cout << "Splitted charStack2:" << endl;
	charStack2.Print();
	charStack.Merge(charStack2);
	cout << "Merged charStack:" << endl;
	charStack.Print();

	return 0;
}

template <class T>
Stack<T>::Stack(int stackCapacity) : capacity(stackCapacity) {
	if (capacity < 1) throw "Stack capacity must be > 0";
	stack = new T[capacity];
	top = -1;	// 스택이 비어 있음을 나타냄
}

template <class T>
bool Stack<T>::IsEmpty() const {
	return top == -1;
}

template <class T>
T& Stack<T>::Top() const {
	if (IsEmpty()) throw "Stack is empty";
	return stack[top];
}

template <class T>
void ChangeSize(T*& a, const int oldSize, const int newSize) {
	if (newSize < 0) throw "New length should not be lower than 0";
	T* temp = new T[newSize];
	int number = min(oldSize, newSize);
	copy(a, a + number, temp);
	delete[] a;
	a = temp;
}

template <class T>
void Stack<T>::Push(const T& item) {
	if (top == capacity - 1) {
		ChangeSize(stack, capacity, capacity * 2);
		capacity *= 2;
	}
	stack[++top] = item;
}

template <class T>
void Stack<T>::Pop() {
	if (IsEmpty()) throw "Stack is empty. Cannot delete.";
	stack[top--].~T();	// T에 대한 소멸자
}

template <class T>
void Stack<T>::Print() {
	for (int i = 0; i <= top; i++) {
		cout << stack[i] << endl;
	}
}

template <class T>
Stack<T>& Stack<T>::Split() {
	if (top < 1) throw "Not enough elements to split.";
	capacity = capacity / 2 + 1;
	Stack<T>* stack2 = new Stack<T>(capacity);
	int number = top / 2 + 1;
	for (int i = number; i <= top; i++) {
		stack2->Push(stack[i]);
	}
	for (int i = number; top >= number; i++) {
		Pop();
	}
	return *stack2;
}

template <class T>
void Stack<T>::Merge(const Stack<T>& stack2) {
	ChangeSize(stack, capacity, capacity + stack2.capacity);
	capacity += stack2.capacity;
	for (int i = 0; i <= stack2.top; i++) {
		Push(stack2.stack[i]);
	}
}

 

테스트 결과는 다음과 같습니다.

---

다음 글에서는 큐 자료구조에 대해 알아보겠습니다.