[자료구조와 알고리즘] 자료구조(3) - 스택

1. 스택(Stack)이란?

Key Ponint 💡 스택이란?

• 데이터를 제한적으로 접근할 수 있는 구조
  • 한 쪽 끝에서만 자료를 넣거나 뺼 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
  • 큐 : FIFO 정책 : 첫 번째 넣은 것이 첫 번째로 나옴
  • 스택 : LIFO 정책 : 마지막에 넣은 것이 첫 번째로

2. 스택의 구조

Key Ponint 💡 스택의 구조

• 스택은 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따른다.
  • LIFO : 마지막에 넣은 데이터를 가장 먼저 추출하는 데이터 관리 정책
  • FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책
• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• 주요기능
  • push() : 데이터를 스택에 넣기
  • pop() : 데이터를 스택에서 꺼내기

3. 스택 구조와 프로세스 스택

Key Ponint 💡

• 스택 구조는 프로세스 실행 구조의 가장 기본
  • 함수 호출시 프로세스 실행 구조를 스택과 비교해서 이해가 필요하다.

# 재귀함수
def recursive(data):
    if data<0:
        print("ended")
    else:
        print(data)
        recursive(data-1)
        print("returned", data)
        
       
       
recursive(4)

# 4
# 3
# 2
# 1
# 0
# ended
# returned 0
# returned 1
# returned 2
# returned 3
# returned 4

4. 자료 구조 스택의 장단점

• 장점
  • 구조가 단순해서, 구현이 쉽다.
  • 데이터 저장/읽기 속도가 빠르다.

• 단점(일반적인 스택 구현시)
  • 데이터 최대 갯수를 미리 정해야 한다.
    • 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능하다.
  • 저장 공간의 낭비가 발생할 수 있다.
    • 미리 최대 갯수만큼 저장 공간을 확보해야 한다.

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

5. 파이썬 리스트 기능에서 제공하는 메서드로 스택 사용해보기

Key Ponint 💡 append(push), pop 메서드 제공

# apppend 와 pop 메서드 사용

data_stack = list()

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


# 나중에 입력된 값이 먼저 제거 된다.
data_stack.pop() # 2

# 남아있는 값은 가장 먼저 입력된 값 : 1
data_stack # 1