[자료구조] Stack(스택)

- 참조 문헌 및 사이트(Reference)

Data Structure : A Pseudocode Approach with C

Data Structure and Algorithm in C++

---

코드는 깃허브를 참조 : https://github.com/junstar92/DataStructure_Algorithm/tree/master/Data_Structure/Stack

 

스택(Stack)은 데이터의 삽입과 삭제가 오로지 top이라고 불리는 한쪽 끝에서 이루어지는 선형 리스트이며, LIFO(Last In First Out)의 특성을 갖는 자료구조로 나중에 들어온 데이터가 먼저 삭제됩니다.

아래와 같은 구조를 갖습니다.

 

스택은 배열과 리스트로 구현이 가능하며, 보통 맨 위에 있는 값만 알 수 있으며 맨 위에 새로운 데이터를 추가하거나 삭제하는 동작을 합니다.

 

C++ STL인 <stack>헤더에 스택이 구현되어 있으므로, 이것을 사용하면 되지만 연습삼아 어떻게 구현되는지 알아보도록 합시다...

 

아래는 스택의 기본 동작입니다.

 

1. Push

Push는 스택의 top에 새로운 데이터를 추가하는 것이고, push가 이루어지고 난 이후에는 새로운 아이템이 top위치에 오게 됩니다. 한 가지 잠재적인 문제가 발생할 수 있는데, 만약 메모리 공간이 충분하지 않다면 스택은 overflow 상태가 되며 새로운 데이터는 추가되지 않고 에러가 발생합니다.

다음 그림은 스택의 push 동작을 보여주고 있습니다.

 

2. Pop

Pop은 스택의 top에 존재하는 데이터를 삭제하는 것이며, Pop 또한 잠재적인 문제가 발생할 수 있는데, 만약 현재 스택에 아무런 데이터가 없이 비어있다면, 스택은 underflow 상태가 되어서 에러가 발생한합니다. Top에 존재하는 데이터를 지우면서 그 데이터를 반환하는 경우도 있지만 우리는 top이라는 동작도 구현할 예정이므로 pop함수에서는 데이터를 삭제만 하는 걸로 정의하고 아래서도 반환은 안하는 걸로 구현해보도록 하겠습니다.

 

3. Top

Top은 단순히 스택의 top위치에 존재하는 데이터 값을 반환합니다. 단순히 값만 반환하며, 삭제는 하지 않습니다.

 

기본적인 연산은 위의 3가지로 이루어져있고, 특정한 곳에서만 삽입과 삭제가 발생하므로 모두 O(1)의 시간을 가지게 됩니다. 부가적으로 스택의 현재 크기를 반환하는 size(), 현재 스택이 비어있는지 확인하는 empty()도 있습니다. 

 

 

배열(Array)로 구현

우선 배열로 구현한 스택을 살펴봅시다.

전체코드는 다음과 같습니다. 리스트와 마찬가지로 선언부와 정의부를 나누기 위해서 .h와 .hpp파일로 나누었습니다.

/* ArrayStack.h */
#ifndef ArrayStack_H
#define ArrayStack_H

class StackEmpty {};
class StackFull {};

template<typename T>
class ArrayStack {
	enum { CAPACITY = 100 };
public :
	ArrayStack(int cap = CAPACITY) : Stack(new T[cap]), capacity(cap), t(-1) {}
	~ArrayStack();
	int size() const;
	bool empty() const;
	T& top() const;
	void push(const T& data);
	void pop();

	void print() const;

private:
	T* Stack;
	int capacity;
	int t;
};
#include "ArrayStack.hpp"
#endif

/* ArrayStack.hpp */

template<typename T>
ArrayStack<T>::~ArrayStack()
{
	delete Stack;
}

template<typename T>
int ArrayStack<T>::size() const
{
	return (t + 1);
}

template<typename T>
bool ArrayStack<T>::empty() const
{
	return (t < 0);
}

template<typename T>
T& ArrayStack<T>::top() const
{
	try {
		if (empty()) throw StackEmpty();

		return Stack[t];
	}
	catch (StackEmpty e) {
		std::cout << "Stack is empty\n";
		exit(2);
	}
}

template<typename T>
void ArrayStack<T>::push(const T& data)
{
	try {
		if (size() == capacity) throw StackFull();

		Stack[++t] = data;
	}
	catch (StackFull e) {
		std::cout << "Stack is full\n";
		exit(2);
	}
}

template<typename T>
void ArrayStack<T>::pop()
{
	try {
		if (empty()) throw StackEmpty();

		--t;
	}
	catch (StackEmpty e){
		std::cout << "Stack is empty\n";
		exit(2);
	}
}

template<typename T>
void ArrayStack<T>::print() const
{
	int s = size();
	std::cout << " bottom [ ";
	for (int i = 0; i < s; i++)
	{
		std::cout << Stack[i] << " ";
	}
	std::cout << "] top\n";
}

 

 

스택을 위한 클래스 정의는 다음과 같습니다.

template<typename T>
class ArrayStack {
	enum { CAPACITY = 100 };
public :
	ArrayStack(int cap = CAPACITY) : Stack(new T[cap]), capacity(cap), t(-1) {}
	~ArrayStack();
	int size() const;
	bool empty() const;
	T& top() const;
	void push(const T& data);
	void pop();

	void print() const;

private:
	T* Stack;
	int capacity;
	int t;
};

사용되는 변수 중 Stack은 데이터가 저장되는 배열이며, 클래스가 생성될 때 생성자에 의해서 동적할당되며, 만약 capacity가 지정이 되지 않으면 기본적으로 100의 크기를 가진 배열이 됩니다. capacity는 스택의 총 메모리 용량(데이터가 들어갈 수 있는 개수)이며, t는 현재 top위치의 index입니다. 스택이 비어있을 때에는 이 값은 -1 입니다.

 

int ArrayStack<T>::size() const
{
	return (t + 1);
}

template<typename T>
bool ArrayStack<T>::empty() const
{
	return (t < 0);
}

template<typename T>
T& ArrayStack<T>::top() const
{
	try {
		if (empty()) throw StackEmpty();

		return Stack[t];
	}
	catch (StackEmpty e) {
		std::cout << "Stack is empty\n";
        exit(2);
	}
}

size(), empty(), top() 함수입니다.

size는 현재 스택에 존재하는 데이터의 개수를 반환하며, 배열의 index가 0부터 시작하기 때문에 t + 1의 값을 반환한니다.

empty는 현재 스택이 비어있는지 확인하는 것이며, 스택이 비어있을 때 t의 값이 -1이라는 성질을 사용합니다.

top의 경우에는 현재 스택의 top위치에 있는 데이터의 값을 반환하며, 값이 비어있다면, StackEmpty 예외를 호출하며 프로그램은 종료됩니다.

 

template<typename T>
void ArrayStack<T>::push(const T& data)
{
	try {
		if (size() == capacity) throw StackFull();

		Stack[++t] = data;
	}
	catch (StackFull e) {
		std::cout << "Stack is full\n";
        exit(2);
	}
}

push 함수는 위와 같습니다. 만약 스택이 이미 가득 찼다면 StackFull 예외를 발생시키며 프로그램은 중단되며, 스택이 여유공간을 가지고 있다면 top index를 하나 증가시켜서 값을 저장한합니다. t++이 아닌 ++t라는 것에 주의하시길 바랍니다.

 

template<typename T>
void ArrayStack<T>::pop()
{
	try {
		if (empty()) throw StackEmpty();

		--t;
	}
	catch (StackEmpty e){
		std::cout << "Stack is empty\n";
        exit(2);
	}
}

pop 함수도 push함수와 유사합니다. 스택의 top위치에 있는 값을 지우는 동작을 하며, 만약 스택이 비어있다면 StackEmpty 예외를 발생시켜 프로그램은 종료됩니다. 스택의 top index값만 감소시키는데, 스택은 top에 존재하는 값에만 접근할 수 있기 때문에 삭제되는 값에 대한 다른 처리를 하지 않아도 됩니다.

 

using namespace std;

#include <iostream>
#include <string>
#include "ArrayStack.h"
int main() 
{
	ArrayStack<string> s;
	s.push("green"), s.print();
	s.push("blue"), s.print();
	s.pop(), s.print();
	s.push("red"), s.print();
	string output = s.top(); s.print();
	s.pop(), s.print();
	s.pop(), s.print();
	return 0;
}

그래서 위와 같이 실행해보면 다음과 같은 결과를 얻을 수 있습니다. 여기서 print 함수는 스택의 상태를 보여주기 위해서 작성한 메소드입니다.

 

리스트(List)로 구현

리스트로 구현하기 위해서 개인적으로 구현해둔 Doubly Linked List(이중 연결리스트)를 사용하였습니다. 이중 연결리스트는 Github에서 참조하면 되고, STL의 <list> 헤더를 사용해서 구현해도 됩니다.

https://github.com/junstar92/DataStructure_Algorithm/tree/master/Data_Structure/DoublyLinkedList/cpp

 

전체 코드는 다음과 같으며, Doubly Linked List 내부 함수로 연결리스트에 데이터를 추가 및 삭제합니다. 추가와 삭제는 리스트의 front에서만 진행되므로 나중에 삽입된 데이터가 제일 먼저 나오게 됩니다. 즉, 연결리스트의 head에서만 삽입과 삭제가 이루어지게 됩니다. 나머지 부분은 배열로 구현한 스택과 차이가 없어서 설명은 생략하도록 하겠습니다.

/* LinkedStack.h */
#ifndef LinkedStack_H
#define LinkedStack_H

#include "DLinkedList.h"

class StackEmpty {};

template<typename T>
class LinkedStack
{
public:
	LinkedStack() : n(0) {}
	int size() const;
	bool empty() const;
	T& top() const;
	void push(const T& data);
	void pop();
	void print();

private:
	DLinkedList<T> DLink;
	int n;
};

#include "LinkedStack.hpp"
#endif

/* LinkedStack.hpp */

template<typename T>
int LinkedStack<T>::size() const
{
	return n;
}

template<typename T>
bool LinkedStack<T>::empty() const
{
	return (n == 0);
}

template<typename T>
T& LinkedStack<T>::top() const
{
	try {
		if (empty()) throw StackEmpty();
		return DLink.front();
	}
	catch (StackEmpty e) {
		std::cout << "Stack is empty\n";
		exit(2);
	}
}

template<typename T>
void LinkedStack<T>::push(const T& data)
{
	DLink.addFront(data);
	++n;
}

template<typename T>
void LinkedStack<T>::pop()
{
	try {
		if (empty()) throw StackEmpty();

		DLink.removeFront();
		--n;
	}
	catch (StackEmpty e) {
		cout << "Stack is empty\n";
		exit(2);
	}
}

template<typename T>
void LinkedStack<T>::print()
{
	std::cout << "top " << DLink;
}

 

다음을 실행하면 아래와 같은 결과를 얻을 수 있습니다.

using namespace std;

#include <iostream>
#include <string>
#include "LinkedStack.h"
int main() 
{
	LinkedStack<string> s;
	s.push("green"), s.print();
	s.push("blue"), s.print();
	s.pop(), s.print();
	s.push("red"), s.print();
	string output = s.top(); s.print();
	s.pop(), s.print();
	s.pop(), s.print();
	return 0;
}

 

다음으로 스택이 활용되는 예시들을 문제를 통해서 살펴봅시다.

 

1. Reversing Data

아래 과정을 통해서 데이터의 순서를 반대로 반전시킬 수 있습니다. 

1. 모든 데이터를 스택에 push

2. 모든 데이터를 pop

이 과정을 거치면 데이터가 반전됩니다.

using namespace std;

#include <iostream>
#include "LinkedStack.h"
int main() 
{
	LinkedStack<int> s;

	int data[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	cout << "Data : ";
	for (int i = 0; i < 10; i++)
		cout << data[i] << " ";
	cout << endl;

	for (int i = 0; i < 10; i++)
	{
		s.push(data[i]);
	}
	for (int i = 0; i < 10; i++)
	{
		data[i] = s.top();
		s.pop();
	}

	cout << "After reversing data\n";
	cout << "Data : ";
	for (int i = 0; i < 10; i++)
		cout << data[i] << " ";
	cout << endl;
	
	return 0;
}

 

두번째로는 괄호 검사(가 있습니다. 즉, 괄호가 정상적으로 열고 닫히는지 검사하는 것인데, 올바른 괄호로는 (), [], ([]), [[]], [({()})] 등이 있고, 잘못된 괄호로는 (, ], ((, ([)], (() 등이 있겠죠.

이 문제의 해결방법은 간단한데, 다음과 같이 검사하면 됩니다.

1. 여는 괄호 '(', '[', '{' 등이 나오면 스택에 push합니다.

2. 닫는 괄호가 나오면, 스택의 top과 비교하고, 같은 종류의 괄호면 스택을 pop합니다. 종류가 맞지 않거나, 스택이 비어있다면 잘못된 괄호라는 것입니다.

3. 마지막까지 전부 처리했는데, 만약 스택의 비어있지 않다면 잘못된 괄호입니다. 다음 문제를 같이 풀어봅시다.

https://www.acmicpc.net/problem/9012

9012번: 괄호

STL의 <stack> 헤더를 사용하여서 구현하였습니다. 평소에 실행 속도 때문에 printf, scanf를 사용해서 여기서도 printf, scanf를 사용했지만, cin, cout을 사용해도 문제는 없습니다.

#include <stdio.h>
#include <stack>
using namespace std;

int main()
{
	int T;
	char input[52];
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		stack<char> s;
		bool pass = true;
		int idx = 0;
		scanf("%s", input);
		while (input[idx] != '\0')
		{
			if (input[idx] == '(')
				s.push(input[idx]);
			else
			{
				if (s.empty())
				{
					pass = false;
					break;
				}
				else
					s.pop();
			}
			idx++;
		}
		if (!s.empty())
			pass = false;

		if (pass)
			printf("YES\n");
		else
			printf("NO\n");
	}

	return 0;
}

 

다른 문제도 후에 추가하도록 하겠습니다.