3. 스택 자료구조
3.1) 스택(Stack) 개요
자료구조(Data Structure)란 ‘자료를 관리하는 방법’이다. 스택(Stack)은 자료구조의 일종으로, 자료를 저장하면 가장 최근의 자료부터 빠져나오는 자료구조이다. 책상 위에 접시를 쌓는 경우를 예를 들어보자. 스택에 자료를 넣는다는 것은 1번 접시부터 차례로 2번 접시, 3번 접시를 각각의 접시 위에 올리는 것과 같다. 스택에서 자료를 가져온다는 것은 이렇게 쌓아올린 접시의 가장 위에 있는, 이 경우 3번 접시부터 차례로 한 개씩 접시를 빼내는 것과 같다. 물론 현실에선 접시를 통째로 들어 올리거나, 독특한 사람은 접시를 가운데에서 빼낼 수 있지만, 스택은 그런 식으로 자료를 관리하지 않는다. 가장 나중에 넣은 자료가 가장 먼저 나오게 된다. 다음은 스택의 의사 코드와 그 결과이다.
|
스택 사용 예제 |
|
스택.넣는다(1); 스택.넣는다(2); 스택.넣는다(3); while (스택.비어있는가() == false) { // 스택에 자료가 남아있는 동안 값 = 스택.꺼낸다(); 출력(값); } |
|
스택 사용 예제 결과 |
|
3 2 1 |
스택은 다음 행동을 반드시 할 수 있어야 한다.
- 넣는다 : 자료구조는 자료를 관리하는 방법이다. 자료를 넣을 수 없다면 자료구조로 기능할 수 없다.
- 꺼낸다 : 스택은 넣은 자료를 반드시 제거할 수 있어야 한다.
스택에 대해 자료를 넣는 행위를 푸시(push), 자료를 꺼내는 행위를 팝(pop)이라고 한다. 위의 의사 코드를 실제로 동작하는 코드로 바꾼다면 다음과 같이 된다.
|
스택 사용 예제 |
|
class Stack { /* implementations */ }; int main() { Stack stack; stack.push(1); stack.push(2); stack.push(3); while (stack.is_empty() == false) { int value = stack.pop(); std::cout << value << std::endl; } return 0; } |
스택을 더 유용하게 만드는 메서드로는 다음과 같은 것이 있다.
- bool is_empty(); // 스택이 비어있는지 확인한다
- Data top(); // 스택에서 가장 최근에 추가된 자료를 확인한다
- int count(); // 스택에 저장된 자료의 수를 가져온다
스택은 일반적으로 두 가지 방법으로 구현한다. 하나는 배열을 이용하는 것이고, 다른 하나는 리스트 자료구조를 이용하는 것이다. JSCC 프로젝트에서는 배열 기반의 스택만 직접 구현해본다.
3.2) 스택 구현
스택을 다음과 같이 설계할 것이다.
- 정수형 자료를 보관하는 스택 클래스를 만든다.
- static const int MAX_STACK_SIZ; // 배열의 크기를 정할 상수
- int list[MAX_STACK_SIZ]; // 정수형 자료를 실제로 보관하는 배열 필드
- int _count; // 스택에 있는 자료의 수를 나타내는 필드
- void push(int data); // 스택에 데이터를 넣는 메서드
- int pop(); // 스택에서 데이터를 꺼내는 메서드
- int top() const; // 스택에 가장 최근에 추가된 데이터를 보는 메서드
- bool is_empty() const; // 스택이 비어있는지 확인하는 메서드
- bool is_full() const; // 스택이 가득 찼는지 확인하는 메서드
- int count() const; // 스택에 있는 자료의 수를 반환하는 메서드
다음은 이 설계를 바탕으로 실제로 구현한 Stack 클래스이다.
|
01_Stack.cpp |
|
typedef std::string Exception; // 임시; 예외로 string 객체를 던진다 class Stack { static const int MAX_STACK_SIZ = 10; int list[MAX_STACK_SIZ]; int _count; public: Stack() : _count(0) {} // 스택의 크기를 반드시 0으로 설정해야 한다 void push(int data) { // 스택에 데이터를 넣는다 if (is_full()) { // 스택이 가득차 데이터를 넣을 수 없다면 예외 처리한다 throw Exception("스택이 가득 찼습니다."); } // 스택의 마지막에 데이터를 넣고 크기를 증가시킨다 list[_count++] = data; } int pop() { // 스택에서 데이터를 꺼낸다 if (is_empty()) { // 스택이 비어있다면 예외 처리한다 throw Exception("스택이 비어있습니다."); } // 스택의 크기를 감소시킨 후 마지막 데이터를 반환한다 return list[--_count]; } int top() const { // 스택에 가장 최근에 추가된 데이터를 본다 if (is_empty()) { // 스택이 비어있다면 예외 처리한다 throw Exception("스택이 비어있습니다."); } return list[_count - 1]; // 스택의 마지막 데이터를 반환한다 } // 스택이 가득 찼다면 true bool is_full() const { return _count == MAX_STACK_SIZ; } // 스택이 비어있다면 true bool is_empty() const { return _count == 0; } // 스택에 저장된 데이터의 수를 가져온다 int count() const { return _count; } }; |
이와 같이 스택을 구현하고 이해할 수 있었다.
