[파이썬] 자료구조 : 재귀함수 & 스택구조 & LIFO구조

재귀함수(Recursive function) : 자기 자신을 부르는 함수

리스트(List) : 동적인 배열 (튜플(tuple) : 정적인 배열)

LIFO : Last in Fisrt out

 

스택(stack) : 일종의 바닥이 막힌 상자 혹은 더미, 나중에 넣은 물건은 나중에 꺼낼 수 밖에 없는 구조,

LIFO(Last In First Out) 라고도 한다.

 

스택(Stack) : 더미

재귀함수를 이용해서 이 스택구조를 구현하겠습니다. (Push는 자료를 입력, Pop은 자료를 출력)

#재귀함수를 이용한 스택구조
def stack(start , end):
    if start <= end:
        print('Push :', start)
        stack(start + 1, end)
        print("Pop  :", start)
    else:
        print("--------")

stack(0, 5)

#결과
Push : 0
Push : 1
Push : 2
Push : 3
Push : 4
Push : 5
--------
Pop  : 5
Pop  : 4
Pop  : 3
Pop  : 2
Pop  : 1
Pop  : 0

짧은 코딩이지만, 조금은 생각해야 합니다.

 

 

List를 이용하여 간단히 스택구조를 구현할 수 있습니다.

#List를 이용한 스택구조
data_stack = list()

for i in range(10):
    data_stack.append(i)
    print('Push :', data_stack)

for i in range(10):
    data_stack.pop()
    print('Pop  :', data_stack)
    
#결과
Push : [0]
Push : [0, 1]
Push : [0, 1, 2]
Push : [0, 1, 2, 3]
Push : [0, 1, 2, 3, 4]
Push : [0, 1, 2, 3, 4, 5]
Push : [0, 1, 2, 3, 4, 5, 6]
Push : [0, 1, 2, 3, 4, 5, 6, 7]
Push : [0, 1, 2, 3, 4, 5, 6, 7, 8]
Push : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Pop  : [0, 1, 2, 3, 4, 5, 6, 7, 8]
Pop  : [0, 1, 2, 3, 4, 5, 6, 7]
Pop  : [0, 1, 2, 3, 4, 5, 6]
Pop  : [0, 1, 2, 3, 4, 5]
Pop  : [0, 1, 2, 3, 4]
Pop  : [0, 1, 2, 3]
Pop  : [0, 1, 2]
Pop  : [0, 1]
Pop  : [0]
Pop  : []

 

좀 더 직관적이고, 간단한 방법으로 스택구조를 구현할 수 있습니다. 

 

스택구조는 많은 곳에서 사용됩니다.

 

윈도우에서 Ctrl+Z,  브라우저에 뒤로 가기 등 스택구조로 동작합니다. 

 

간단한 구조이지만, 많이 쓰이기 때문에 반드시 알아야 하는 구조입니다.