스택(stack)

앞서 형태에 따른 자료구조의 종류를 살펴 보았습니다.

이번에는 선형구조의 가장 기본이 되는 스택에 대해 살펴보겠습니다.

스택(stack)은 영어 사전에서 찾아보면 '(건초, 밀집 따위를 쌓아 놓은) 더미, 낟가리'를 의미한다고 되어 있다.

스택의 예를 들면 식당에 쌓여 있는 접시 더미, 책상에 쌓여 있는 책, 창고에 쌓여 있는 상자 등을 들 수 있다.

스택을 창고에 쌓여 있는 상자를 이용하여 설명하자면,

우리는 보통 창고에서 새로운 상자들을 쌓을 때는 상자 더미의 맨 윗부분에 놓는다.

또 상자가 필요하면 상자 더미의 맨 위에 있는 상자를 꺼낸다. 만약 중간에서 상자를 꺼내면 전체 상자가 붕괴 될 것이다.

따라서 가장 최근에 들어온 상자가 가장 위에 있게 되고, 또 먼저 나가게 된다.

이러한 입출력 형태를 후입 선출(LIFO : Last-In First-Out)이라고 한다.

이제 간단히 어떤 형태의 자료구조 인지 감이 왔을 것이다.

컴퓨터 용어사전의 스택의 뜻을 빌려와보면

스택(stack) : 모든 원소들의 삽입(insert)과 삭제(delete)가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조

삽입과 삭제가 일어나는 리스트의 끝을 top이라 하고, 다른 한 쪽 끝을 bottom이라 한다. 

스택은 종종 pushdown stack이라고도 하는데, 스택의 top에 새로운 원소를 삽입하는 것을 push라 하고,

가장 최근에 삽입 된 원소를 의미하는 스택의 top으로 부터 한 원소를 제거하는 것을 pop이라 한다.

그리고 현재 스택에서 top의 위치에 있는 데이터를 확인하는 것을 peek라 한다.

이와 같은 스택 연산은 항상 스택의 top에서 발생하므로 top 포인터의 값을 1씩 증감시킴으로써 수행된다.

이러한 스택 자료구조를 사용하는데 알아야 할 오류가 두가지가 있다.

하나는 stack underflow이며, 스택이 비어 있을 때 pop 연산을 하는 경우 발생하게 된다.

그 이유는 더 이상 가져 올 데이터가 존재 하지 않는데 데이터를 가져오려 하기 때문이다.

또 다른 하나는 stack overflow이다. 스택이 할당 받은 공간에 데이터가 가득 차있을 때 

push 연산을 하는 경우 발생 하게 된다.

그 이유는 더이상 데이터가 추가 될 공간이 없는데 데이터를 추가하려 하기 때문이다.

이상으로 선형 자료구조 중 하나 인 스택의 설명을 마치려고 합니다.

파란색으로 정의 된 각 연산들이 무엇을 의미하는지 정확하게 알고, 개념을 이해 한뒤

c나 java를 통해서 한 번 구현 해보는 것이 가장 좋은 공부 방법이라 생각합니다.

소스코드가 필요하시다면 개인적으로 메일을 보내 드리거나 포스팅을 수정하도록 하겠습니다.