[Python] 자료구조 - 스택

 

 

프로그래머스 lv 0과 lv 1은

어찌저찌해서 풀 수 있었으나

lv 2부터는 정말 기본기가 탄탄하지 않으면

풀기 힘들겠다고 느꼈습니다..

 

파이썬 알고리즘 문제 때문에 힘든 나날을 보내던 도중

 

https://brunch.co.kr/@jihyun-um/41

코딩 테스트 4단계 공부법

 

이 블로그를 발견하게 되었는데요,

 

이 블로그의 저자는 연습 문제를 풀기에 앞서 이론을 탄탄히 다지는 단계가 필요하다고 합니다.

이론을 공부하지 않고 닥치는 대로 문제만 푸는 것을

부실한 토지에 건물을 올리는 것이라고 비유합니다.

 

그러면서 기본 자료구조와 알고리즘을 공부해야한다고 하는데요,

그래서 당장 책을 구입하여 공부를 시작하였습니다.

 

 

---

 

 

스택

 

 

스택은 stack으로

stack의 의미는 무더기, 더미입니다.

 

당신이 주방에서 접시 무더기를 설거지를 한다고 가정해봅시다.

씻고 난 접시를 위에서부터 차곡차곡 쌓아서 올립니다.

그러면 요리사는 쌓여있는 접시를 위에서부터 하나씩 꺼내서 씁니다.

 

나중에 쌓은 접시부터 꺼내어져 사용됩니다.

이를 '후입선출'이라고 하죠.

 

 

접시와 마찬가지로

스택이라는 곳에

A, B, C를 삽입하면

C, B, A 순으로 출력하게 됩니다.

 

쉽죠?

 

 

---

 

 

스택의 특징

 

 

파이썬에는 '스택'이라는 자료형이 구현되어 있지 않습니다.

따라서 클래스를 통해서 구현을 해야합니다.

 

클래스로 구현할 때 생각해줘야할 것으로

멤버변수와 멤버함수가 있습니다.

 

 

멤버변수는 스택에 포함된 데이터로

array(): 저장될 배열(리스트)

capacity(): 스택의 최대 용량(리스트는 용량이 없긴 합니다..)

top(): 최상단 요소의 위치

 

멤버함수는 스택의 연산으로

 

삽입,

삭제,

스택의 전체 요소 수를 return,

최상단의 자료를 확인,

스택이 가득 찾는지 여부,

스택이 비어있는지 여부를

 

구현해줘야 합니다.

 

 

---

 

 

스택 구현

 

 

1. 파이썬의 리스트를 사용

s = list()
msg = input() # msg에 문자 입력해서 저장

for c in msg:
    s.append(c) # 스택에 삽입

print('문자열 출력: ', end = ' ')
while len(s) > 0:
    print(s.pop(), end= ' ') # 마지막 요소를 꺼내기
print()

 

예를들어 msg에 '자료구조'를 넣었다면

'조구료자'가 나오게 됩니다.

 

 

2. 파이썬 라이브러리 사용

 

import queue
s = queue.LifoQueue(maxsize = 20)

msg = input()
for c in msg:
    s.put(c)

print('문자열 출력: ', end = ' ')
while not s.empty():
    print(s.get(), end = ' ')
print()

 

queue 라이브러리의 LifoQueue를 사용하여 스택을 구현할 수도 있습니다.

 

maxsize를 통해 스택의 크기를 지정해주고

put()을 통해 스택에 요소를 삽입하고

get()을 통해 스택의 요소를 삭제하고 리턴합니다.

 

 

---

 

 

순환 호출

 

 

함수가 자기 자신을 다시 호출하여 문제를 해결하는 프로그래밍 기법입니다.

함수가 자신을 다시 호출할 때마다 시스템 스택에 쌓이게 됩니다.

 

함수 호출에 의한 부담과

시스템 스택을 많이 사용하면 느려진다는 단점이 있지만

 

트리, 이진 탐색이나 퀵 정렬 등과 같은 알고리즘을

구현할 때 크게 도움이 됩니다.

 

아주 쉬운 예로

팩토리얼 구현이 있습니다.

 

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

 

이렇게 하면 factorial() 함수는

n에서 시작하여 (n-1).... 2, 1의 순서대로 함수를 쌓고

factorial(1)의 함수의 연산이 끝나면

factorial(2)로 가고

.

.

.

factorial(n)까지 연산을 하게 됩니다.

 

 

마치 설거지한 접시를 쌓는 것과 같습니다.

 

쉽죠?