CS with Python - Stack

스택 (Stack)
--> 스택은 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조

[스택의 특징]

1. 스택에 저장된 자료는 선형 구조를 갖는다.

   선형구조/비선형구조란?
   선형구조: 자료 간의 관계가 1대1의 관계를 갖는 구조
   비선형구조: 자료 간의 관계가 1대 N의 관계를 갖는 구조 (ex. 트리)

2. 스택은 자료를 삽입(push) 및 자료를 추출(pop)할 수 있다.

3. 스택은 후입선출(LIFO, Last-In-First-Out)의 구조를 가진다.

[스택의 중요성]

1. 스택을 통해 Function call에 대해 이해할 수 있다

   Function call이란?
   프로그램에서 함수호출과 복귀에 따른 수행 순서를 관리

2. 앞에서 이해한 Function call로부터 시작하면
   스택 - 재귀호출 - DFS (백트래킹, 분할정복) - Memoization - DP로 연결되는 크나큰 흐름을 이해하는 데 도움이 된다.

[스택의 구현]

1. 스택을 append, pop 기능을 활용해 구현해보자

# 스택으로 활용할 리스트 생성
S = []

# push(5)
S.append(5)

# pop(5)
S.pop(5)

2. 스택을 인덱스를 활용해 구현해보자
   (함수로 만들어서 사용해도 좋다!)

# 스택으로 활용할 리스트 생성
S = [0] * 10  # 자료의 저장공간에 제한 필요
top = -1  # 마지막에 저장된 자료의 인덱스

# push(5)
top += 1
S[top] = 5

# pop(5) (result에 pop 저장)
if S:  # 스택에 pop할 원소가 있다면
    result = S[top]
    top -= 1

ver 230415 - 기초 작성