스택(Stack) ADT

이번 포스팅에서는 스택의 ADT에 대해서 알아보도록 하겠습니다.
스택은 자료구조 중에서도 정말 기본적인 자료구조입니다. 그렇기 때문에 보다 더 확실하게 짚고 넘어갈 필요가 있겠습니다. 그 후에, 이를 C언어를 통해서 구현해보도록 하겠습니다. 

---

스택이란 무엇인가요?

스택은 말하자면 한 곳에 모인 두꺼운 문서뭉치와도 같습니다. 문서 뭉치중에서 특정 문서에 접근하고 싶다고 해도 바로 접근하는 것이 불가능합니다. 위에 놓인 문서들부터 빼낸 후에야 원하는 문서에 접근할 수 있습니다.

 

이와 같이 먼저 넣은, 즉, 보다 더 과거에 넣은 자료가 보다 나중에 출력이 되고
보다 더 최근에 넣은 자료가 상대적으로 가까운 미래에 출력이 되는 선입후출(FILO), 또는 후입선출(LIFO)의 특징을 갖는 자료구조입니다.

 

이러한 특징에서 볼 수 있듯이, 기본적으로 자료를 입력하는 행위, 저장된 자료를 출력하는 행위의 두 가지 연산이 기본적으로 정의되어 있습니다. 그리고 이를 각각 PUSH와 POP이라 합니다.

 

하지만 이 연산만으로 스택 자료구조로 풍부한 기능을 구현하기에는 좀 벅찬 감이 있습니다. 따라서 추가적인 연산들을 스택 ADT에 명시해두겠습니다.

 

스택 ADT

ADT는 이러한 자료구조를 사용하는 사용자 입장에서 어떠한 입력값을 전달해주면 어떠한 기능을 수행하고, 어떠한 형태로 값을 반환하는지와 같은 정보를 명시해 둔, 메뉴얼과 같은 추상 자료형입니다. 

 

말 그대로 사용자 관점에서 정의한 것이기 때문에, 사용자는 이 프로그램에 직접적으로 접근할 수 없습니다.

 

 

---

• 자료형 정의(구조체 정의)

스택의 각 단위 메모리 공간을 연결리스트로 구현합니다.
이 스택은 선입후출의 성질에 근거해 정해진 위치에만 데이터를 삽입할 수 있고, 정해진 위치의 데이터에만 접근할 수 있다는 특징이 있습니다. 그렇기 때문에 스택을 관리할 때에는 필수적으로 그 스택에 가장 과거에 저장한 자료, 가장 최근에 저장한 자료를 지정할 포인터가 필요합니다.

또한 스택에서 데이터의 입력 및 출력을 할 때에는 현재 스택에 저장된 자료의 개수를 유용하게 사용합니다. 그렇기 때문에 추가적으로 스택이 현재 가지고 있는 자료의 개수를 저장하는 Stack 구조체를 정의합시다.

 

데이터를 실제로 저장하는 공간인 스택 연결리스트는 기본 연결리스트와 동일하게 데이터와 다음에 연결할 노드를 지정하는 next 포인터를 저장하면 되겠습니다.

---

• 스택에서 정의된 연산

1. void Push(Stack *stack, void *dataPtr)

Stack포인터 stack 을 전달받아 stack이 관리하는 stack - 연결리스트에 void 포인터로 캐스팅한 데이터의 포인터를 
입력합니다.

 

2. void Pop(Stack *stack) 

앞서 말했듯이 스택은 정해진 곳에서만 데이터의 입출력이 가능하므로 출력할 대상인 스택의 포인터만 전달하면, 그 스택의 가장 먼저 입력된 자료를 스택으로부터 제거합니다.

 

  주의:

많은 책에 Pop함수는 스택에서 데이터를 제거하는 기능과 그 데이터를 반환하는 기능을 수행하는 함수로 정의하고 있습니다. 하지만 한 함수에 여러 기능을 정의하는 것은 프로그램 관점에서 봤을 때 불안정하다고 할 수 있겠습니다. 따라서, 시험과 같은 맥락에서는 Pop함수를 void *Pop(Stack *stack)의 원형을 갖는 함수로 정의를 하시면 됩니다. 하지만 여러분이 실제로 어떠한 프로젝트를 진행하시는 경우, 함수 하나에 하나의 기능만을 할당하실 것을 권장드립니다.

 

3. Stack *createStack(void)

스택 구조체를 동적할당을 통하여 생성한 후에 그 스택 포인터를 반환하는 함수입니다.
이와 같이 동적할당을 통해 메모리공간을 생성하는 함수의 경우 할당이 제대로 되었는지를 잘 체크하셔야합니다.

 

4.void destroyStack(Stack *stack)

스택 구조체를 삭제하는 함수입니다. Push , createStack 함수에서 볼 수 있듯이, 정의된 메모리공간 중에 동적할당으로 정의된 것이 많습니다. 그렇기 때문에 free함수를 적절한 순서를 통해서 잘 사용하시는게 관건입니다.

 

5.Boolean isFullStack(Stack *stack)

스택에 정의된 메모리공간을 넘어가게 메모리가 입력되었는지를 알려줍니다. 하지만 우리는 지금 연결리스트로 스택을 구현하고 있기 때문에 크게 필요하지 않습니다. 

당연한 얘기지만 stack->count 와 기존에 스택의 사이즈를 비교해서 부울리언 값을 반환하면 되겠습니다.

 

6.Boolean isEmptyStack(Stack *stack)

전달 받은 스택포인터의 스택에 입력된 데이터가 없는지를 확인하면 되겠습니다.
가장 단순한 방법으로 stack->count == 0을 boolean으로써 반환하면 됩니다.

 

7.int countStack(Stack *stack)

전달 받은 스택에 입력된 데이터의 개수를 반환합니다. stack->count를 반환하면 됩니다.

 

 

---

 

이번 포스팅에서는 스택 ADT에 대해서 알아보았습니다. 스택이 갖는 특징인 후입선출에 근거해서 
스택이 자료를 관리하고 추가, 삭제, 접근하는 방법을 알아보았습니다.

다음 포스팅에서는 C코드를 통해서 위에서 설명한 스택을 간단하게 구현해보겠습니다. 감사합니다.