[자료 구조] 파이썬으로 선형 자료 구조 구현

스택 (Stack)

• 스택 이란 무엇인가?

  • 후입선출 LIFO (Last In First Out)의 성질을 가진 자료 구조
  • 창고에 박스를 하나씩 쌓고 하나씩 빼내는 느낌

• 스택은 어디에 쓰이는가?

  • 데이터가 스트리밍 되고 있는 상황에서 최신의 데이터를 다뤄야하는 경우
  • 윈도우의 ctrl + z, 웹 브라우저의 뒤로가기
  • 문자열이나 리스트의 reverse

• 파이썬에서 스택을 쓰려면?

# 리스트만으로도 구현 가능
# 스택 정의
stack = []

# 스택 원소 삽입
stack.append(data)

# 스택 원소 추출
stack.pop()

큐 (Queue)

• 큐 이란 무엇인가?

  • 선입선출 FIFO (first In First Out) 의 자료 구조

• 큐은 어디에 쓰이는가?

  • 순서 보장이 필요한 데이터 처리
  • CPU의 프로세스 스케줄링, 네트워크, 버퍼 처리

• 파이썬에서 큐를 쓰려면?

< 방법1 >

# 큐 정의
queue = []

# 큐 원소 삽입
queue.insert(0,data)

# 큐 원소 추출
queue.pop()

< 방법2 >

# 큐 정의
queue = []

# 큐 원소 삽입
queue.append(0,data)

# 큐 원소 추출
queue.pop(0)

## pop(0)은 사용하지 않는 편이 좋음
## 남은 요소를 하나씩 땡겨야 해서 시간 복잡도가 올라감

< 방법3 >

## 추천 방법 ##
# 방법1과 로직은 같음
# 덱 모듈 import
from collections import deque

# 큐 정의
queue = deque()

# 큐 원소 삽입
queue.appendleft(data)

# 큐 원소 추출
queue.pop()

< 방법4 >

## 추천 방법 ##
# 방법2와 로직은 같음
# 덱 모듈 import
from collections import deque

# 큐 정의
queue = deque()

# 큐 원소 삽입
queue.append(data)

# 큐 원소 추출
queue.popleft()

덱 (Deque)

• 덱이란 무엇인가?
  • stack과 queue를 합친 구조

• 덱은 어디에 쓰이는가?
  • 스택과 큐를 사용할 수 있는 곳

• 파이썬에서 덱을 쓰려면?
  • 보통 시간 초과가 나오기 쉬운 문제가 많기 때문에 모듈 사용 권장

# 덱 모듈 import
from collections import deque

# 큐 정의
queue = deque()

# 큐 원소 삽입
# 오른쪽 삽입
queue.append(data)
# 왼쪽 삽입
queue.appendleft(data)

# 큐 원소 제거
# 왼쪽 제거
queue.popleft()
# 오른쪽 제거
queue.pop()