[자료구조] 스택(Stack) -Data Structure with 파이썬

스택(Stack)

제한적으로 접근할 수 있는 나열 구조 (데이터를 제한적으로 접근할 수 있는 구조)

 

접근 방법은 언제나 목록의 끝에서만 일어난다 (한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조)

 

가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

 

LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식

• LIFO: 마지막에 넣은 데이터를 가장 먼저 추출하는 방식
• FILO: 처음에 넣은 데이터를 가장 마지막에 추출하는 방식

 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

 

활용

• 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 프로세스 메모리 구조 - stack 영역
• 컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용

 

장단점

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

 

 

스택(Stack)의 핵심 연산

• push()
  • 데이터를 넣는 기능
  • 반환 X
• pop()
  • 데이터를 꺼내는 기능
  • 데이터 반환

 

파이썬 리스트로 스택 사용

data_stack = list()

data_stack.append(1)
data_stack.append(2)
print(data_stack)
# [1, 2]

data_stack.pop()
print(data_stack)
# [1]

 

---

스택의 배열 기반 구현

파이썬에서는 배열을 리스트로 제공 함.

 

스택의 연결리스트 기반 구현