[백준 18258] 큐 2(Python)

링크드 리스트를 직접 구현하고, 이를 토대로 큐를 만들었다.

1. 아이디어

링크드리스트를 직접 구현하고, 이를 기반으로 큐를 만들 때, header node와 tail node를 추가했다. header node의 data에 큐의 삽입 연산으로 들어간 node의 개수를 기록했다. tail node의 경우, 마지막으로 들어간 node의 link가 None이라는게 마음에 안들어서 넣었다. 큐의 연산을 수행할 때, 연산 종류에 상관 없이, 삽입 연산으로 들어간 node의 존재 유무를 고려해서 구현한다.

header node - 1번째로 삽입된 node - 2번째로 삽입된 node - ... - tail node 형식으로 구현했다. 이를 위해 마지막 node를 가리키는 pointer 변수를 뒀고 이 변수는 back 연산에서도 사용 된다.

2. 코드

import sys

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

class LinkedList:
    def __init__(self):
        self.header = Node(0)
        self.tail = Node(0)
        self.header.link = self.tail
        self.tail.link = self.tail
        self.pointer = self.header

    def push(self, node):
        if self.header.link is self.tail:
            node.link = self.tail
            self.header.link = node
            self.pointer = node

        else:
            node.link = self.pointer.link
            self.pointer.link = node
            self.pointer = node
        
        self.header.data += 1
    
    def pop(self):
        if self.header.link is self.tail: return -1
        else:
            data = self.header.link.data
            node = self.header.link
            self.header.link = self.header.link.link
            self.header.data -= 1
            del node
            return data
    
    def front(self):
        if self.header.data == 0: return -1
        else: return self.header.link.data
    
    def back(self):
        if self.header.data == 0: return -1
        else: return self.pointer.data
    
    def size(self):
        return self.header.data
    
    def empty(self):
        return 1 if self.header.data == 0 else 0 
    
tc = int(sys.stdin.readline().rstrip())
linkedlist = LinkedList()

while tc:
    cmd = sys.stdin.readline().rstrip()
    if 'push' in cmd:
        string, data = cmd.split()
        linkedlist.push(Node(int(data)))
    
    elif cmd == 'front': print(linkedlist.front())
    elif cmd == 'pop': print(linkedlist.pop())
    elif cmd == 'size': print(linkedlist.size())
    elif cmd == 'empty': print(linkedlist.empty())
    elif cmd == 'back': print(linkedlist.back())

    tc -= 1