[자료구조] 재귀/스택/큐

재귀 (Recursion)

• 자기 자기를 다시 호출하는 것을 의미
• 종료 조건이 없을 경우 무한적으로 작동함
• 무한 작동을 막기 위해서는 Base Case (탈출조건) 이 필요함
  • Base case에서는 재귀가 멈춤
  • General case에서는 재귀가 계속 작동됨
  • 대표적인 예시로 팩토리얼

• 재귀 함수는 Tail Recursion, Head Recursion 두 가지 존재
  • Tail Recursion은 재귀함수가 맨 마지막에 존재
  • Head Recursion은 재귀함수가 맨 앞에 존재

스택

• LIFO (Last in First Out) 특성을 가지는 자료구조
• 특징 그대로 가장 마지막에 들어온 요소가 가장 먼저 나감
• 스택의 변화는 Top 위치에서 실행됨
  • 스택 안 요소 넣는 작업 Push
  • 스택 안 요소를 빼는 작업 Pop
  • 두 작업 모두 시간복잡도 O(1) 이 걸림
• 주로 실행 취소(Ctrl+Z), 재귀함수에서도 사용됨
• 스택은 기본적으로 크기가 정해져있음

큐

• FIFO (First In First Out) 특성을 가지는 자료구조
• 특징 그대로 처음 들어온 요소가 가장 먼저 나가게 됨
• 큐의 변화는 양쪽에서 발생
  • 큐 안에 요소를 넣는 작업 Enqueue
  • 큐 안에 요소를 빼는 작업 Dequeue
  • 두 작업 모두 시간 복잡도 O(1)이 걸림
• 주로 매표소 구현에서 사용
• 큐는 기본적으로 크기가 정해져있음
  • 원형 Queue를 사용 시 데이터 최대 사이즈를 유지한 채로 Queue를 사용할 수 있음
  • 꽉 찬 상태에서 추가하면 맨 앞으로 되돌아감