[자료구조 및 알고리즘] 큐 (Queue)

큐

 

Queue가 어떻게 쿠웨웨가 아니라 큐인지 모르겠지만... 큐는 스택의 특징과 다르게 선입선출(FIFO)의 성격을 가지고 있다. 따라서 큐는 순서대로 대기하고 실행시키고 싶을 때 사용하는 자료구조이다. 급식실에서 밥 먹으려고 줄 서있는 학생들을 생각하면 이해하기 쉬울 것 같다.

 

큐의 구조

코드

 

큐 또한 파이썬에서는 리스트로 구현가능한데, pop을 해줄 때 앞의 값을 제거 해야하므로 pop(0)을 해주어야 한다. pop(0)의 시간복잡도는 O(n)이므로 O(1)보다는 효율적이지 못하다. O(1)인 방법으로 해결하기 위해 collections에서 deque를 import해주어 queue를 구현해볼 수 있다. 참고로 Queue 모듈에서 queue를 사용할 수 있지만, Queue 모듈은 멀티 스레딩 환경까지 고려해 스레드간에 안전한 방식으로 동작하는 모듈이라 속도가 느리다고 한다. 그래서 멀티 스레딩을 고려하지 않아도 되는 경우에는 deque를 사용한다. deque는 멀티스레딩 환경을 고려하지 않아 스레드 간에 안전하지 않지만 속도가 빠른 장점이 있다고 한다.

 

queue = [] #얘만으로도 가능은 하지만...

import sys
from collections import deque
input = sys.stdin.readline

a = int(input())
queue = deque()

for _ in range(a):
    x = input().split()
    if x[0] == 'push': queue.append(x[1])
    elif x[0] == 'pop':
        if queue: print(queue.popleft())
        else: print(-1)
    elif x[0] == 'size': print(len(queue))
    elif x[0] == 'empty':
        if queue: print(0)
        else: print(1)
    elif x[0] == 'front':
        if queue: print(queue[0])
        else: print(-1)
    else:
        if queue: print(queue[-1])
        else: print(-1)

백준 28278번을 빌려 코드를 작성해보았다. deque의 popleft(), appendleft(x), pop(), append(x)는 시간복잡도가 모두 O(1)이라서 그냥 리스트로 구현할 때보다 효율적이라고 할 수 있다. 하지만 무작위 접근에서의 시간복잡도가 O(n)인데, 이는 큐가 연결리스트로 구성되어 있기 때문이다. 여담으로 리스트는 무작위 접근에 최적화 되어 있어 시간복잡도가 O(1)이다.

 

큐의 응용

 

큐를 활용하여 다양한 형태의 큐를 만들 수 있다고 하는데 아직은 잘 모른다... 천천히 알아보도록 하자...