[백준 10845번] - Queue / Python

 

 

 

 

📍Deque

▪ 큐(Queue)는 선입선출 방식이다. 

▪ 그러나 자료의 개수가 많아지면 큐의 연산이 느려지기 때문에 데크를 사용하게 된다.

▪ 데크(Deque)는 양방향 큐로, 앞뒤 양쪽에서 요소를 추가하거나 제거할 수 있다.

 

 

그래서 나는 데크를 이용해서 문제를 풀었다.

 

 

📍 Deque의 장점

▪ 앞뒤에서 접근할 수 있기 때문에 append, pop이 매우 빠르다.

▪ 스택, 큐처럼 사용할 수 있다.

 

 

 

[백준 10845번] - Queue

https://www.acmicpc.net/problem/10845

10845번: 큐

 

(정답)

from collections import deque
import sys
n=int(input())
queue=deque()

def push(x):
    queue.append(x)

def pop():
    return queue.popleft() if queue else -1

def size():
    return len(queue)

def empty():
    return 0 if queue else 1

def front():
    return queue[0] if queue else -1

def back():
    return queue[-1] if queue else -1
    
        
for _ in range(n):
    cmd=sys.stdin.readline().split()

    if cmd[0]=='push':
        push(cmd[1])

    if cmd[0]=='pop':
        print(pop())

    if cmd[0]=='size':
        print(size())

    if cmd[0]=='empty':
        print(empty())

    if cmd[0]=='front':
        print(front())

    if cmd[0]=='back':
        print(back())

 

 

📍 Deque 메서드

▪ deque.append(value):  value를 오른쪽 끝에 삽입한다.

▪ deque.appendleft(value):  value를 왼쪽 끝에 삽입한다.

▪ deque.pop():  오른쪽 끝 요소를 가져오면서 동시에 삭제한다.

▪ deque.popleft():  왼쪽 끝 요소를 가져오면서 동시에 삭제한다.

▪ deque.extend(array):  배열(array)을 순환하며 해당 요소들을 오른쪽에 추가한다.

▪ deque.extendleft(array):  배열(array)을 순환하며 해당 요소들을 왼쪽에 추가한다.

▪ deque.remove(value):  value를 찾아서 삭제한다.

 

 

 

 

 

리스트에 비해서 push, pop에 대해 빠른 연산이 이루어짐을 확인할 수 있었다.

시간초과를 방지하고 싶을 때는 Deque를 사용하도록 하자!