- 차례
- 1절. 소개
- 2절. Stack
- 1절. 소개
-
- 2.1절. Stack 데이타 추상
-
- 2.1.1절. Stack 구현을 위해 기술되어야할 행동
- 2.1.2절. 구현 및 테스트
-
- 2.1.2.1절. Stack Class
- 2.1.1절. Stack 구현을 위해 기술되어야할 행동
2절. Stack
Stack 의 자료저장 형태는 배열과 동일하다. 다만 자료를 빼내오는 순서에 따라서 Stack 인지가 구분되어진다.
2.1절. Stack 데이타 추상
Stack 는 "더미" 란 뜻을 가진다. 책더미, 신문더미 등에 사용하는 바로 그 더미 이다. 책더미를 예로 들어보자 책더미를 쌓았다고 했을때, 이 책더미에서 책을 가져오는 가장 정상적인 방법은 제일 위에 있는 책을 가져오는 방식이다.
다시 말하자면 가장 먼저 들어간 책은 가장 나중에 꺼낼수 있을 것이다. 이런식으로 자료가 가장 밑에 쌓이고(입력), 자료를 가져올때(출력)는 가장 위(최근)의 자료를 가져오는 자료구조를 Stack 라고 한다. 이러한 Stack 의 특징때문에 흔히 "FILO (First-In-Last-Out)" 혹은 "LIFO (Last-In-First-Out)" 라고 한다. 선입후출, 후입선출 형 자료구조이다.
그림 1. Stack 자료구조
Stack 데이타 추상은 자료의 입출력이 LIFO가 되도록 구현하면 된다.
2.1.1절. Stack 구현을 위해 기술되어야할 행동
행동 대신 메서드라고 해도 관계는 없다. Stack 는 LIFO 자료입출력을 위해서 보통 4가지의 메서드가 기술된다. 즉 Push 와 Pop, Empty, Size 이다. 그리고 이외에 stack 사이즈관리 등을 위한 capacity와 같은 몇가지 메서드를 부가적으로 구현할수도 있을것이다. "필수" 라고 되어있는 것은 stack 의 필수 행동들이고 "유용" 이라고 되어 있는것은 구현되면 도움이 되는 행동들이다.
표 1. Stack 기본 행동
| Push | stack 의 가장 위(top)에 데이타를 저장한다. | 필수 |
| Pop | stack 의 가장위에 있는 데이타를 가져온다. 가져온 데이타는 stack 에서 삭제한다. | 필수 |
| Empty | stack 가 비어있는지 확인한다. | 필수 |
| Size | 스택에 들어있는 원소갯수를 돌려준다. | 유용 |
| Capacity | 스택의 크기 - 담을수 있는 원소갯수 - 를 구한다. | 유용 |
2.1.2절. 구현 및 테스트
2.1.2.1절. Stack Class
위의 "Stack 기본 행동" 을 모두 구현할수 있도록 클래스를 제작한다. Stack 데이타 추상을 위해서 클래스를 사용하는 이유는 ADT 의 구현이 용이하기 때문이다. 그리고 이번에는 좀더 "일반적인" Stack 데이타 추상을 위해서 Template class 를 이용하도록 하겠다.
stack.h
#include <string>
#include <iostream>
using namespace std;
template <typename T>
class stack
{
private:
T *container; // 저장소
int member_num; // 스택에 저장된 원소의 갯수
int stack_size; // 스택의 용량크기
int ele_sizeof; // 타입 T 의 sizeof
public:
// 생성자
// 디폴트 인자로 스택의 용량크기를 받아들인다.
// 용량크기 만큼 메모리 할당하고
// 몇가지 값을 초기화 한다.
stack(int asize=12)
{
stack_size = asize;
member_num = 0;
ele_sizeof = sizeof(T);
container = (T *)malloc(ele_sizeof * stack_size);
}
// 소멸자
// 스택을 free 한다.
~stack()
{
free(container);
}
// 데이타를 스택에 입력한다.
// 만약 스택사이즈가 꽉차있다면
// realloc 를 호출해서 스택사이즈를
// (현재 스택사이즈 * 2) 만큼 늘려준다.
void push_back(T data)
{
if (member_num == (stack_size - 1))
{
stack_size *= 2;
container = (T *)realloc(container, ele_sizeof * stack_size);
}
*(container + member_num) = data;
member_num++;
}
// 스택에서 데이타를 꺼낸다.
T pop_back()
{
member_num --;
return *(container+member_num);
}
// 데이타가 비어있는지 확인한다.
bool empty()
{
return member_num == 0;
}
// 스택에 저장된 데이타의 갯수
int size()
{
return member_num;
}
// 스택의 용량
int capacity()
{
return stack_size;
}
};
|
다음은 템플릿 클래스로 구현한 stack 자료추상의 구현이 잘되었는지 확인하기 위해서 만든 main() 함수를 포함한 테스트용 코드이다.
stack_test.cc
#include "stack.h" #include <iostream> using namespace std; int main() { stack<int> mystack(2); int i, size; cout << "Capacity " << mystack.capacity()<< endl; mystack.push_back(1); mystack.push_back(2); mystack.push_back(3); mystack.push_back(4); cout << "Capacity " << mystack.capacity()<< endl; cout << "size : " << mystack.size() << endl; size = mystack.size(); for (i = 0; i < size; i++) { cout << mystack.pop_back() << endl; } if (mystack.empty()) { cout << "stack is empty" << endl; } } |
