Deque 파이썬[자료구조]

덱(Deque = Double Ended Queue)

 

덱은 데이터 값을 저장하는 기본적 구조로, 일차원 선형구조이다.

스택과 큐의 연산을 모두 지원하는 자료구조로서 양끝에서 삽입과 삭제가 가능한 큐이다.

 

collections  모듈의 deque 클래스에 구현되어 있으며 양끝에서 삽입과 삭제를 할 수 있어야 하므로 양방향 연결리스트(Doubly Linked List ) 로 구성되어있다. 값을 삽입 삭제하는 용도로 활용할경우 

시간복잡도는 O(1)로서 효율적이다.

 

백준 18258 큐 

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

N = int(input())

Que = deque()

for _ in range(N):
    A = list(input().split())

    if A[0]=='push':
        Que.append(A[1])
    
    elif A[0]=='pop':
        try: print(Que.popleft())
        except: print(-1)


    elif A[0]=='front':
        try:print(Que[0])
        except: print(-1)
    
    elif A[0]=='back':
        try:print(Que[-1])
        except: print(-1)
    
    elif A[0]=='size':
        print(len(Que))
    
    elif A[0]=='empty':
        if len(Que)==0:
            print(1)
        else : print(0)

참조 블로그
https://mong9data.tistory.com/50