파이썬과 자료구조(스택)

이승혜·2021년 3월 11일

파이썬과 자료구조

목록 보기

3/5

📒 스택(Stack)

데이터를 제한적으로 접근할 수 있는 구조
- 한쪽 끝에서만 자료를 넣거나 뺄 수 있음
가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
- 큐 : FIFO
- 스택 : LIFO
스택은 LIFO 또는 FILO 데이터 관리 방식을 따른다
- LIFO : 마지막에 넣은 데이터를 가장 먼저 추출
- FILO : 처음에 넣은 데이터를 가장 마지막에 추출
대표적으로 컴퓨터 내부의 프로세스 구조의 함수 동작 방식으로 활용
주요 기능
- push() : 데이터를 스택에 쌓기
- pop(): 데이터를 스택에서 꺼내기

✅ 재귀함수로 스택 이해하기

def recursive(data):
    if data < 0:
        print("끝!")
    else:
        print(data) 
        recursive(data - 1)
        print("returned", data)


recursive(4)

# 4
# 3
# 2
# 1
# 0
# 끝!
# returned 0 가장 나중에 쌓은 함수를 먼저 빼냄
# returned 1
# returned 2
# returned 3
# returned 4

디버깅을 해보면 Call Stack에 recursive 함수가 차곡차곡 쌓이는 것을 볼 수 있음 => 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

✅ 스택의 장단점

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

✅ 스택의 시간 복잡도

insert : O(1)
delete : O(1)
search : O(n)

삭제나 삽입 시 맨 위에 데이터를 삽입하거나 삭제하기 때문에 시간 복잡도는 늘 O(1)이다. 하지만 특정 데이터를 찾을 때는 특정 데이터를 찾을 때 까지 수행을 해야하므로 O(n)의 시간 복잡도를 가짐

✅ 구현 연습

리스트 변수로 stack 구현하기

data_stack = list()

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

print(data_stack) # [1, 2, 3, 4]

# 가장 마지막에 넣은 원소가 가장 먼저 반환
print(data_stack.pop()) # 4
print(data_stack.pop()) # 3
print(data_stack.pop()) # 2
print(data_stack.pop()) # 1

push, pop 함수 사용하지 않고 구현하기

data_stack = list()

def append(data):
    # 리스트 가장 마지막에 data 삽입
    data_stack.append(data)

def pop():
    # data는 가장 뒤에 있는 원소
    data = data_stack[-1]
    # 가장 뒤에 있는 원소를 삭제
    del data_stack[-1]
    # 반환
    return data

append(1)
append(2)
append(3)
append(4)

print(data_stack) # [1, 2, 3, 4]

pop() # 4
pop() # 3
pop() # 2 
pop() # 1

class로 구현하기

class Stack(list):
    push = list.append
    pop = list.pop

    def is_empty(self):
        if not self:
            print(True)
            return True
        else:
            print(False)
            return False

stack = Stack()

stack.push(1)
print(stack) # [1]
stack.push(2)
print(stack) # [1, 2]
stack.push(3)
print(stack) # [1, 2, 3]
stack.push(4)
print(stack) # [1, 2, 3, 4]

stack.is_empty() # False

stack.pop()
print(stack) # [1, 2, 3]
stack.pop()
print(stack) # [1, 2]
stack.pop()
print(stack) # [1]
stack.pop()
print(stack) # []

stack.is_empty() # True

스택으로 재귀 구현하기(팩토리얼)

def factorial(n):
    stack = []
    while n > 0:
        # stack에 n을 하나씩 줄여가며 삽입
        stack.append(n)
        n -= 1
    print(stack) # [5, 4, 3, 2, 1]
    result = 1

    while stack:
        # stack에서 하나씩 꺼내서 곱함
        result *= stack.pop()

    print(stack) # []
    return result

print(factorial(5)) # 120

참고 : for문으로 팩토리얼 구현

def factorial(n):
    result = 1
    # n이 5일 경우, 1에서 5까지 반복하며 곱함
    for i in range (1, n+1):
        result *= i
    return result

print(factorial(5))