#3 스택, 큐, 재귀함수

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미
  대표적인 탐색 알고리즘 : DFS, BFS

• 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조
  -> 스택과 큐는 자료구조의 기초 개념
  삽입(push) : 데이터를 삽입한다.
  삭제(pop) : 데이터를 삭제한다.

• 스택
  : 선입후출(First In Last Out) 구조 또는 후입선출(Last In Fist Out)

@ 예제

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) #최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

append()로 삽입, pop()으로 삭제
삭제할 때 가장 나중에 들어온 수가 먼저 삭제된다.

• 큐
  : 선입선출(First In First Out) 구조

@ 예제

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()


print(list(queue))

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용
list(queue)로 리스트화 시킬 수 있다.

• 재귀 함수
  : 자기 자신을 다시 호출하는 함수

@ 예제

def recursive_function() :
	print("재귀함수를 호출합니다.")
    recursive_function()
recursive_function()    

def fac(n) :
    if n<=1 :
        return 1
    return n*fac(n-1)
    
print(fac(5))

재귀함수로 팩토리얼 구현
return nfac(n-1) 는 n! = n(n-1)