[알고리즘] STACK & QUEUE

강의 출처 : 나동빈님 유튜브 강의

1. STACK

1-1. STACK 자료구조

• 먼저 들어온 데이터가 나중에 나가는 자료구조
• 입구와 출구가 동일한 형태로 스택을 시각화
• 박스 쌓기를 예로 들 수 있음
  • 박스를 쌓을 때 밑부터 쌓음
  • 박스를 뺄 때 위부터 뺌
    

1-2. STACK 동작 예시

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
  

1-3. STACK 구현 예제

stack =[]
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

2. QUEUE (큐)

2-1. QUEUE 자료구조

• 먼저 들어 온 데이터가 먼저 나가는 형식, 선입선출의 자료구조
• 큐는 입구와 출구가 모두 뚫려있는 터널과 같은 형태로 시각화
• 터널, 은행창구에서 번호표를 뽑을 때 은행원이 일처리하는 것을 생각해보자.
  

2-2. QUEUE 동작 예시

• 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
• 먼저 들어온 것이 삭제되는 모습
  

2-3. QUEUE 구현 예제

• 큐를 사용할 때, 시간복잡도 때문에 일반적으로 deque를 사용하는 것이 좋음

frome collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
>>> deque([3, 7, 1, 4])

queue.reverse() # 역순으로 바꾸기
print(deque) # 나중에 들어온 원소부터 출력
>>> deque([4, 1, 7, 3])