알고리즘 -Queue

woohobi·2021년 10월 12일
0

알고리즘

목록 보기
5/5

Queue

Queue는 stack 과 다르게 FIFO 방식으로 동작합니다. 아래 그림에서 볼 수 있듯이 가장 처음에 들어간 요소가 가장 처음으로 나오게 됩니다.

단독으로 Queue 문제가 나오는 경우는 stack 보다 적지만 대표적으로 bfs에서 자주 활용되니 원리를 잘 알아놓는 것이 중요합니다.
스택은 출입구가 top 쪽 한 곳이였던 것에 비해, 큐는 top으로 원소가 들어오고, bottom 으로 요소가 나가게 됩니다. 즉, pop()을 하게 되면 front요소가 return 되고, append 연산을 하면 top으로 요소가 add 됩니다.

python에서의 queue

from collections import deque

#queue 모듈에 정의되어있는 Queue 를 사용할 수도 있지만,
# multi thread 에 대한 동기화 처리 때문에(알고리즘 문제풀이에서는 필요하지 않음) deque 보다 처리시간이 느려
# deque를 사용하면 됩니다.
# deque는 양쪽에서 삽입 삭제가 모두 가능한 자료구조인데 queue연산을 할때 append를 시켜주면 back쪽에, popleft를 시켜주면 front의 요소를 pop 시킵니다

queue = deque()

# add연산
queue.append((1,2))

result = queue.popleft()
#result = a,b

2164 카드
문제 풀이

from collections import deque


n= int(input())

queue = deque()

#1부터 n까지 queue에 넣어 초기화해줍니다
for i in range(1,n+1):
    queue.append(i)

# queue 가 있는 동안에는 while문을 계속 돌게 되는데, 마지막 카드가 한장 남았을 경우 반복문을 break 시켜준뒤 답을 출력하면 됩니다.
while queue:
    # 1,2,3,4,5,6 이 카드가 있을때, 1을 제거, 2를 카드 아래로 옮김
    queue.popleft()
    if len(queue)==1:
        break
    queue.append(queue.popleft())

print(queue.popleft())
profile
CDD - Coffee Driven Development

0개의 댓글