[420] 파이썬 큐(Queue) 구현하기

1. 큐(Queue)

큐는 자료구조 중 하나로 선입선출(First In First Out, FIFO) 하는 추상적인 개념을 말합니다.

보통 큐를 연결리스트를 이용하여 구현합니다.

https://ko.wikipedia.org/wiki/큐_(자료_구조)

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

2. 큐 구현하기

가. 노드 class 만들기

연결리스트를 사용하기 때문에 먼저 노드 class를 만듭니다.

노드 객체는 값을 저장하는 data와 다음 연결되는 노드를 저장하는 next 속성을 가집니다.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

나. 큐 class 만들기

큐는 head와 tail을 가집니다.

새로운 값을 추가하면 tail 뒤에 추가되고, 제거하면 head에서 제거됩니다.

길이를 확인하려면 head에서 tail까지 선형 탐색을 해야해서 비효율적이므로, len 속성을 만들어 관리합니다.

메서드는 새로운 값을 추가하는 push와 head에 있는 값을 버리는 pop을 만듭니다.

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.len = 0
    
    def push(self, data):
        new_node = Node(data)
        self.len += 1
        if self.head == None:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

    def pop(self):
        if self.head == None:
            return -1
        self.len -= 1
        node = self.head
        self.head = self.head.next
        if self.head == None:
            self.tail = None
        return node.data

3. 구현한 큐로 문제 풀기

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

백준에서 큐를 구현하는 문제입니다.

위에서 만든 큐를 이용해서 풀 수 있습니다.

python3로 제출하면 시간초과가 나오므로 pypy3로 제출하였습니다.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
        self.len = 0
    
    def push(self, data):
        new_node = Node(data)
        self.len += 1
        if self.head == None:
            self.head = self.tail = new_node
            return
        self.tail.next = new_node
        self.tail = new_node

    def pop(self):
        if self.head == None:
            return -1
        self.len -= 1
        node = self.head
        self.head = self.head.next
        if self.head == None:
            self.tail = None
        return node.data
    
import sys
input = sys.stdin.readline
N = int(input())
q = Queue()
for _ in range(N):
    query = input().split()
    match query:
        case ["push", data]:
            q.push(data)
        case ["pop"]:
            print(q.pop())
        case ["size"]:
            print(q.len)
        case ["empty"]:
            print(int(q.len == 0))
        case ["front"]:
            print(q.head.data if q.head else -1)
        case ["back"]:
            print(q.last.data if q.tail else -1)