Baekjoon 10866번 덱

문제

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

걸린 시간

-

풀이

Python3

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

class Deque():
    def __init__(self):
        self.front = None
        self.rear = None
        self.search = None
        self.count = 0

    def empty(self):
        if self.front == None:
            return 1
        else:
            return 0

    def size(self):
        return self.count

    def push_front(self, item):
        new = Node(item)
        self.count += 1
        if self.empty():
            self.front = new
            self.rear = new
        else:
             tmp = self.front
             self.front = new
             new.link = tmp

    def push_back(self, item):
        new = Node(item)
        self.count += 1
        if self.empty():
            self.front = new
            self.rear = new
        else:
             self.rear.link = new
             self.rear = new

    def pop_front(self):
        tmp = self.front
        if self.empty():
            return -1
        else:
            item = self.front.item
            self.front = tmp.link

            if self.front == None:
                self.rear = None

            self.count -= 1

            return item

    def pop_back(self):
        if self.empty():
            return -1
        else:
            item = self.rear.item

            if self.count < 2:
                self.front = None
                self.rear = None
            else:
                self.search = self.front

                for i in range(0, self.count-2):
                    self.search = self.search.link    

                self.rear = self.search
                self.rear.link = None 

            self.count -= 1

            return item

    def _front_(self):
        if self.empty():
            return -1
        else:
            return self.front.item

    def _back_(self):
        if self.empty():
            return -1
        else:
             return self.rear.item

if __name__ == "__main__":
    N = int(input())
    command = [input() for _ in range(0, N)]
    D = Deque()    
    for i in command:
        c = i.split(' ')
        if c[0] == "push_back":
            D.push_back(c[1])
        elif c[0] == "push_front":
            D.push_front(c[1])
        elif c[0] == "front":
            print(D._front_())
        elif c[0] == "back":
            print(D._back_())
        elif c[0] == "size":
            print(D.size())
        elif c[0] == "empty":
            print(D.empty())
        elif c[0] == "pop_front":
            print(D.pop_front())
        elif c[0] == "pop_back":
            print(D.pop_back())

덱 자료구조는 보통 이중 연결 리스트로 구현된다고 한다. 덱을 구현해보지 않은 상태에서 큐와 스택 개념을 이용해 단순 연결 리스트로 구현했기에 통과는 했지만 비효율적이다.