Stack의 소개
Stack은 한 쪽 끝은 막혀있고, 다른 쪽 끝은 뚫려 있는 자료구조입니다. 나중에 정식으로 공부를 할 때 자세히 배우니까 지금은 Stack이 뭔지만 대충 소개하겠습니다. 우선, Stack을 직관적으로 이해하기 위해, Stack이 대충 어떤 모양인지 그림으로 표현해 보겠습니다.
|
|
|
1 |
|
3 |
|
2 |
|
5 |
이 그림은 size 5짜리 빈 스택에 5 2 3 1 순으로 데이터를 집어넣은(데이터를 넣는 작업을 push라고 합니다) 후의 스택의 내부 구조를 나타낸 것입니다. 만약 여기서 데이터 하나를 뺀(데이터를 빼내는 작업을 pop이라고 합니다)다면, 1이 반환됩니다. 그리고 스택은 다음과 같이 되겠지요. 3 2 5
즉, 맨 마지막에 넣은 데이터(Last Input)가 가장 먼저 삭제되어 반환되는(First Output) 자료구조를 우리는 Stack이라고 부릅니다. Last In First Out. 줄여서 LIFO라고 하는 이 자료구조는, Recursive(재귀호출) 등을 이해하는데 필수적으로 이해해야 할 자료구조입니다.
Stack의 구현
Stack을 구현하는 방법은 여러가지가 있습니다. 연결 리스트로도 구현할 수 있고, 동적 배열로도 구현할 수 있습니다. 하지만 여기서는 편의상, 일반적인 정적 배열로 구현하기로 합시다.
스택을 배열로 구현하기 위해서는, 실제의 배열 하나와, 스택의 위치를 저장할 변수가 필요합니다. C++로 직접 선언해보면, 다음과 같이 됩니다.
Int stack[10], top;
Stack의 삽입과 삭제
스택의 삽입(push)의 구현은 간단합니다. 그냥 top을 1 증가시켜주고, 그 후 stack[top]에 데이터를 넣으면 됩니다.
void push(int data)
{
top++;
Stack[top]=data;
}
스택의 삭제(pop) 또한 간단합니다. Stack[top]을 반환하고, top을 -1 시켜주면 됩니다.
Int pop(int data)
{
Top--;
Return stack[top+1];
}
Overflow, Underflow
실제 스택은 push와 pop만 있으면 충분하지 않습니다. 스택의 사이즈 이상의 데이터를 push할 경우, 스택에 Stack Overflow라는 에러를 발생됩니다. 반대로, 스택이 빈 상태에서 데이터를 뺴내려고 할 때 발생하는 에러를 Stack underflow라고 합니다.
Stack Overflow와 Stack Underflow가 일어날 경우 프로그램에 문제가 생길 수 있기 때문에, 프로그래머는 위 두가지 에러가 일어나지 않도록 push와 pop 함수에 제한을 해 둘 필요가 있습니다. Stack overflow와 Stack underflow가 일어나지 않도록 하는 방법은, 각자 생각해보시기 바랍니다.
