자료구조 스택 : 먼저 넣은 것이 나중에 빠진다.

 재귀 호출에 대해서 저번시간에 쭉 배워보았습니다. 이번에는 자료구조 스택에 대해서 배워보고, 활용을 해 보도록 하겠습니다. 사실 계산기 프로그램 하나로 될 거 같긴 하지만, 더 좋은 예제가 없는지 고민을 해 보겠습니다. 하튼, stack은 나중에 넣은 원소가 먼저 빠진다는 특성 (Last In First Out : LIFO)을 가지고 있는데요. 주요 연산들만 간단하게 알아보는 시간 가지도록 합시다.

 

 

---

 먼저 스택은 크게 2가지 포인터로 이루어져 있습니다. base pointer, 줄여서 bp입니다. 그리고 top pointer, sp라고 많이 이야기를 할 거에요. base는 스택의 시작점이 되는 포인터, 그리고 top은 실제로 꼭대기에 있는 원소를 가리키게 되어요. 만약에, 비어 있다면 top은, 배열로 구현했다면 -1번째 원소를 가리킬 거에요. 그리고 data를 저장하는 배열은 동적 할당으로 생성할 거에요.

 

 

 이 상태에서 원소를 추가해 봅시다.

 

 

 그러면 top은 0번째 원소를 가리킬 겁니다. 즉, 여기서 맨 위에 있는 원소를 꺼내오라는 쿼리가 들어오면 5를 가져오게 되는 것입니다. 이제 또 다른 원소를 하나 더 넣어봅시다.

 

 

 그러면 sp는, 맨 위에 있는 원소인 7을 가리킵니다. 배열의 1번째 요소입니다. 즉, push 연산이 일어날 때 마다, sp는 다음 원소를 가리키게 됩니다. 스택의 맨 윗 부분이 바뀌고 있기 때문입니다. 이것을 동적 배열로 구현하면 어떨까요? 예를 들어서, 초기 capacity가 2였다고 해 봅시다. 이 상태에서 push 연산을 한 번 더 해 보겠습니다.

 

 

 그러면 스택의 size가 2인데, capacity도 2이기 때문에, expand를 해야 합니다. 그런가요? expand를 할 때는 기존 용량의 2배로 확장을 합니다. 그러면, 새롭게 할당한 공간은 4개의 capacity를 가지게 됩니다.

 

 

 그러면 새롭게 할당한 배열이 스택이 되어야 할 거에요. 기존에 있었던 것은 free나 delete 등으로 제거해 줍니다. 그리고 새롭게 할당한 것을 써 주면 되겠습니다.

 

 

  그리고 2를 추가해 봅시다. 그러면 top이 하나 증가할 거에요.

 

 

 즉 스택 꼭대기 포인터가 2번째 원소를 가리키게 됩니다. 사실 이러한 트릭은 C++의 vector나 Java의 ArrayList에서 볼 수 있어요. (다만, 자바의 어레이리스트는 grow rate가 1.5긴 하지만요). 그러니, 구현하기 힘드시다면 스택을 구현하실 때, Java의 ArrayList나 C++의 vector를 이용하셔도 현명한 선택이 되리라 생각합니다.

 

 

---

 이제 pop을 4번 해 봅시다.

 

 

 pop은 쉽습니다. 맨 꼭대기에 있는 원소를 제거하기 때문에, top, 그러니까 sp pointer를 하나 감소시켜주기만 하면 됩니다. 또 다시 pop 연산을 수행해 봅시다. 그러면 top 포인터가 5를 가리킬 겁니다.

 

 

 여기서 또 pop을 호출해 봅시다. 아직까지 원소가 남아있기 때문에, 스택 꼭대기 포인터는 하나 감소할 수 있어요.

 

 

 그런데 pop을 한 번 더 한 순간 top이 -1번째 원소를 가리킵니다. 스택이 비어있기 때문에, 이 상태에서 pop 연산이라던지, 맨 위의 원소를 뽑아오는 연산은 invaild 합니다. 즉, 스택이 비어있다면, 스택의 맨 위에 있는 원소를 뽑아오는 연산과 pop 연산이 invaild 합니다. 비어 있는데 pop을 하려고 하는 경우, 언더플로우라고 해요. 이 부분을 잘 컨트롤 하시면 손쉽게 구현하실 수 있습니다.

 

 정리해 봅시다. 자료구조 스택은 나중에 넣은 원소가 먼저 빠진다는 특징을 가지고 있어요. 동적 배열로 구현한다면, size랑 capacity가 같을 때, push 연산이 들어온다면 expand를 호출하시면 된다는 점. 그리고, pop과 맨 위에 있는 원소를 뽑아오는 연산은 비어 있다면 유효한 연산이 아니라는 것 정도만 정리하시면 되겠습니다. 추가로, 공간이 무한정 커질 수는 없으니, 적당히 컷팅을 해야 할 건데요. 보통 적당히 큰 수로 잡아요. 2천만에서 4천만?

 

 

 만약에 확장 후에 capacity가 Bound가 초과할 경우에 더 이상 expand를 하지 않게 하면 되어요. 사이즈가 Bound를 넘어가려고 하는 경우에 꽉 차서 더 이상 push를 못하게 하는 식으로 컨트롤 하셔도 무난합니다. 이 상태에서 더 추가하려고 하면 overflow다. 라는 처리를 해 주시면 됩니다. 몇 개의 프로그램을 구현해 보면서 스택에 대해서 이해를 해 보도록 하겠습니다.