데이터 구조3. 스택(Stack) 파이썬에서 구현하기

1. 스택(Stack)의 기본 개념

 

2. 스택(Stack)의 구조

 

3. 스택구조 구현 해보기 - 재귀함수

 

 

1. 스택(Stack)의 기본 개념

 

 

오늘은 파이썬에서 가장 기본적인 데이터 구조 형태 중에 하나인 스택(Stack)에 대해서 알아보고자 합니다. 

 

Stack이라는 단어에서 유추해볼 수 있듯이 어떠한 데이터를 쌓고, 꺼내는 창고와 비슷한 구조라고 보시면 됩니다. 창고에서 물건을 꺼낼 때 맨 먼저 있는 것을 꺼낼 수도 있고, 반대로 맨 뒤에 있는 것부터 꺼낼 수도 있죠.

 

파이썬에서 스택도 마찬가지입니다. 아래의 그림을 보시면 더 이해가 빠르실 것 같습니다. 

 

스택의 구조

 

 

 

2. 스택(Stack)의 구조

 

(1) 스택의 기본 정책

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

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

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

 

(2) 스택의 주요 기능

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

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

 

 

(3) 스택의 장단점 

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.
• 단점 (일반적인 스택 구현시)
  • 데이터 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
  • 저장 공간의 낭비가 발생할 수 있음
    • 미리 최대 갯수만큼 저장 공간을 확보해야 함

참고: 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적임. 이 경우, 위에서 열거한 단점이 있을 수 있음

 

 

3. 스택 구조 재현하기 

 

(1) 재귀함수를 통한 스택 구조 구현

 

재귀함수로 스택 구조가 파이썬에서 어떻게 움직이는지 한 번 보도록 하겠습니다. 쉽게 말해서, "짐을 쌓고, 맨 나중에 저장된 짐부터 꺼내는 논리"의 코드를 구현해봄으로써 조금 더 직관적으로 이해해보도록 하겠습니다. 

 

# 재귀 함수
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)        

우선 재귀함수가 무엇인지는 알고리즘 목차에서 자세히 다루어보도록 하겠습니다. 

 

이런 함수를 짜고, data = 5 넣어보면 다음과 같은 일이 일어납니다. 1부터 5까지 우선 데이터를 저장하고, 5부터 데이터를 꺼내는 것을 볼 수 있습니다. 

print(data)는 데이터가 저장되는 것을 보여주고, print("returned", data)는 데이터까 꺼내지는 논리를 보여줄 것입니다. 아래의 사진을 보시면 이해가 빠를 것이라 생각합니다. 

 

재귀함수를 통한 Stack(스택) 원리의 이해

 

 

 

 

(2) 리스트/array를 통한 스택(stack) 구조 구현

 

재귀함수는 이해를 하기 위해서 구성해본 알고리즘이라면, 이제는 진짜 스택구조를 쓸 수 있도록 한 번 함수를 짜보도록 하겠습니다. 

 

여러 방법이 있겠습니다만, 우리가 이때까지 학습했던 리스트(List)를 복습 차원에서 활용해보도록 하겠습니다. 리스트에서는 append와 pop이란 메소드가 있습니다. 이것을 사용하게 아주 간단하게 스택(stack)을 구현해볼 수 있습니다. 아래의 코드를 한 번 보시죠. 

 

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