[자료구조] [python] Queue using Two Stacks

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. 

 

www.hackerrank.com/challenges/queue-using-two-stacks/problem

Queue using Two Stacks | HackerRank

 

 

• 이번 문제는 python의 deque모듈을 이용하면 쉽게 풀 수 있는 문제다.
• python의 collections의 deque 모듈을 사용하여, 자료의 양 끝에서 항목의 조회, 삽입, 삭제를 효율적으로 할 수 있다. 특히 양쪽 끝에 있는 원소를 삽입/삭제 하는데 시간효율성은 O(1)이다. rotate(n) 메서드는 n이 양수이면 오른쪽으로, n이 음수이면 왼쪽으로 n만큼 시프트할 수 있다.
• collections 패키지의 deque모듈은 동적 배열이 아닌, 이중 연결 리스트다. (추가 참고, 파이썬 공식 라이브러리 설명집 : docs.python.org/3.8/library/collections.html#collections.deque)

 

import sys
from collections import deque

query = int(input())
temp = deque()

for q in range(query):
    i = input()
    typ =list(map(int, i.split()))
        
    if typ[0] == 1 :
        temp.append(typ[1])
    elif typ[0] == 2:
        temp.popleft()
    else:
        print(temp[0])