큐

한 쪽에서는 삽입만, 다른 한 쪽에서는 삭제만 가능한 자료구조

큐(queue)란 FIFO(First In First Out, 선입선출)의 특징을 가지는 자료구조입니다. 선입선출 즉, 먼저 들어온게 먼저 나갑니다. 터널을 연상합시다.

스택과는 다르게 양 쪽이 모두 열려 있습니다. 한 쪽에서만 삽입/삭제가 이루어졌던 스택과는 달리, 큐는 삽입과 삭제가 다른 쪽에서 일어납니다. 한 쪽으로만 들어올 수 있다는 것은 스택과 동일하지만, 다른 쪽으로 나가야 한다는 것이 스택과 차별화된 큐만의 특징입니다. 그렇기 때문에 선입선출이 가능한 것이죠.

스택과 마찬가지로 리스트와 덱(deque)으로 구현이 가능합니다.

큐의 삽입, 삭제

li = []        
li.append(1)    # li == [1]
li.append(2)    # li == [1, 2]
li.pop(0)       # li == [2]
li.pop(0)       # li == []

스택처럼 append(값)과 pop() 함수를 모두 사용할 수 있습니다. 또한 스택과 다르게 전단(front) 삭제도 가능합니다. 이는 pop(0)를 사용하여 실행할 수 있습니다.

하지만 pop()과 달리 pop(0)은 '0'이라는 index를 지정해주는 과정이 있기에, 0번째 원소를 꺼낸 후 다시 List를 재정비해주는 과정이 필요하므로 O(N)의 시간 복잡도를 가집니다.

이 때 deque의 popleft()를 사용하면 O(1)의 시간복잡도로 이를 해결할 수 있습니다. 그래서 queue를 구현할 때 List보다는 deque를 쓰는 것이 권장됩니다. 해당 개념은 다음 차시 덱에서 더 알아보기로 합시다.

연습문제

BOJ 1966

1966번: 프린터 큐Baekjoon Online Judge

문제를 읽어보면, 전단(front)에서 원소를 삭제해야 하기 때문에, 큐를 사용해야 합니다. 하지만 삽입/삭제를 거치면서 원래 지정한 문서의 인덱스마저 바뀌게 됩니다. 때문에, 중요도를 담은 배열 이외에 다른 배열을 하나 더 만들어서, 지정한 문서의 위치를 동시에 저장하는 방식으로 하시면 됩니다.

li = list(map(int, input().split()))
check = [False for _ in range(n)]
check[m] = True

위와 같이 중요도를 담은 배열 li와, 궁금한 문서의 위치를 저장해줄 배열 check를 만들도록 합시다. check 배열의 원소를 모두 False로 만들되, 궁금한 문서는 True로 지정해줘야겠죠? while문을 돌다가, 리스트의 0번 인덱스의 값이 최댓값이면서 처음 지정한 문서일 때 반복문을 종료해주시면 됩니다.

t = int(input())
for i in range(t):
    n, m = map(int, input().split())
    li = list(map(int, input().split()))
    check = [False for _ in range(n)]
    check[m] = True
    cnt = 0
    while True:
        if li[0] == max(li):
            cnt += 1
            if check[0] == True:
                print(cnt)
                break
            else:
                li.pop(0)
                check.pop(0)
        else:
            li.append(li.pop(0))
            check.append(chk.pop(0))

위에서 말했듯이, 큐는 주로 덱으로 구현하기 때문에 개념적인 것을 이해한 후, 덱에 대해 더 자세히 학습하러 가봅시다 !