24. Stack

우리가 다수의 데이터를 한번에 다루고자 했을 때엔, 배열을 사용했었다.

 

그러나 기존에 사용하던 배열은, 배열의 크기를 상수로 지정해야 했으며, 런타임 중 능동적인 배열의 크기 변화를 필요로 할 경우에 불리하였다.

 

물론, 14. Array 클래스의 기능을 다루었을 때, Resize라는 빌트인 메서드를 통해 배열의 크기를 변경할 수 있으나, 배열에 값을 추가하거나 삭제할 때 마다 해당 메서드를 호출해야하므로 연산상의 부담이 더해진다.

 

이를 더 편리하고 효율적으로 관리하기위해, c#에서는 여러가지 자료구조들을 제공하는데, 오늘 다루어볼 것은 Stack이다.

 

Stack은 배열 기반의 자료구조로 가장 큰 특징으로는 후입선출(Last in First out)이 있다.

 

후입선출은 말 그대로, 나중에 나온 것이 맨 처음으로 나온다는 것이다.

 

맨 처음 나온 것은, 가장 나중에 나오게 될 것이다.

 

연상해보자면, 프링글스 과자를 떠올려보자.

 

우리가 프링글스 과자를 먹기위해서는, 뚜껑을 열고 포장지를 뜯어 맨 위의 과자부터 순서대로 빼먹게 된다.

 

프링글스를 먹다가 갑자기 맨 아래에 있는 프링글스 맛과 맨 위에있는 프링글스의 맛을 비교해보고 싶어져서 아래부분을 뜯어 맨 아래와 맨 위의 과자를 동시에 꺼내 먹는사람은 드물 것이다. 

 

가장 먼저 담긴 프링글스는 가장 마지막에 먹을 수 있듯, Stack의 구조도 이와 같다.

 

따라서 Stack은 맨 처음 저장한 데이터를 가장 나중에 사출할 때. 혹은, 가장 최근에 넣은 것을 가장 먼저 사용할 필요가 있을 때 사용하기 용이하다.

 

 

 

 

Stack은 Top이라고 하는, Stack 안에 있는 것 중 가장 최근에 넣어진 곳의 위치를 알려주는 녀석이 있다.

 

쉽게 말해서, 먹다남은 과자를 밀봉하기위해 밀봉 클립을 꽂아두는 경우가 있는데, 이 밀봉 클립이 바로 Stack의 Top이다.

 

과자를 밀봉할 때, 안의 공간을 많이 남겨두고 클립을 꽂지 않고, 최대한 공기를 빼낸 채로 클립을 꽂지 않는가?

 

내용물의 바로 위에 클립을 꽂아두어 밀봉하듯이, Top도 가장 최근에 넣은 데이터 바로 위에서 가장 최근에 넣은 자료를 가리킨다.

 

날아가기 쉬운 종이의 맨 위에 날아가지 않도록 올려두는 지우개 같은 것이라고도 할 수 있겠다.

 

이 Top은 Stack에 자료가 삽입될 때 마다 해당 자료를 가리키게 된다.

 

이를 통해, Stack의 가장 최근 자료가 무엇인지, Stack에 쌓여있는 데이터의 갯수가 몇개인지를 알 수 있다.

 

Top은 Stack이 생성될 때 -1로 초기화 되고, Stack에 Push를 통해 새 값이 저장되는 순간 증감식을 통해 1이 증가하여 인덱스 0을 가리키게 된다.

 

이와 같은 방식으로 Push를 통해 Stack에 값이 계속 저장될 때 마다, Top은 가장 윗부분을 가리키게 된다.

 

 

 

 

다음은 Stack의 생성 방법과 사용 방법이다.

 

 

 

static void Main(string[] args)
{
    Stack<int> stack = new Stack<int>();
    stack.Push(1);
    stack.Push(2);
    stack.Push(3);
    
    Console.WriteLine(stack.Pop());
    Console.WriteLine(stack.Pop());
    Console.WriteLine(stack.Pop());
    
    // 출력값 : 3 2 1
}

 

먼저 Push 기능은 Stack안에 데이터를 밀어넣는 것이다.

 

이는 STL의 vector를 다룰 때도 사용했었다. 다만, 이번엔 뒤에서 밀어넣는 것이 아니라 그저 넣을 뿐이다.

 

vector처럼 모든 값이 한칸씩 이동하면서 밀어넣어지는 것이 아니라 처음 넣을 때 부터 가장 밑바닥에 깔리게되는 것이다. 

 

이렇게 Push될 때, Top의 위치 역시 한 칸 올라가 가장 윗 부분을 가리키게 된다.

 

배열을 예로 들었을때, Push가 호출되는 순간, 배열 arr[++Top]에 매개변수의 값이 저장되는 식이다.

 

top은 생성자를 통해 -1로 초기화된다고 설명했었다. 따라서 맨 처음엔 0번째 인덱스에 해당 값이 저장되는 식으로,

이것이 반복되는 구조다.

 

 

 

Pop은 가장 바깥쪽에 있는. 그러니까 가장 최근에 넣은 Stack의 값을 사출, 해당 값을 반환하는 기능이다.

 

이는 vector때와 같지만, 마찬가지로 모든 인덱스에 해당하는 값이 이동하지는 않고, 맨 위의 값만 혼자 나오는 것이다.

 

위 처럼 Push를 통해 1, 2, 3 순서대로 Stack에 넣은 값들은 위에서부터 순서대로 3, 2, 1 순으로 정렬되어있으며,

해당 값을 Pop을 통해 사출하여 값을 가져온다면, 위에서부터 3, 2, 1순서대로 사출되어 위와같이 3 2 1을 출력하게 된다.

 

Pop을 통해 값이 사출되면, Top역시 증감식을 통해 값이 줄어들게 된다.

 

위와 마찬가지로 배열을 통해 설명했을 때, 현재 가장 위에 위치해있는 arr[Top]의 값을 임시로 저장하고,  arr[Top--]값을 비운 다음, 임시로 저장한 arr[Top]값을 반환하게 되는 것이다.

 

 

 

 

 

Top의 기능은 현재 Stack의 데이터 갯수를 나타내는 역할로만 기능하지 않는다.

 

현재 Stack이 Push를통해 새 값을 입력받게될 경우에, 저장 한도를 넘어 오버플로우가 생기는지의 여부를 알려줄 수도 있다.

 

Stack의 최대 저장 갯수가 10개라고 가정한다면, Top의 값이 10이면 더이상 값을 집어넣지 못하기 때문에 이를 이용자에게 알려주는 것이 가능하다.

 

반대로, Stack이 Pop을통해 기존의 값을 반환하고 해당 값을 초기화하고자 할 때, 남아있는 데이터가 없어, 언더플로우가 발생하는지의 여부를 알려주는 것도 가능하다.

 

Top의 값이 초기와 같은 -1이라면, 해당 Stack에는 꺼낼 값이 없으므로 이 Stack은 비어있는 Stack이라고 알려줄 수 있다.