✔️ Deque

deque라는 이름은 Double Ended Queue의 약자입니다. deque는 양쪽 끝에서 요소의 삽입과 삭제를 지원하는 선형 자료구조입니다. deque는 FIFO, LIFO 동작으로 모두 사용할 수 있습니다.

💡 큐는 단방향으로 삽입과 삭제가 이루어집니다.

1.1 메소드

deque의 메서드는 두 가지 형식으로 존재합니다. 하나는 작업이 실패할 경우 예외를 발생시키고, 다른 하나는 작업이 이루어진 결과 값(또는 null)을 반환합니다.

	First Element (Head)		Last Element (Tail)
	Throws exception	Special value	Throws exception	Special value
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst	pollFirst	removeLast()	pollLast()
Examine	getFirst()	peekFirst()	getLast()	peekLast()

1.2 시간 복잡도

• 원소의 추가/ 제거 O(1)
• First Element / Last Element 확인 O(1)

1.3 구현

Leetcode - 641. Design Circular Deque

class MyCircularDeque {

        Deque<Integer> deque;
        int size;

        public MyCircularDeque(int k) {
            deque = new LinkedList<>();
            size = k;
        }

        public boolean insertFront(int value) {
            if (deque.size() == size) {
                return false;
            }
            deque.offerFirst(value);
            return true;
        }

        public boolean insertLast(int value) {
            if (deque.size() == size) {
                return false;
            }
            deque.offer(value);
            return true;
        }

        public boolean deleteFront() {
            if (deque.isEmpty()) {
                return false;
            }
            deque.removeFirst();
            return true;
        }

        public boolean deleteLast() {
            if (deque.isEmpty()) {
                return false;
            }
            deque.removeLast();
            return true;
        }

        public int getFront() {
            if (!deque.isEmpty()) {
                return deque.getFirst();
            }
            return -1;
        }

        public int getRear() {
            if (deque.isEmpty()) {
                return deque.getLast();
            }
            return -1;
        }

        public boolean isEmpty() {
            return deque.isEmpty();
        }

        public boolean isFull() {
            return deque.size() == size;
        }
    }

    class MyCircularDeque2 {
        class DoublyLinkedList {
            DoublyLinkedList left;
            DoublyLinkedList right;
            int val;

            public DoublyLinkedList (int val) {
                this.val = val;
            }
        }

        int len;
        int k;
        DoublyLinkedList head;
        DoublyLinkedList tail;

        public MyCircularDeque2(int k) {
            this.k = k;
        }

        public boolean insertFront(int value) {
            if (isFull()) {
                return false;
            }
            if (isEmpty()) {
                head = new DoublyLinkedList(value);
                tail = head;
            } else {
                DoublyLinkedList node = new DoublyLinkedList(value);
                head.left = node;
                node.right = head;
                head = node;
            }
            len++;
            return true;
        }

        public boolean insertLast(int value) {
            if (isFull()) {
                return false;
            }
            if (isEmpty()){
                head = new DoublyLinkedList(value);
                tail = head;
            } else {
                DoublyLinkedList node = new DoublyLinkedList(value);
                tail.right = node;
                node.left = tail;
                tail = node;
            }
            len++;
            return true;
        }

        public boolean deleteFront() {
            if (isEmpty()) {
                return false;
            }
            if (len == 1) {
                head = null;
                tail = null;
            } else {
                head = head.right;
                head.left = null;
            }
            len--;
            return true;
        }

        public boolean deleteLast() {
            if (isEmpty()) {
                return false;
            }
            if (len == 1) {
                head = null;
                tail = null;
            } else {
                tail = tail.left;
                tail.right = null;
            }
            len--;
            return true;
        }

        public int getFront() {
            if (len == 0) {
                return -1;
            }
            return head.val;
        }

        public int getRear() {
            if (len == 0) {
                return -1;
            }
            return tail.val;
        }

        public boolean isEmpty() {
            return len == 0;
        }

        public boolean isFull() {
            return len == k;
        }
    }