Introducing. Stack.

본 스터디는 열혈강의 자료구조 - 프리렉이란 교재로 진행된다. 더욱 자세한 내용은 해당 책을 참고하기 바란다. 정말 괜찮은 책이다.

스택을 소개합니다.

• 영어 단어로 더미(Stack).
• 가장 대표적 성질은 나중에 들어간게 먼저 나온다. (Last-In-First-Out;LIFO;리포)
• 같은 성질인데 말을 조금 바꾸면 ‘먼저 들어간게 나중에 나온다’ (First-In-Last-Out;FILO)
• 선형 자료구조 : 앞뒤 자료가 1:1
• 꺼내는 것(반환)과 삭제, 추가는 스택의 제일 위에서만 가능하다.

스택의 개념

위키피디아에서 설명하는 스택.

스택은 한방향으로 쌓는 자료 구조이다. 새로운 자료를 스택에 추가하는 것을 push라고 한다. 그리고 스택에서 자료를 꺼내는 것을 pop이라고 한다. 이때 꺼내지는 자료는 최상단(가장 마지막에 들어간)의 자료다. 이때 말하는 가장 마지막에 삽입된 자료를 top이라 한다. 그리고 그 마지막 자료를 꺼내지 않고 보기만 하는 것을 peek라 한다.

푸시(push)연산.

| |
| |
|B| <- top
|A|

이렇게 생긴 스택 공간이 있다고 하자. 자료 C를 추가하게 되면,

| |
|C| <- top
|B|
|A|

로 바뀌게 된다. 아래서 부터 인덱스를 붙이면 2번자리에 C가 저장됨을 알 수 있다.

스택의 크기란 스택에 저장할 수 있는 최대의 자료 개수를 말한다. 최대 갯수가 제한이 있기 때문에 이 한도를 초과해서 추가하려고하면 추가될 수 없는 경우가 발생한다. 이 경우를 overflow현상이라 이야기한다.

팝(pop)연산.

다음으로 팝 연산에 대해 살펴보도록 하자. 팝은 스택에서 자료를 꺼내는 것을 말한다. 이러한 팝 연산은 스택의 제일 위에서만 발생한다.

| |
|C| -> pop
|B| <- top
|A|

| |
| |
|B| <- top
|A|

위는 저장된 자료가 팝 연산에 의해 반환 되는 과정이다.

만약 아무 자료가 저장되지 않은 상태(empty 상태)에서 팝 연산을 호출하면 어떻게 되야할까? 아마도 아무자료가 없으니 제거할 자료가 없는 상황이 될 것이다. 이런 상황을 underflow현상이라고 말한다.

피크(peek)연산.

팝과 유사한 연산이다. 그러나 자료를 제거하지않고 단지 반환만 받을 수 있다는 점에서 차이가 있다.

| |
|C| <- top / -> peek
|B|
|A|

| |
|C| <- top
|B|
|A|

탑을 이용하여 스택의 최상위에 있는 가장 최근에 삽입된 자료를 반환한다. 오직 반환만 한다는 점에 주목하라.

스택의 추상 자료형

스택을 실제 사용하기 위해서는 다음 표에 있는 기능들이 필요하다.