[Python]Queue 백준 18258

   문제

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

앞에 문제를 끝내고 다시 자료구조로 돌아왔다.

큐를 구현하는 문제이다.

스택을 구현한곳에서 조금만 바꾸면 될 것 같았으나 시간초과가 떴다.

이유는 pop을 하는 과정에서 단순히 제거를 했을경우 pop을 할때마다 한칸씩 모두 옮겨야

 하는 작업을 할것이다.파이썬으로는 결국 통과하지 못했다.

pypy3으로 제출했을때 겨우 통과했다.

import sys
 
 
class Queue():
    def __init__(self):
        self.list=[]
        self.tail=0
        self.top=0#시간초과로 인해 pop의 경우 제거대신 top을 움직임
 
 
    def push(self,num):
        self.list.append(num)
        self.tail+=1
 
 
    def pop(self):
        if self.tail-self.top==0:
            return -1
        pop_result=self.list[self.top]
        self.top+=1
        return pop_result
 
    def size(self):
        return self.tail-self.top
 
    def empty(self):
        return 0 if self.tail-self.top else 1
 
    def front(self):
        if self.tail-self.top==0:
            return -1
        return self.list[self.top]
 
    def back(self):
        if self.tail-self.top==0:
            return -1
        return self.list[self.tail-1]
 
 
 
num=int(input())
queue=Queue()
command=[list(sys.stdin.readline().split()) for _ in range(num)]
 
 
for i in range(num):
    if command[i][0] == "push":
        queue.push(command[i][1])
    elif command[i][0] == "pop":
        print(queue.pop())
    elif command[i][0] == "size":
        print(queue.size())
    elif command[i][0] == "empty":
        print(queue.empty())
    elif command[i][0] == "front":
        print(queue.front())
    elif command[i][0] == "back":
        print(queue.back())

제출 결과를 보니 파이썬으로 통과한 사람들이 꽤있었다.

코드를 살펴보니 대부분 collections모듈의 deque를 사용하고 있었다.

collections.deque를 찾아보니 여러가지 함수가 포함되어있는데

일반적인 스택과 큐는 물론 회전큐를 위한 함수도 있었다.

이번에는 따로 이 모듈을 다루지 않겠지만 밑에문제에서 써야될거 같다.