스택

 

스택(Stack)

• 한 쪽 끝(Top)에서만 새로운 항목을 삽입(Push)하거나 기존 항목을 삭제 및 반환(Pop)하는 논리적 선형 구조.
  • 시간 순으로 먼저 삽입된 항목이 나중에 삭제되는 후입선출(LIFO : Last-In, First-Out) 구조.
  • Top에서만 삽입, 삭제가 이루어지는 특수한 리스트.(List)
• python에서의 스택
  • python 리스트(동적 배열)에 의한 구현 -> push pop 연산 모두 O(1)
  • 단순 연결 리스트에 의한 구현 -> push pop 연산 모두 O(1)

 

스택에 적용 가능한 주요 연산

• Stack() : 빈 스택 생성
• push(item) : 기존 Top 다음 위치에 item 삽입
• pop() : Top 위치에 존재하는 item  삭제 및 반환
• peek() : Top 위치에 존재하는 item 반환
• is_empty() : 스택이 empty면 True 반환
• size() : 스택의 사이즈 반환 

 

스택 활용 예시