파이썬 - 알고리즘(큐, 스택)

• 스택
  • 데이터를 처리하는 기본 자료 구조
  • 데이터의 삽입과 삭제가 상단(top)에서만 발생
  • 후입선출(Last In, First Out, LIFO) 형태로 데이터 처리
    • 가장 마지막에 입력된 데이터가 가장 먼저 제거되는 구조
    • 먼저 넣은 데이터보다 나중에 넣은 데이터를 우선 처리하는 방법
  • 스택 활용 사례
    • 함수 호출 스택
    • 웹 브라우저 방문 기록( 뒤로 가기)
    • 괄호 검사와 같은 문자열 처리
  • 스택 연산(데이터 처리) 방식
    • push: 스택에 데이터를 삽입하는 동작
    • pop: 스택에서 데이터를 제거하는 동작

스택 구현

• 큐 
  • 데이터를 처리하는 기본 자료 구조
  • 선입선출(First In, First Out, FIFO) 형태로 데이터 처리
    • 마지막에 데이터를 입력하고 가장 먼저 입력된 데이터가 먼저 제거되는 구조
  • 큐의 활용 사례
    • 프로세스 관리 ex) 작업 대기열
    • BFS( 너비 우선 탐색) 구현
  • 큐 연산(데이터 처리) 방식
    • Enqueue : 큐에 데이터를 삽입하는 동작
    • Dequeue : 큐에서 데이터를 제거하는 동작

큐 구현

 

• 덱(Deque) 개요
  • 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
  • 스택과 큐를 병합한 형태의 자료구조
  • 파이썬 내장 모듈 collections 활용
  • 덱(Deque)은 Double Ended QUEue의 약자
  • 덱의 활용 사례
    • 회전 큐 ex) 슬라이딩 윈도우
    • 문자열 회문 검사
  • 덱 연산(데이터 처리) 방식
    • append : 덱의 마지막에 데이터를 삽입하는 동작
    • appendleft : 덱의 처음에 데이터를 삽입하는 동작
    • pop : 덱의 마지막 데이터를 제거하는 동작
    • popleft: 덱의 처음 데이터를 제거하는 동작

덱 구현