[Java] Deque 구현

Deque를 잘 모르신다면 여기를 눌러주세요.

 

 

구현하는 Deque 기능

• pushFront(element) → 앞쪽에 요소 추가
• pushBack(element) → 뒷쪽에 요소 추가
• popFront() → 앞쪽 원소 제거 및 반환
• popBack() → 뒷쪽 원소 제거 및 반환
• peekFront() → 앞쪽 원소 확인(제거하지 않음)
• peekBack() → 뒷쪽 원소 확인(제거하지 않음)
• isEmpty() → 비어 있는지 확인(true/false)

 

Deque 구현하기(Linked List)

혹시 기능만 보고 구현하시고 싶으신 분을 위해 숨김으로 하겠습니다.

public class Deque {
    private Node front;
    private Node back;
    private int size;

    public Deque() {
        front = null;
        back = null;
        size = 0;
    }

    public void pushFront(int value) {
        Node node = new Node(value);

        if (isEmpty()) {
            front = node;
            back = node;
        } else {
            node.next = front;
            front.prev = node;
            front = node;
        }

        size++;
    }

    public void pushBack(int value) {
        Node node = new Node(value);

        if (isEmpty()) {
            front = node;
            back = node;
        } else {
            back.next = node;
            node.prev = back;
            back = node;
        }

        size++;
    }

    public int popFront() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }

        int result = front.value;
        front = front.next;

        if (front == null) {
            back = null;
        } else {
            front.prev = null;
        }

        size--;
        return result;
    }

    public int popBack() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }

        int result = back.value;
        back = back.prev;

        if (back == null) {
            front = null;
        } else {
            back.next = null;
        }

        size--;
        return result;
    }

    public int peekFront() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        return front.value;
    }

    public int peekBack() {
        if (isEmpty()) {
            throw new NoSuchElementException("Deque is empty");
        }
        return back.value;
    }

    public int size() {
        return size;
    }

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

    private static class Node {
        int value;
        Node prev;
        Node next;

        public Node(int value) {
            this.value = value;
        }
    }
}