1. 개요

내장된 자료구조 큐를 사용하는데 왜 이렇게 구현하는지 궁금해졌습니다.

• 자바 - 링크드 리스트
• 파이썬 - deque

2. 큐

삽입 - 싱글 연결리스트

싱글 링크드리스트로 큐를 구현하면서 가장 시간이 오래 걸린점은 가장 마지막 노드에 원소를 삽입할때 탐색해야해서 O(n)이 걸렸습니다.

이를 해결하기 위해서 가장 마지막 노드를 tail에 저장하면 되는데 이렇게 할것이면 결국 더블 링크드 리스트로 만들어서, 덱을 만들고, 필요한 기능만 사용하는 것이 유리해보였습니다.

3. 코드

1) Python

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


class Deque:
    def __init__(self):
        self.__head = None
        self.__tail = None
        self.__cnt = 0

    def is_empty(self):
        return self.__cnt == 0

    def size(self):
        return self.__cnt

    def __increase(self):
        self.__cnt += 1

    def __decrease(self):
        if self.__cnt > 0:
            self.__cnt -= 1

    def add_first(self, val):
        node = Node(val)

        self.__head = node
        self.__tail = node

        self.__increase()

    def add_last(self, val):
        node = Node(val)

        self.__tail.next = node
        node.prev = self.__tail
        self.__tail = self.__tail.next

        self.__increase()

    def push(self, val):
        if self.is_empty():
            self.add_first(val)
        else:
            self.add_last(val)

    def pop_left(self):
        if not self.is_empty():
            head = self.__head

            if self.__head.next:
                self.__head = self.__head.next

            self.__decrease()

            return head.val
        else:
            return None

    def pop(self):
        if not self.is_empty():
            tail = self.__tail

            if tail.prev:
                self.__tail = self.__tail.prev

            self.__decrease()

            return tail.val
        else:
            return None

    def front(self):
        return self.__head.val

    def last(self):
        return self.__tail.val

2) Java

class Node {
    public int val;
    public Node next;
    public Node prev;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class Deque {
    private Node head;
    private Node tail;
    private int cnt;

    public Dequeue() {
        this.head = null;
        this.tail = null;
        this.cnt = 0;
    }

    public boolean isEmpty() {
        return this.cnt == 0;
    }

    public int size() {
        return this.cnt;
    }

    public void increase() {
        this.cnt++;
    }

    public void decrease() {
        if(this.cnt > 0) this.cnt--;
    }

    public void addFirst(int val) {
        Node node = new Node(val);

        this.head = node;
        this.tail = node;

        this.increase();
    }

    public void addLast(int val) {
        Node node = new Node(val);

        this.tail.next = node;
        node.prev = this.tail;
        this.tail = this.tail.next;

        this.increase();
    }

    public void push(int val) {
        if(this.isEmpty()) {
            this.addFirst(val);
        }
        else {
            this.addLast(val);
        }
    }

    public Integer popLeft() {
        if(!this.isEmpty()) {
            Node head = this.head;

            if(this.head.next != null) {
                this.head = this.head.next;
            }

            this.decrease();

            return head.val;
        }
        else {
            return null;
        }
    }

    public Integer pop() {
        if(!this.isEmpty()) {
            Node tail = this.tail;

            if(tail.prev != null) {
                this.tail = this.tail.prev;
            }

            this.decrease();

            return tail.val;
        }
        else {
            return null;
        }
    }

    public Integer front() {
        return this.head.val;
    }

    public Integer last() {
        return this.tail.val;
    }
}

3) JavaScript

class Node {
    constructor(val) {
        this.val = val
        this.next = null;
        this.prev = null;
    }
}

class Deque {
    constructor() {
        this.head = null
        this.tail = null
        this.cnt = 0
    }

    isEmpty() {
        return this.cnt === 0
    }

    size() {
        return this.cnt
    }

    increase() {
        this.cnt++
    }

    decrease() {
        if(this.cnt > 0) this.cnt--
    }

    addFirst(val) {
        const node = new Node(val)

        this.head = node
        this.tail = node

        this.increase()
    }

    addLast(val) {
        const node = new Node(val)

        this.tail.next = node
        node.prev = this.tail
        this.tail = this.tail.next

        this.increase()
    }

    push(val) {
        if(this.isEmpty()) {
            this.addFirst(val)
        }
        else {
            this.addLast(val)
        }
    }

    popLeft() {
        if(!this.isEmpty()) {
            const head = this.head

            if(this.head.next) {
                this.head = this.head.next
            }

            this.decrease()

            return head.val
        }
        else {
            return null
        }
    }

    pop() {
        if(!this.isEmpty()) {
            const tail = this.tail

            if(tail.prev) {
                this.tail = this.tail.prev
            }

            this.decrease()

            return tail.val
        }
        else {
            return null
        }
    }

    front() {
        return this.head.val
    }

    last() {
        return this.tail.val
    }
}