[4일차] 03 자료구조 : 03-5 스택과 큐

함께 푼 문제

[백준 / 큐] 10828 : 스택 (python)

[백준 / 큐] 1966 : 프린터 큐 (python)

 

스택

• 후입선출(LIFO)
• 깊이 우선 탐색에 효과적
• 후입선출 개념은 재귀 함수 알고리즘 원리와 일맥상통함

satck = []
#삽입
stack.append(1)
stack.append(2)
stack.append(3)
#제거
stack.pop() #3 #후입선출

 

큐

• 선입선출(FIFO)
• 넓이 우선 탐색에서 자주 사용

from collections import deque

queue = deque()
#삽입
queue.append(1)
queue.append(2)
queue.append(3)
#제거
queue.popleft() #1 선입선출

• popleft는 제일 왼쪽에 있는걸 삭제한 뒤 빈공간을 채우기 위해 뒤쪽에 있는 요소들을 한칸씩 왼쪽으로 땡겨야한다. 따라서 list로 구현하면 시간복잡도가 크기 때문에 deque를 사용하여 큐를 구현한다.

 

파이썬 우선순위 큐 사용법

선언

from queue import PriorityQueue

Q = PriorityQueue()

삽입

Q.put(5)
Q.put(2)
Q.put(3)

• 숫자가 작은 것이 앞에 저장된다.

제거

Q.get() #2
Q.get() #3
Q.get() #5

 

• 우선순위큐는 일반 큐와 다르게 append, pop을 사용하지 않고 put, get을 사용한다.

정렬 기준 적용

삽입

Q.put((1, -6)) # (우선순위, 값)
Q.put((3, 3))
Q.put((2, 2))
Q.put((1, 1))

• (우선순위, 값) 형태로 삽입할 수 있다.
• 우선순위를 나타내는 수가 작을수록 앞에 저장된다. (숫자가 작을수록 우선순위가 크다.)
• 우선순위가 같은 경우 값이 작을수록 앞에 저장된다.

제거

while not Q.empty():
    print(Q.get()[1])

#-6
#1
#2
#3

• Q.get()을 할 경우 (1, -6) 형태로 출력된다. 값만 출력하고 싶은 경우 Q.get()[1]을 하면 값만 출력된다.