Data Structures 03. 스택 (Stack)

스택 (Stack)

: 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
➔ LIFO (Last In First Out)

• 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름
  - LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책

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

• 대표적인 스택의 활용
  - 컴퓨터 내부의 프로세스 구조의 함수 동작 방식

• 주요 기능
  - push(): 데이터를 스택에 넣기
  - pop(): 데이터를 스택에서 꺼내기
  
  

Stack의 구조와 Process Stack

: 스택의 구조는 프로세스 실행 구조의 가장 기본

# 재귀 함수 => 스택
def recursive(data):
    if data < 0:
        print ("ended")
    else:
        print(data)
        recursive(data - 1)
        print("returned", data)   
        
recursive(3)
        
# 함수 위에 함수가 호출되면, 스택과 같은 구조로 상단에 쌓음
# 맨 위에 있는 함수가 끝나면 그 함수를 호출한 그 다음 함수가 불려지는 형태로 프로세스가 동작
# 이 형태를 구현하는데 가장 유용한 자료구조가 스택 -> 따라서 이런 프로세스동작방식에 스택을 사용

--- 출력 결과 ---
3
2
1
0
ended
returned 0
returned 1
returned 2
returned 3
None

Stack 구조의 장단점

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

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

리스트로 스택 구현

stack_list = []

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

def pop():
    data = stack_list[-1]
    del stack_list[-1]
    return data

for a in range (10):
    push(a)

print(stack_list)
print(pop())
print(stack_list)
print(pop())
print(stack_list)

--- 출력 결과 ---
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9
[0, 1, 2, 3, 4, 5, 6, 7, 8]
8
[0, 1, 2, 3, 4, 5, 6, 7]