[Java-자료구조] Deque 사용과 구현

Deque

• 선형 자료구조
• 컨테이너의 양쪽 끝에서 삽입과 제거가 이루어지는 스택과 큐를 합쳐놓은 자료구조
• Deque에는 일반적인 Deque와 한쪽에서만 입력하도록 제한된 Scroll Deque, 한쪽에서만 제거하도록 제한된 Shelf Deque가 있다.

 Deque

멤버변수: rear, head( element가 삽입되거나 제거되는 위치)

Deque 사용법

import java.util.Deque

자바는 java.util.Deque interface로 Queue를 제공하고 있다.

 

Deque 선언

Deque<Integer> deque = new LinkedList<>(); // Deque를 구현한 linkedlist class 이용
Deque<Integer> deque1 = new ArrayDeque<>(); // Deque를 구현한 ArrayDeque class 이용

Deque 자체는 인터페이스이기 때문에 이를 구현한 ArrayDeque, LinkedList, LinkedBlockingDeque와 같은 클래스를 사용해야 한다.

 

Deque 메서드

데이터 삽입(Push)

deque.add(E element); // rear부분에 추가
deque.addFirst(E element); // head부분에 추가
deque.addLast(E element); // rear부분에 추가
//성공시 true 꽉찬 상태인 경우 IllegalStateException 반환

deque.offer(E element); // rear부분에 추가
deque.offerFirst(E element); // head부분에 추가
deque.offerFirst(E element); // rear부분에 추가
//성공시 true 꽉찬 상태인 경우 false반환

 

데이터 삭제(Pop)

deque.remove(); // head부분 element 제거
deque.removeFirst(); // head부분 element 제거
deque.removeLast(); // rear부분 element 제거
//성공시 true 비어있는 상태인 경우 NoSuchElementException 반환

deque.poll(); // head부분 element 제거
deque.pollFirst(); // head부분 element 제거
deque.pollFirst(); // rear부분 element 제거
//성공시 true 비어있는 상태인 경우 false 반환

 

데이터 검색

deque.element(); // head에 있는 element를 반환
// 존재하면 element를 반환하고 존재하지 않으면 NoSuchElementException를 반환

deque.peek(); // head에 있는 element를 반환
deque.peekFirst(); // head에 있는 element를 반환
deque.peekLast(); // rear에 있는 element를 반환
// 존재하면 해당 element를 반환하고 존재하지 않으면 null 반환

 

이외에도 LinkedList의 메소드를 그대로 모두 사용 가능하다.

 

Deque 시간복잡도

동작	시간복잡도 Big O
Insertion	O(1)
Deletion	O(1)
Search	O(1)  - index를 이용한 접근시 / O(N) - element로 검색

---

 

Deque 장단점

장점

• 크기가 가변적이다
• 앞과 뒤에서의 삽입과 삭제가 용이하며 빠르다.
• index를 이용한 임의 접근이 가능하다.
• list보다 속도가 빠르며 쓰레드 환경에서 안전하다.

단점

• Deque의 중간에서의 삽입과 삭제가 어렵다.

 

---

구현

Queue interface

public interface Queue<E> {

    boolean add(E element); // element를 Queue에 추가 저장공간이 부족하면 IllegalStateException

    boolean offer(E element); // element를 Queue에 추가

    E element(); // 삭제없이 front의 요소를 가져온다. 비어있으면 NoSuchElementException

    E peek();  // 삭제없이 front의 요소를 가져온다.

    E remove(); // 객체를 꺼내서 반환  비어있으면 NoSuchElementException

    E poll(); // 객체를 꺼내서 반환
}

 

Deque using LinkedList

public class Deque<E> extends DoublyLinkedList<E> implements Queue<E>{

    Deque(){
        super();
    }

    @Override
    public boolean offer(E element){
        addLast(element);
        return true;
    }

    public boolean offerFirst(E element){
        addFirst(element);
        return false;
    }

    public boolean offerLast(E element){
        addLast(element);
        return false;
    }

    @Override
    public E element(){
        return getFirst();
    }

    @Override
    public E peek(){
        return peekFirst();
    }

    public E peekFirst(){
        return getFirst();
    }

    public E peekLast(){
        return getLast();
    }

    @Override
    public E poll(){
        return pollFirst();
    }

    public E pollFirst(){
        return removeFirst();
    }

    public E pollLast(){
        return removeLast();
    }
}

LinkedList 코드

import java.lang.reflect.Array;
import java.util.NoSuchElementException;

public class DoublyLinkedList<T> implements List<T>, Cloneable {

    protected DoublyLinkedListNode<T> head;
    protected DoublyLinkedListNode<T> tail;
    protected int size;

    DoublyLinkedList(){
        head = null;
        tail = null;
        size = 0;
    }

    private DoublyLinkedListNode<T> search(int index){
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        DoublyLinkedListNode<T> tmp = head;
        for(int i=0; i<index; i++){
            tmp = tmp.getNext();
        }
        return tmp;
    }

    public void addFirst(T element){
        DoublyLinkedListNode<T> tmp = head;
        head = new DoublyLinkedListNode<>(element);
        if(tmp == null){
            tail = head;
            size++;
            return;
        }
        tmp.setPrev(head);
        head.setNext(tmp);
        size++;
    }

    public void addLast(T element){
        if(size == 0){
            addFirst(element);
            return;
        }
        DoublyLinkedListNode<T> tmp = tail;
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(element);
        tail = newNode;
        tmp.setNext(tail);
        tail.setPrev(tmp);
        size++;
    }

    @Override
    public boolean add(T element) {
        addLast(element);
        return true;
    }


    @Override
    public void add(int index, T element) {
        if(index<0 || index > size){
            throw new IndexOutOfBoundsException();
        }
        if(index==0){
            addFirst(element);
            return;
        }
        if(index==size){
            addLast(element);
            return;
        }
        DoublyLinkedListNode<T> newNode = new DoublyLinkedListNode<>(element);
        DoublyLinkedListNode<T> prevNode = search(index-1);
        DoublyLinkedListNode<T> nextNode = prevNode.getNext();

        prevNode.setNext(newNode);
        newNode.setPrev(prevNode);
        newNode.setNext(nextNode);
        nextNode.setPrev(newNode);
        size++;
    }

    public T removeFirst(){
        DoublyLinkedListNode<T> headNode = head;
        if(headNode == null){
            throw new NoSuchElementException();
        }
        T element = headNode.getData();
        DoublyLinkedListNode<T> nextNode = head.getNext();
        head.setData(null);
        head.setNext(null);
        head = nextNode;
        size--;

        if(size==0){
            tail = null;
        }
        return element;
    }

    public T removeLast(){
        if(size==1) {
            return removeFirst();
        }
        DoublyLinkedListNode<T> prevNode = tail.getPrev();
        T element = tail.getData();
        tail.setNext(null);
        tail.setPrev(null);
        tail.setData(null);
        tail = prevNode;
        size--;
        if(size==0){
            tail = null;
        }
        return element;
    }

    public T remove(){
        return removeFirst();
    }

    @Override
    public T remove(int index) {
        if(index == 0){
            return removeFirst();
        }
        if(index < 0 || index >= size){
            throw new IndexOutOfBoundsException();
        }
        DoublyLinkedListNode<T> prevNode = search(index-1);
        DoublyLinkedListNode<T> targetNode = prevNode.getNext();
        DoublyLinkedListNode<T> nextNode = targetNode.getNext();
        T data = targetNode.getData();

        prevNode.setNext(nextNode);
        nextNode.setPrev(prevNode);
        targetNode.setData(null);
        targetNode.setNext(null);
        targetNode.setPrev(null);
        size--;
        return data;
    }

    @Override
    public boolean remove(Object element) {
        DoublyLinkedListNode<T> prevNode = head;
        DoublyLinkedListNode<T> tmp = head;

        for(;tmp != null; tmp = tmp.getNext()){
            if(element.equals(tmp.getData())){
                break;
            }
            prevNode = tmp;
        }

        if(tmp == null){
            return false;
        }

        if(tmp.equals(head)){
            remove();
        }else{
            prevNode.setNext(tmp.getNext());
            tmp.getNext().setPrev(prevNode);
            tmp.setData(null);
            tmp.setNext(null);
            size--;
        }
        return false;
    }

    public T getFirst(){
        return head != null ? head.getData() : null;
    }

    public T getLast(){
        return tail != null ? tail.getData() : null;
    }

    @Override
    public T get(int index) {
        DoublyLinkedListNode<T> targetNode = search(index);
        return targetNode.getData();
    }

    @Override
    public void set(int index, T element) {
        DoublyLinkedListNode<T> targetNode = search(index);
        targetNode.setData(element);
    }

    @Override
    public boolean contains(Object element) {
        return indexOf(element)>=0;
    }

    @Override
    public int indexOf(Object element) {
        int index = 0;
        for(DoublyLinkedListNode<T> i = head; i!=null;i=i.getNext()){
            if(element.equals(i.getData())){
                return index;
            }
            index++;
        }
        return -1;
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public void clear() {
        for(DoublyLinkedListNode<T> i = head; i!= null;){
            DoublyLinkedListNode<T> nextNode = i.getNext();
            i.setData(null);
            i.setNext(null);
            i.setPrev(null);
            i = nextNode;
        }
        head = null;
        tail = null;
        size = 0;
    }

    public Object clone() throws CloneNotSupportedException {
        DoublyLinkedList<? super T> clone = (DoublyLinkedList<? super T>) super.clone();
        clone.head = null;
        clone.tail = null;
        clone.size = 0;

        for(DoublyLinkedListNode<T> i = head; i != null; i = i.getNext()){
            if(i.getData()!=null){
                clone.add(i.getData());
            }
        }
        return clone;
    }

    public Object[] toArray(){
        Object[] array = new Object[size];
        int index = 0;
        for(DoublyLinkedListNode<T> i = head; i!=null;i=i.getNext()){
            array[index++] = (T) i.getData();
        }
        return array;
    }

    public <E> E[] toArray(E[] array){
        if(array.length<size) {
            array = (E[]) Array.newInstance(array.getClass().getComponentType(), size);
        }
            int index = 0;
            Object[] result = array;
            for(DoublyLinkedListNode<T> j=head; j!=null; j=j.getNext()){
                result[index++] = j.getData();
            }
            return array;
    }
}

 

---

알고리즘 사용 사례 with Deque

• 스택이나 큐의 방식으로 사용 가능하며 head와 tail부분의 값을 빼는데 유리
• push와 pop 연산이 자주 일어나는 경우