[Algorithm] 백준 10845번: 큐 | 연결 리스트와 큐를 클래스로 구현

문제 출처: https://www.acmicpc.net/problem/10845

---

1. 결과

메모리 29200KB, 시간 80ms

2. 풀이

문제에서 제시한 연산 6개를 수행할 수 있는 기본적인 자료구조 큐를 구현해보는 문제였다. 큐는 FIFO(First In First Out), 선입선출의 특징을 갖는 자료구조로써, 말 그대로 먼저 들어온 자료가 먼저 출력되는 형태이다. 현실에서는 선착순, 은행 대기줄 등의 상황을 예시로 들 수 있다. 파이썬에서 제공하는 자료 타입인 리스트(list, 자료구조인 리스트와는 다른 것)로도 구현할 수 있는데, 기본적으로 파이썬의 리스트 타입은 자료구조 중 '배열'이고, 그중에서도 기본적으로는 스택을 구현한 형태를 갖는다. append를 하면 가장 뒤에 쌓이고, pop을 하면 가장 뒤에 있는 것이 출력되기 때문에, 선입후출, 후입선출의 형태를 갖는 것이다. 그렇기 때문에 이 리스트 타입을 이용하려면 유의하며 구현해야 한다.

나는 이 문제에서 일반적인 배열을 이용하지 않고, 연결 리스트로 구현해봤다. 특정 위치의 자료 탐색은 배열이 유리하지만, 자료의 삽입과 삭제는 연결 리스트가 더 유리하기 때문에, 한 번 연결 리스트로 구현해보고 싶었다. 연결 리스트는 파이썬에서 기본적으로 제공하는 것은 아니기 때문에, 클래스로써 구현해야 했다. 큐 또한 한 번 클래스 사용에 익숙해지기 위해 클래스로써 같이 구현해서 코드를 작성했다. 연결 리스트와 문제에서 제시한 연산을 수행하는 자료구조 큐는 아래 코드와 같다.

import sys

# 연결 리스트
class LinkedListElement:
    def __init__(self, val,  p, n):
        self.value = val
        self.prev = p
        self.next = n

# 큐
class Queue:
    def __init__(self):
        self.start = None
        self.end = None
        self.count = 0
    
    def push(self, x):
        if self.empty():
            elem = LinkedListElement(x, None, None)
            self.start = self.end = elem
        else:
            elem = LinkedListElement(x, self.end, None)
            self.end.next = elem
            self.end = elem
        self.count += 1
        return
    
    def pop(self):
        if self.empty(): return -1
        elif self.size() == 1:
            start = self.start.value
            self.start = self.end = None
        else:
            start = self.start.value
            startNext = self.start.next
            self.start = startNext
            self.start.prev = None
        self.count -= 1
        return start
    
    def size(self):
        return self.count
    
    def empty(self):
        if self.count == 0: return 1
        return 0
    
    def front(self):
        if self.empty(): return -1
        return self.start.value
    
    def back(self):
        if self.empty(): return -1
        return self.end.value

def main():
    N = int(sys.stdin.readline())
    q = Queue()
    for _ in range(N):
        command = sys.stdin.readline().split()
        if command[0] == 'push': q.push(int(command[1]))
        elif command[0] == 'pop': print(q.pop())
        elif command[0] == 'size': print(q.size())
        elif command[0] == 'empty': print(q.empty())
        elif command[0] == 'front': print(q.front())
        elif command[0] == 'back': print(q.back())
    return

if __name__ == "__main__":
    main()