CS 공부일지 [자료구조]-(3)스택과 큐

📝 자료구조 - (3) 스택과 큐

스택

• 선형 자료 구조
• 후입선출(Last-In-First-Out)

• 장점
  • 데이터 삽입/삭제가 빠름 [ O(1) ]
  • 데이터를 역순으로 처리할 때 유용

• 단점
  • 크기 제한 있음
  • 메모리 사용량 증가
  • 스택의 크기가 고정되어 있어 스택이 가득 차면 새로운 데이터 삽입 불가
    --> 스택 오버플로우(Overflow)

⌗ 스택의 단점을 보완하기 위해

• 스택의 크기 동적 조절 : 동적 스택(Dynamic Stack)
• 스택에서 데이터 삭제시 메모리 공간 재활용 : 스택의 재활용(Recycling)

큐

• 선형 자료 구조
• 선입선출(First-In-First-Out)

• 장점
  • 삽입/삭제시 빠른 시간복잡도 [ O(1) ]
  • 데이터를 선입선출로 처리
  • 데이터 처리시 순서 보장

• 단점
  • 큐의 크기가 한정
  • 메모리를 낭비할 수 있음
  • 임의 위치에 있는 데이터에 접근하기 어려움 [ 탐색 - O(n) ]

⌗ 큐의 단점을 보완하기 위해

• 크기 동적 조절 : 동적 큐(Dynamic Queue) (연결 리스트를 사용)
• 원형 큐 사용으로 메모리를 효율적으로 사용

• 스택 vs 큐(Python)

# 스택 구현 예시
stack = []

# 데이터 삽입
stack.append(1)
stack.append(2)
stack.append(3)

# 데이터 삭제
stack.pop() # 3이 삭제됨
stack.pop() # 2가 삭제됨
stack.pop() # 1이 삭제됨

# 큐 구현 예시
from collections import deque

queue = deque()

# 데이터 삽입
queue.append(1)
queue.append(2)
queue.append(3)

# 데이터 삭제
queue.popleft() # 1이 삭제됨
queue.popleft() # 2가 삭제됨
queue.popleft() # 3이 삭제됨

• 스택(stack)은 list로 구현
• 큐(queue)는 collections 모듈에서 제공하는 deque 클래스로 구현
• 스택 vs 큐의 가장 큰 차이인 후입선출(Last-In-First-Out)과 선입선출(First-In-Firts-Out)