Published: Jan 20, 2020 by Dev-hwon

Stack (스택)

• 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조
• 배열 인덱스 접근이 제한
• 후입선출(LIFO) 구조
• 시간복잡도 O(1)

1. 스택 구조

• 스택은 LIFO(Last In, Fisrt Out) 또는 FILO(First In, Last Out) 데이터 관리 방식을 따름

• 대표적인 스택의 활용
  • 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
  • 깊이 우선 탐색(DFS)에 유용하게 사용
• 주요 기능
  • push: 스택 맨 끝에 항목을 삽입
  • pop: 스택 맨 끝 항목을 반환하는 동시에 제거
  • top/peek: 스택 맨 끝 항목을 조회
  • empty: 스택이 비어 있는지 확인
  • size: 스택 크기를 확인

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

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

3. 장단점

Code

class Stack(object):
  def __init__(self):
    self.items = []

  def isEmpty(self):
    return not bool(self.items)

  def push(self, value):
    self.items.append(value)

  def pop(self):
    value = self.items.pop()
    if value is not None:
      return value
    else:
      print('Stack is empty.')

  def size(self):
    if self.items:
      return self.items[-1]
    else:
      print('Stack is empty.')

  def __repr__(self):
    return repr(self.items)