리스트로 Stack 구현하기 (Python)

스택(Stack)은 큐와 반대로, 가장 나중에 넣은 데이터가 가장 먼저 나오는 구조로 저장하는 형식입니다.

따라서, 기본 구조는 LIFO(Last-In, First-Out)이며, 큐가 줄서기라면 스택은 책쌓기 입니다.

책상에 책을 쌓았을 때 가장 위에 있는(가장 마지막에 쌓은) 책을 먼저 꺼내는 행위와 같습니다.

프로그램을 구현하고 실행할 때, 실행된 프로그램을 '프로세스' 라고 부릅니다.

프로세스 내에 다양한 함수들이 존재하는데, 함수가 시작될 때 스택에 담기고 종료될 때 사라집니다.

즉, 스택은 컴퓨터 내부 프로세스 실행 구조의 가장 기본입니다.

재귀 함수를 구현해 보겠습니다.

def recursive(data):
    if data < 0:
        print('ended')  # 호출 후 함수가 끝납니다.
    else:
        print(data)
        recursive(data - 1)
        print('returned', data)  # 함수가 끝난 후 나중에 쌓인 순서대로 print 합니다.
  
recursive(4)
# 4
# 3
# 2
# 1
# 0
# ended
# returned 0
# returned 1
# returned 2
# returned 3
# returned 4

함수 위에 함수가 호출되면서 스택 구조로 상단에 쌓이게 됩니다.

최상단의 함수가 호출이 되면 사라지고 그 다음 상단의 함수가 호출이 되는 식으로 반복합니다.

스택의 장점은, 데이터를 넣고 빼는 가장 쉬운 방법 중 하나로, 구조가 단순해서 구현하기가 쉽습니다.

프로세스를 실행할 때 빠른 속도가 중요하기 때문에 단순한 스택 구조를 사용하는 것입니다.

스택의 단점은, 데이터를 무한정 쌓을 수가 없고, 데이터의 최대 개수를 미리 정해야 합니다.

미리 최대 공간을 확보하게 된다면, 평소에 쓰지 않는 부분까지 확보하게 되어 낭비가 쉽습니다.

위에서 구현한 recursive 함수의 경우에는 2950번까지 가능했고, 그 이상부터는 RecursionError: maximum recursion depth exceeded while calling a Python object 에러가 떴습니다.

push()는 데이터를 스택에 넣는 기능, pop()은 스택에서 꺼내는 기능을 말합니다.

data_stack = list()

data_stack.append(1)  # push()
data_stack.append(2)
data_stack.append(3)
data_stack.append(4)

data_stack
# [1, 2, 3, 4]

data_stack.pop()  # pop()
# 4
data_stack.pop()
# 3

data_stack
# [1, 2]

push()와 pop()을 아~주 간단히 구현할 수 있습니다.

stack_lst = list()

def push(data):
    stack_lst.append(data)
    
def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data