자료 구조 - 스택,큐,재귀함수

자료 구조 기초

탐색

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

자료구조

• 데이터를 표현하고 관리하고 처리하기 위한 구조

스택 Stack

선입후출 or 후입선출 구조

• 아래에서부터 위로 차곡차곡 쌓기
• 아래 박스 치우기위해서는 위의 박스 먼저 치워야함

파이썬

• append()
  • 리스트의 가장 뒤쪽에 데이터 삽입
• pop()
  • 리스트의 가장 뒤쪽에서 데이터를 꺼내기

    예제

    #스택 선언
    stack = []
    #스택에 5 추가
    stack.append(5)
    #스택에 가장 최근에 추가된 항목 삭제
    stack.pop()

    
    
    

    큐 Queue

선입선출 구조

• 대기 줄에 비유
  • 먼저 온 사람이 먼저 들어가고 나중에 온 사람이 나중에 들어감

    라이브러리 사용하기

• collections 의 deque
  

  from collections import deque

  예제

  from collections import deque
  

#Queue 구현을 위해 deque 라이브러리 사용
queue = deque()
#삽입
queue.append(5)
#삭제 (먼저 삽입된 자료부터 삭제)
queue.popleft()

#먼저 삽입된 순서대로 출력
print(queue)
#다음 출력을 위해 역순으로 바꾸기
queue.reverse()
#나중에 들어온 원소부터 출력
print(queue)
#리스트 자료형으로 변환
list(queue)

<br/><br/>
# 재귀함수
> 자기자신을 다시 호출하는 함수
### 예시
```Python
def recursive_function():
    print('재귀함수를 호출합니다.')
    recursive_function()

recursive_function()

주의사항

• 재귀 함수가 언제 끝날지 종료 조건을 꼭 명시

참고

• 재귀 함수는 내부적으로 스택 자료 구조와 동일

팩토리얼을 통한 반복문과 재귀함수 비교

# 반복문
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
        result *= i
    return result

# 재귀적으로 구현
def factorial_recursive(n):
    # n이 1 이하인 경우 1을 반환
    if n <= 1:
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성
    return n * factorial_recursive(n-1)

참고

이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 : 나동빈