[Data Structure] Stack

Stack

Stack(스택)은 DS에서 가장 간단하면서도 중요한 개념입니다. DS 뿐만 아니라 앞으로 계속적으로 컴퓨터로 코딩을 하게된다면, 자주 접하게 될 것입니다! 오늘은 그러한 스택에 대해 알아보도록 합시다.

 

---

 

특징

Stack의 가장 큰 특징은 바로 LIFO 특성을 갖는다는 것입니다. LIFO란, Last In First Out 이라는 뜻으로, 풀이하자면 마지막에 들어간 것이 처음으로 나간다는 뜻 입니다.
감이 잘 잡히지 않을 분들을 위해 그림과 함께 예시를 들어드리겠습니다.

 

Stack의 In과 Out

<in>을 살펴보면, 1, 2, ... n 해서 총 n개의 숫자 박스가 빨간 상자 안으로 들어가고 있죠? 이 때, 들어온 순서는 어떻게 될까요? 조금만 생각해도 1, 2, 3, 4, ..., n 순서로 들어왔다는 것을 알 수 있습니다.

이제 <out> 부분을 살펴볼까요? 이 빨간 상자 안에서 다시 숫자 박스들을 꺼내게 되면, 가장 먼저 빠져나가는 박스는 몇 번째 박스일까요? 역시 당연하게도 n부터 빠져나가게 됩니다.

이처럼 가장 나중에 들어온 것이(Last In) 가장 먼저 나간다(First Out)고 하여 LIFO 라고 부르게 되었고, 이것이 Stack이라고 할 수 있습니다.

 

---

그럼 이러한 방식은 어디에 써요?

누군가는 이렇게 질문할 수도 있을 것 같네요. 얼핏 보면 불공평해보이죠? 늦게 왔는데 먼저 나간다니, 처음 온 것들한테는 얼핏 불공평해 보일 수도 있습니다. 하지만, 의외로 사용할 수 있는 곳은 많습니다.

우선, 이런 방식은 데이터의 순서를 바꿀 때에도 유용하게 사용할 수 있습니다. 아까의 빨간 상자와 숫자 박스로 다시 돌아가 봅시다. 분명 처음에는 1, 2, 3, ..., n 순서로 데이터가 들어왔겠죠? 그런데 데이터가 나갈때는 n, n-1, n-2, ..., 1로 나가게 됩니다. 이렇게 하면 입력되는 데이터의 순서가 달라지겠죠?

 

프로그램 상에서는 function call과 return이 이러한 방식을 취한다고 볼 수 있습니다. A에서 B를 호출하고, B에서 C를 호출했다고 가정해 볼까요? 이렇게 되면 C의 결과가 다시 B로 돌아가고, B의 결과가 다시 A로 돌아갑니다. 이 때에도 LIFO 방식으로 flow가 진행됩니다.

 

누군가 기계를 분해하고 다시 조립할 때에도 마찬가지입니다. 만약 냉장고를 분해하고 다시 조립하는 상황이 생겼다고 가정해 볼까요? 맨 처음으로 냉장고 문짝을 뜯어내었고, 다음으로는 그 안에 있는 선반을 뜯었다고 생각해 봅시다. 이런식으로 분해해서 마지막으로 냉장고 안쪽의 어떤 나사를 푸는것으로 마무리를 지었습니다. 이제 다시 조립을 해 볼까요? 어떤것부터 해야 할까요? 아마 마지막으로 분해했던 그 나사를 다시 조립하는 일이 되지 않을까요? 그렇게 다시 조립하다보면 맨 마지막에는 냉장고 문을 조립하고 있을 것입니다.

---

각종 연산들

Stack에는 여러 연산이 있습니다. 그 중, Stack에 데이터를 넣고 빼는 연산이 바로 Push()와 Pop()입니다.

Push() 는 Stack에 값을 집어넣는 연산입니다. 마지막으로 들어간 요소는 Top으로써 언제든 Pop() 연산을 통해 나갈 준비가 되게 됩니다.

이제 연산들에 대해 잠깐 살펴볼까요?

1. CreateStack()

이 연산은 Stack을 생성해주는 연산입니다. 기본적으로 초기 생성된 Stack은 비어있습니다.

2. Push()

이 연산은 Stack에 새로운 원소를 추가하는 연산입니다.

3. Pop()

이 연산은 Stack의 가장 마지막에 들어온 원소(Top)을 꺼내는 연산입니다. 꺼내진 원소는 Stack에서 제거됩니다.

4. Full_check()

이 연산은 현재 Stack이 꽉 차있는지 아닌지 확인하는 연산입니다. 꽉 차있다면 True, 그렇지 않다면 False를 반환합니다.

5. Empty_check()

이 연산은 현재 Stack이 비어있는지 확인하는 연산입니다. 비어있다면 True, 비어있지 않다면 False를 반환합니다.

 

 

이 외에도 경우에 따라 Top() 연산 등을 구현하거나 작동시킬 수 있습니다.

---

Stack은 Queue와 더불어 가장 기초가 되는 Data Structure입니다. 잘만 사용하면 정말 유용하게 사용할 수 있는 구조이며, 많은 경우 기본 라이브러리에 포함되어있으니 사용법을 꼭 익혀두시기 바랍니다.