파이썬 알고리즘 기초 - 스택(Stack)

이번 시간에는 '스택'에 대해서 다뤄 보겠습니다. 

 

출처:https://amzn.to/2RKPXkD

이게 스택입니다. 말 그대로 '스택' 그 이상도 그 이하도 아니네요. 

자, 저 책 하나하나를 데이터로 생각해볼게요. 일반적으로 생각해볼 때, 책을 어떻게 안정적으로 꺼낼 수 있을까요?

예를 들어, 위에서 10번째에 위치한 책(=데이터)를 꺼내고 싶은데  그 위까지 책을 한 팔로 살 짝 들어서 옆으로 싹 뺀다면, 안 무너뜨릴 자신 있으신가요? ㅎㅎ 위에서부터 9권을 내리고 10번째 책을 빼는게 안정적이겠죠? 

 

스택 이라는 자료구조가 그렇습니다. 저 스택을 쌓을 때 위에 있을수록 더 늦게 쌓은 책이잖아요? 

나중에 입력한 데이터를 먼저 빼는(LIFO) 데이터 구조가 스택입니다! 

저는 스택이라는 데이터 구조를 생각할 때, 저렇게 위태위태하게 쌓은 이미지를 상상합니다. 

그래야만 우리는 늦게 넣은 데이터를 먼저 뺀다는 생각을 할 수 있습니다! 

 

자, 이제 조금 더 CS적인 느낌으로 보겠습니다. 

 

이러한 스택이 있습니다. 여기에 53이라는 데이터를 넣어 보겠습니다.

스택에서는 이를 push 라고 합니다. 

 

 

 

이번에는 데이터를 꺼내 보겠습니다. 스택에서는

데이터를 꺼내는 걸 pop 이라고 합니다.

 

 

 

 

간단하죠? 

 

정리하겠습니다. 

스택은  LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따릅니다. 

 

-LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책

-FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책

 

주요기능은

 

push(): 데이터를 스택에 넣기

pop(): 데이터를 스택에서 꺼내기

 

입니다. 

 

아래 그림을 음미해주세요~

출처:https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

1) 재귀함수로 스택 구현하기 

 

스택은 재귀 함수를 공부할 때도 많이 언급됩니다. 

재귀적으로 구현이 가능하기 때문입니다. 

 

recursive(4) # 4

    recursive(3) # 3

        recursive(2) # 2

            recursive(1)  # 1  

                                      # ended 

                                          # returned 0

                                                # returned 1 

이하 생략

 

위와 같이 재귀적으로 함수가 구현이 되는데요.

# 부분이 출력되는 값입니다. 직접 하나하나 글로 표기하면서 print 를 중심으로 보면 왜 위와 같은 결과가 나오는지

그리고 재귀적으로 스택이 구현되는지 감이 오실 겁니다 :) 

 

2)  파이썬 리스트가 갖고 있는 append(push), pop 메서드로 스택 구현하기

 

간단하죠? 

 

3) pop 없이 파이썬으로 구현해보기 

 

pop에서 인덱싱을 이용해서 구현할 수 있습니다. 

 

 

 

이번 포스팅도

패스트캠퍼스 온라인 강좌인 '알고리즘 기술면접 완전 정복'을 참고 했습니다. 

감사합니다 :)