💡 큐

이미지 출처

큐(Queue)란?

큐는 한쪽끝에서는 입력만, 다른 한쪽끝에서는 출력만 동작하는 자료구조이다.
큐는 가장먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO)로
데이터가 입력되는 곳을 BACK또는 REAR라고 하며 데이터가 출력되는 곳을 FRONT라고 한다.
예시) 사람들이 줄을 서서 가게에 들어가는 모습

📢 18258번 문제

백준 문제 링크

📢 풀이

사용 언어 : python
어려운 점 : 시간초과 발생
POP을 사용하게되면 시간복잡도가 O(n)이 되어 시간초과가 발생한다.

해결방법 1

• pop을 사용하여 제거를 하지말고 맨 앞부분을 가리키고 있는 index를 pop기능을 수행할 때마다 +1씩 더해주기

해결방법 2

• deque 이용하기 , pop대신 popleft를 사용하기
  deque는 양방향에서 삽입과 삭제가 가능한 시간복잡도가 O(1)인 자료구조이다.

🔎 코드

✔ 해결방법1 코드 : index + 1 해주기

import sys
n = int(input())
result = []
a = 0
for i in range(n):
    x = sys.stdin.readline().split()
    if x[0] == "push":
        result.append(int(x[1]))
    elif x[0] == "size":
        print(len(result)-a)
    elif x[0] == "pop":
        if len(result)-a:
            print(result[a])
            a += 1
        else:
            print(-1)
    elif x[0] == "empty":
        if len(result)-a:
            print(0)
        else:
            print(1)
    elif x[0] == "front":
        if len(result)-a:
            print(result[a])
        else:
            print(-1)
    elif x[0] == "back":
        if len(result)-a:
            print(result[-1])
        else:
            print(-1)

✔ 해결방법2 코드 : deque 사용

import sys
from collections import deque

n = int(input())
result = deque()
for i in range(n):
    x = sys.stdin.readline().split()
    if x[0] == "push":
        result.append(int(x[1]))
    elif x[0] == "size":
        print(len(result))
    elif x[0] == "pop":
        if result:
            print(result.popleft())
        else:
            print(-1)
    elif x[0] == "empty":
        if result:
            print(0)
        else:
            print(1)
    elif x[0] == "front":
        if result:
            print(result[0])
        else:
            print(-1)
    elif x[0] == "back":
        if result:
            print(result[-1])
        else:
            print(-1)