[자료구조] 스택 (Stack)

스택이란?

나중에 들어간 데이터를 가장 먼저 출력하는 구조이다. 쉽게 설명하자면, 뷔페에서 쌓아둔 접시들을 예시로 들 수 있다. 층층이 쌓인 접시들 중에서 가장 마지막으로 쌓은 접시를 손님들은 가장 먼저 가져간다. 스택에 무언가를 삽입하고자 했는데 이 스택이 이미 꽉 찬 상태여서 나타나는 에러를 Stack Buffer Overflow 스택 버퍼 오버플로우라고 한다. 개발자들의 빛과 희망과 같은 스택 오버플로우 웹사이트 이름도 여기에서 유래했다! 깔깔깔.

• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 파이썬에서는 스택 자료형을 따로 지원하지는 않지만, 리스트로 만들 수 있다. 
• 스택 : LIFO , FILO
  • LIFO (Last-In-First-Out) : 나중에 들어간 것이 먼저 나온다.
  • FIFO (First-In-First-Out) : 처음 들어간 것이 처음 나온다. 
• 큐 : FIFO
• push() : 데이터 입력, pop() : 데이터 출력
• 장점 : 구조가 단순해서 구현이 쉽다. 데이터 저장/읽기 속도가 빠르다.
• 단점 : 데이터 최대 갯수를 미리 정해야 한다 (파이썬 재귀 함수는 최대 1000번까지 호출 가능). 저장 공간의 낭비가 발생 가능해서 비효율적일 수 있다. 

Resource: https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

 

직접 시연해보며 확인하기 

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

 

리스트로 스택 사용하기

주의할 점은 push() 대신 append()를 사용한다는 점! list는 push라는 attribute를 갖고 있지 않는다.

data_stack = list()

data_stack.append(1)
data_stack.append(2)

data_stack

output : [1, 2]

 

data_stack.pop()

output: 2

 

위의 내용을 함수로 표현하자. (pop을 사용하지 않고 구현하자)

stack_list = list()

def push(data):
    stack_list.append(data)

#stack_list.pop() 대신 사용할 수 있는 방법
def pop():
    data = stack_list[-1] 
    del stack_list[-1]
    return data

# 0부터 9까지의 수를 넣는다. 
for index in range(10):
    push(index)

pop()

결과는 맨 마지막에 넣은 숫자 9. 

 

스택으로 재귀함수 구현

def recursive(data):
    if data < 0:
        print("End")
    else:
        print(data)
        recursive(data-1)
        print("Returned", data)

recursive(4)

실행 결과

 

GitHub - DAWUNHAN/algorithms-and-dataStructure: Algorithms and DataStructure with Python

본 내용은 패스트캠퍼스 올인원 알고리즘 강좌 내용을 요약/정리한 노트입니다.