Deque를 직접 구현해보기

큐는 삽입과 삭제가 리스트의 한쪽 방향에서만 이루어지지만 deque는 리스트의 양쪽 끝 모두에서 이루어질 수 있다.

따라서 양쪽 방향 모두 삽입과 삭제가 이루어질 수 있으므로 기존의 큐나 스택으로 사용할 수 있어 유연하게 사용할 수 있다.

사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/

이런 Deque를 직접 구현해 보자.

우선 Deque의 기능을 정리한 인터페이스이다.

package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 

그리고 인터페이스를 가지고 구현된 Deque

package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 

그리고 이 deque를 가지고 테스트를 진행할 Main클래스

package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 

출력결과

Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 20

> af 30

> af 10

> p

10,30,20

> rf

> p

30,20

> rl

> p

30

> al 33

> al 22

> p

30,33,22

> r

22,33,30

> p

30,33,22

> af 44

> al 88

> p

44,30,33,22,88

> rl

> rf

> p

30,33,22

> rf

> p

33,22

> rl

> p

33

> q

Commands Terminated.

다음 시간에는 이것을 이용해 버켓 정렬을 구현해보자.