백준 - 18528번(큐 구현하기)

큐란 무엇인가?

선입선출 구조이다.

스택은 프링글스 통에 자료를 차곡차곡 쌓아서 제일 먼저 넣은 친구를 가장 나중에 뺀다.

그러나 큐는 프링글스통에 밑에 구멍이 있는 파이프 같은 녀석이다.

가장 먼저 넣은 녀석을 가장 먼저 뺀다.

스택은 입구와 출구가 같고, 큐는 입구와 출구가 다르다.

 <스택>

(입구, 출구) 0ㅁㅁㅁㅁ 

<큐>

(입구) 0ㅁㅁㅁㅁ0 (출구) 

 

1) collections 모듈에서 deque를 import 하지 못하는 상황에서는 다음과 같다.

넣기: insert(0,x) 를 실행시키면 리스트 가장 앞에 원소를 넣을 수 있다.

빼기: pop(0)을 실행시키면 리스트 가장 앞의 원소를 빼내고 출력할 수 있다.

이럴 경우 성능 측면에서 불리한 것이 많다. 각 연산의 시간 복잡도는 O(N)이다.

 

2) 그러나 collections 모듈에서 deque를 import 할 수 있는 상황에서는 다음과 같다.(가장 추천)

ex) arr = deque()

넣기: appendleft() 를 실행시키면 리스트 가장 앞에 원소를 넣는다.

빼기 : popleft() 를 실행시키면 리스트 가장 앞의 원소를 빼내고 출력한다.

이 경우 시간복잡도가 각 연산당 O(1)이다. append()와 pop()을 사용해서 양방향에서 데이터를 추가할 수 있는 장점도 있다.

다만 무작위 접근을 할땐 내부적으로 linked list로 이루어져 있기 때문에 i번째 데이터에 접근하기 위해선 i번 반복을 해야 하기 때문에

시간 복잡도가 O(N) 이다.

 

3) queue 모듈에서 Queue를 import 하는 방법도 있다.

ex) arr = Queue() #대문자 주의

넣기: put()를 실행시키면 리스트 가장 앞에 원소를 넣는다.

빼기 : get()를 실행시키면 리스트 가장 앞의 원소를 제거한다.

이는 deque와 다르게 양방향성을 가지지 않기 때문에 위 두 명령어로만 자료의 처리가 가능하다.

멀티스레딩을 지원해서 여러 개의 스레드가 동시에 데이터 추가 삭제가 가능하다.

각 연산의 시간 복잡도는 O(1)이고 무작위 접근을 할 때는 O(N)의 시간을 갖는다.

 

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
arr = deque([])
for i in range(n):
    x = [[0][0]]
    x = sys.stdin.readline().strip().split()

    if x[0] == 'push':
        arr.append(int(x[1]))

    elif x[0] == 'pop':
        if len(arr) == 0:
            print(-1)

        else:
            print(arr.popleft())

    elif x[0] == 'size':
        print(len(arr))

    elif x[0] == 'empty':
        if len(arr) == 0:
            print(1)
        else:
            print(0)

    elif x[0] == 'front':
        if len(arr) == 0:
            print(-1)
        else:
            print(arr[0])

    elif x[0] == 'back':
        if len(arr) == 0:
            print(-1)
        else:
            print(arr[-1])

deque를 사용해서 만든 큐 구현 프로그램이다.