Stack은 데이터의 추가 및 제거가 자료구조의 상단에서만 발생할 수 있는 동종 데이터의 그룹입니다. LIFO(Last In First Out)구조라고 할 수 있습니다.
예를들어 동전을 쌓게 된다면 첫 번째 동전을 두고 그 위에 동전을 쌓고 또 쌓고 이 과정을 반복합니다. 그리고 다시 동전 탑을 원래대로 돌려놓을 때 위에서 부터 하나씩 내려놓죠. 이런 일련의 과정이 Stack구조가 데이터를 추가하고 제거하는 방식과 유사합니다.
Stack에 대한 개념 설명을 넘어 상세한 구현 논리에 대해 설명해보겠습니다.
Stack의 class
member variable: int top, int items[5]
member function: Push, Pop, MakeEmpty, IsFull, IsEmpty
*설명을 위해 Stack을 크기 5짜리 배열로 두고 진행하겠습니다.
Push(Stack에 데이터를 추가한다)
Stack구조가 만들어지면 다음과 같이 초기화 될것입니다. 배열은 비어있고 Stack 클래스의 멤버변수인 ‘top’은 -1로 초기화 되는 것이죠.
그림2에서 갑자기 Top이 [0]위치로 이동한 것을 알 수 있는데 Stack구조에서 Push 함수를 호출할 시 Top에 1을 더해주기 때문입니다.
그림3을 보면 Top이 위치한 [0]에 Data0이 삽입 된 것을 알 수 있습니다. 이처럼 Top은 데이터가 들어올 곳을 가리키는 일종의 포인터 역할을 합니다.
그림4를 보면 다시 Top이 +1된 것을 알 수 있습니다. 새로운 Data가 들어올 것이라는 것을 예상해볼수 있습니다.
예상했던대로 그림5에서 Top이 위치한 [1]에 Data1이 들어온 것을 알 수 있습니다.
그림5에서 Push 함수를 반복 수행해서 그림6의 상태가 되었습니다. 여기에서 다시 Push함수를 수행한다고 가정해보겠습니다. 사실 Push함수 내부에서는 IsFull함수의 결과에 따라 데이터를 추가할지 말지 결정을 합니다. 그리고 IsFull함수는 현재 Stack 구조에서 데이터가 꽉 찼는지 여부를 판단하고 꽉찼다면 True를, 아니라면 False를 반환합니다.
그렇다면 IsFull함수가 어떻게 데이터가 꽉 찼는지 판단할까요? 바로 멤버변수 Top을 통해서입니다. 그림6을 보시면 현재 Top은 [4]에 위치합니다. 그리고 해당 배열은 크기가 5개짜리이고 [4]이상의 index를 가질 수가 없습니다. 그렇기 때문에 Top도 그 이상으로 나아갈 수가 없게 되며 이런 논리를 토대로 Top이 ‘배열의크기-1'과 같다면 Stack에서 배열이 꽉 찼는지 여부를 알 수 있게 되는 것입니다. 해당 배열의 크기는 5이며 -1을 계산하면 4가 나오기 때문에 현재 Top이 가리키는 index의 값과 같습니다. 그렇기 때문에 IsFull함수는 현재 Stack 배열이 꽉 찼다고 판단하는 것이지요.
그림6에서 Push를 수행해도 내부의 IsFull이 True로 반환될 것이고 Push는 데이터를 추가하지 않을 것입니다.
Pop(Stack에서 데이터를 추출한다)
이번에는 Stack에서 데이터를 뽑는 Pop멤버함수의 구현 논리를 살펴보겠습니다. 그림7을 보면 Stack 배열이 꽉 차있다는 것을 알 수 있습니다.
그림7에서 Pop함수를 수행하면 그림8과 같은 모습으로 Stack 배열의 상태가 변하게 됩니다. 동작순서로는 먼저 Top이 가리키는 [4]에 위치하던 Data4를 임시 int형 변수 temp에 복사해주고 Top-1을 수행하는 것입니다. 그리고 temp 담겨있던 Data4는 Pop함수의 반환값이 됩니다. (Pop 함수를 수행하면 지워질 데이터를 반환하기 때문에 ‘제거’ 대신에 ‘추출’로 어휘선정을 했습니다)
그림8에서 다시 한 번 Pop함수를 수행하면 그림9 상태가 됩니다. 이번에도 역시 Top이 -1 연산이 되어 [2]를 가리키는 모습과 item[3]에 존재하던 Data3이 없어진 것도 확인 할 수 있습니다.(Data3은 Pop함수의 반환값이 될 것이다)
하지만 사실 그림8,9에서 보여지는 Stack 배열의 상태는 직관적인 이해를 위해서 추상적인 개념으로 설명한 것입니다.(추상적 개념도 Stack 배열의 메커니즘을 이해하는데는 상관이 없습니다. 그렇지만 실제 메모리상에서 어떤 구조로 동작을 할지 살펴보겠다는것이죠.) 그렇다면 실제로는 메모리에서 어떤 논리로 Pop함수가 다뤄지게 될까요?
Pop함수를 논리적 개념으로 설명해드리겠습니다. 그러기 위해서 다시 Stack 배열을 꽉 채웠습니다.
그림10에서 Pop함수를 수행했습니다. 추상적 개념과의 차이점은 바로 Data4가 아직 배열 안에 존재한다는 것입니다. 사실 Pop함수가 수행되면 임시변수 temp를 만들어 Top이 가리키는 Item[4]의 값을 temp에 복사하는것, Top의 값에 -1을 수행하는 것, Pop함수의 반환값으로 temp를 return 시켜주는 것 이외에는 추가 동작이 없습니다. 그렇기 때문에 아직 배열에 Data4가 남아있게 되는 것입니다. (즉, Data4를 없애는 코드는 수행되지 않았다는 것이죠)
그렇다면 어째서 저렇게 버젓이 Data4가 남아있는데도 Data4이 추출되었다고 취급될 수 있는 것일까요? 그것은 바로 이 자료구조가 Stack이라는 것으로 설명이 됩니다. 이 글의 시작부분에서 Stack은 데이터의 추가 및 제거가 상단에서만 이뤄진다고 설명을 드렸었습니다. 그렇다는 것은 다른 방법으로는 삭제도, 접근도, 추가도 할 수 없다는 것을 의미합니다. 오직 Push와 Pop, MakeEmpty(밑에서 설명)만으로 Stack 배열을 제어할 수 있다는 말이지요.
그림11에서 Data4가 존재하는 [4]에 다시 접근하기 위해서는 어떤 방법이 있을까요? 우선 Top을 [4]로 다시 이동시켜야 할 것입니다. 그렇다는 것은 Push 함수를 수행해서 Top에 +1을 하고 새로운 데이터를 item[4]에 추가한다는 것을 의미합니다.(Push가 성공적으로 수행되면 새로운 데이터를 추가하게됨) 즉, Data4는 다른 데이터에 의해 덮어씌워진다는 것을 의미하는 것이죠. 바로 이것이 그림11에서 Data4를 삭제된 데이터로 취급하는 이유입니다.
이번엔 그림12에서 Pop함수를 5번 수행했다고 가정해보겠습니다. Pop함수는 Top에 -1을 수행하기 때문에 총 -5가 연산되어 -1이 된다는 것을 알 수 있습니다. 이렇게 되면 Stack 배열이 현재 비어있다고 볼 수 있는데요. 아무래도 그림13에서는 논리적인 개념으로 다가간 배열의 모습이기 때문에 비어져있는 모습이라고 생각 되기 힘드실수 있을거라고 생각합니다. 그래서 이해를 돕기위해 다시 추상적 개념으로 설명을 진행하겠습니다.(다시 말하지만 추상적 개념으로 이해하셔도 Stack 구조의 메커니즘을 이해하시는데는 아무런 지장이 없습니다, 다만 실제 논리적인 개념은 저렇다는 것만 알고 계시면 됩니다!)
추상적 개념으로 생각한다면 안에 있던 모든 데이터가 사라진 Stack 배열은 그림14와 같을 것입니다. 그런데 만약 여기서 한 번 더 Pop함수를 수행한다면 어떻게 될까요?
이 부분을 생각해보기 전에 아셔야할 게 있습니다. 사실 Pop함수를 통해 데이터의 추출을 진행하기 전에 한 단계 거쳐야하는 함수가 있다는 것인데요, 그 함수는 바로 IsEmpty라는 함수입니다. 이 함수는 배열이 비었는지의 여부에 따라 True와 False를 반환하는 함수입니다. True면 Stack 배열이 비어있다는 뜻이므로 Pop함수가 호출 되더라도 데이터 추출 작업이 진행되지 않게 되고 False면 Stack 배열이 비어있지 않다는 것이므로 Pop함수를 정상적으로 수행하게 되는 것입니다.
그렇다면 IsEmpty는 어떻게 Stack배열이 비었는지의 여부를 판단하는 것일까요? 그것은 바로 Top이 -1인지 판단하면 됩니다. 그렇기 때문에 그림14에서 다시 Pop을 수행한다면 IsEmpty에 의해 검사를 받게 될테고 True가 나올 것이기 때문에 아무런 데이터도 추출되지 않을 것입니다.(추출 될 데이터가 없기 때문에)
MakeEmpty(Stack배열 내의 모든 데이터를 삭제한다)
그림15는 MakeEmpty함수를 설명해드리기 위해 다시 꽉찬 배열을 준비한 것입니다.
방금 IsEmpty를 설명드리면서 Top이 -1이 되면 비어있는 Stack 배열로 취급된다는 설명을 드렸었는데요, 그렇다는 것은 어떤 상태의 Stack 배열에서도 Top에 -1만 넣어준다면(MakeEmpty함수를 수행한다면) 빈 배열이 된다는 것을 의미합니다. 그림15의 Top은 [4]에 위치하고 있습니다.
그리고 그림16은 그림15에서 MakeEmpty를 수행하여 Top에 -1을 대입한 상태의 Stack 배열입니다. 아까 언급됐던 논리적 개념의 Stack 배열의 모습이죠? 논리적 개념으로 설명을 진행해야 MakeEmpty의 원리를 이해하실수 있기 때문에 논리적 개념으로 설명을 진행하도록 하겠습니다. 현재 배열이 가지고 있는 공간은 [0], [1], [2], [3], [4]이며 Stack 배열에서는 오직 Top으로만 접근이 가능합니다. 그리고 -1인 Top을 [0], [1], [2], [3], [4]쪽으로 이동시키기 위해서는 여러분도 이제 아시다시피 Push를 통해서만 ,그것도 점진적으로만 접근이 가능하고 [0], [1], [2], [3], [4]에 존재하는 데이터 값들은 Push에 의해서 모두 다시 새로 설정될 것이라는 것도 이미 아실 것입니다. 즉 정리해서 말하자면 Stack 배열이 어떤 데이터들로 채워져있고 몇 개의 데이터가 들어가있더라도 MakeEmpty를 수행해 Top이 -1이 되는 순간 실제 배열 안에는 값이 남아있을지라도 모두 삭제된 데이터로 취급된다는 것입니다.(값이 다시 덮어씌어 질 것이므로 미리 없는 데이터 취급을 하는 것이죠!)
이번 글에서는 Stack을 배열로 구현 했을 때의 동작 논리에 대해 얘기해봤습니다. 추후에 Stack을 Linked로 구현했을 때의 동작 논리도 소개해드림으로써 같은 자료구조라도 구현 방식에 따라 다른 동작 논리를 보인다는 것을 설명해드리도록 하겠습니다! 오늘도 긴 글 봐주셔서 감사하며 다음 글에서는 배열로 구현된 Queue에 대해 설명해드리겠습니다.
