(4) Stack

■ Stack

1) 정의 :

First In Last Out - FIFO 구조

> 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조

> array로 이루어진 자료구조 사용

 

2) 대표 활용 :

> 컴퓨터 내부 프로세스 , 함수 콜 스택 등에 사용

> PS 중에 동적계획법에 사용되는 경우도 있음

 

3) 코드

> 재귀함수 stack

# 재귀 함수
# 재귀 깊이 설정
import sys
sys.setrecursionlimit(10000) # -> 공간 미리 확보해둔 것임!, in the system

# 재귀함수는 stack으로 process가 진행된다
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)     

>>> recursive(5)
5
4
3
2
1
0
ended
returned 0 // last in first out
returned 1
returned 2
returned 3
returned 4
returned 5

> list stack

data_stack = list()
data_stack.append(1)
data_stack.append(2)

data_stack
>>> [1, 2]

data_stack.pop()
>>> 2

4) 자료구조 스택 장단점

(1) 장점 :

   - 구조가 단순하여 구현이 쉬움

   - 저장 / 읽기 속도가 빠름( 이건 array 특징과 다름 → array end point에서 push pop을 하기 때문인 듯 )

(2) 단점 :

   - array와 마찬가지로 데이터 size의 최대 개수를 정해야 함

     ( python경우 재귀 깊이 설정 가능 )

   - 저장공간의 낭비가 발생할 수 있음( array의 특징 )

---

참조 :

gyoogle.dev/blog/computer-science/data-structure/Stack%20&%20Queue.html

스택 & 큐 | 👨🏻‍💻 Tech Interview