이번 시간에는 '스택'에 대해서 다뤄 보겠습니다.
이게 스택입니다. 말 그대로 '스택' 그 이상도 그 이하도 아니네요.
자, 저 책 하나하나를 데이터로 생각해볼게요. 일반적으로 생각해볼 때, 책을 어떻게 안정적으로 꺼낼 수 있을까요?
예를 들어, 위에서 10번째에 위치한 책(=데이터)를 꺼내고 싶은데 그 위까지 책을 한 팔로 살 짝 들어서 옆으로 싹 뺀다면, 안 무너뜨릴 자신 있으신가요? ㅎㅎ 위에서부터 9권을 내리고 10번째 책을 빼는게 안정적이겠죠?
스택 이라는 자료구조가 그렇습니다. 저 스택을 쌓을 때 위에 있을수록 더 늦게 쌓은 책이잖아요?
나중에 입력한 데이터를 먼저 빼는(LIFO) 데이터 구조가 스택입니다!
저는 스택이라는 데이터 구조를 생각할 때, 저렇게 위태위태하게 쌓은 이미지를 상상합니다.
그래야만 우리는 늦게 넣은 데이터를 먼저 뺀다는 생각을 할 수 있습니다!
자, 이제 조금 더 CS적인 느낌으로 보겠습니다.
이러한 스택이 있습니다. 여기에 53이라는 데이터를 넣어 보겠습니다.
스택에서는 이를 push 라고 합니다.
이번에는 데이터를 꺼내 보겠습니다. 스택에서는
데이터를 꺼내는 걸 pop 이라고 합니다.
간단하죠?
정리하겠습니다.
스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따릅니다.
-LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
-FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
주요기능은
push(): 데이터를 스택에 넣기
pop(): 데이터를 스택에서 꺼내기
입니다.
아래 그림을 음미해주세요~
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에서 인덱싱을 이용해서 구현할 수 있습니다.
이번 포스팅도
패스트캠퍼스 온라인 강좌인 '알고리즘 기술면접 완전 정복'을 참고 했습니다.
감사합니다 :)
'Python_programming > 알고리즘' 카테고리의 다른 글
파이썬 알고리즘 기초 - 큐(Queue) (0) | 2020.01.31 |
---|---|
파이썬 알고리즘 기초 - 하노이의 탑 (재귀 알고리즘) (2) | 2020.01.26 |
파이썬 알고리즘 기초 - 이진 탐색(binary search) (0) | 2020.01.24 |
파이썬 알고리즘 기초 - 선형 배열 (feat. 시간 복잡도) (0) | 2020.01.24 |