[자료구조] Stack

안녕하세요 개발콩입니다 !! 😆

오늘은 자료구조 Stack에 대해 정리하도록 하겠습니다.

 

 

Stack

한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO, FILO 형식의 자료구조입니다.

 

 

우리가 주로 먹는 프링글스 과자를 생각하면 이해하기 쉬울 것 같아요.

 

우리는 과자를 먹을 때 가장 위에 있는 과자를 먹게되고, 과자를 다시 넣게 된다면 제일 위에 넣게 되죠.

즉, 우리는 과자를 꺼낼 때 가장 마지막에 넣었던 과자를 먹게됩니다!

 

 

 

Stack의 메서드

• push
  • 스택에 데이터를 추가합니다.
• pop
  • 가장 마지막에 들어온 데이터를 제거합니다.
• top
  • 가장 마지막에 들어온 데이터를 확인합니다.

 

 

 

 

Stack의 시간복잡도

push	O(1)
pop	O(1)
top	O(1)

 

 

 

 

스택 오버플로우

스택에서 사용 가능한 것보다 더 많은 공간을 사용하는 경우

 

 

스택 언더플로우

스택에서 데이터가 없는 상태에서 삭제를 시도하는 경우

 

 

 

사용방법

우리는 Swift언어에서 기본 제공하는 ArrayList를 활용해 Stack을 구현하지 않고 쉽게 사용할 수 있습니다!

push	append
pop	popList() -> Self.Element? / removeList() -> Self.Element
top	last