[DataStructures] 큐(queue) - 더블링크드리스트를 이용한 데큐(Deque using doubly linked list)

더블링크드리스트 데큐 - Deque using doubly linked list

- 데큐(deque)를 링크드 리스트로 구현한다

1. Node<T>.class

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Node<T>{           private T data;     private Node<T> next;     private Node<T> pre;           public T getData() {         return data;     }     public void setData(T data) {         this.data = data;     }     public Node<T> getNext() {         return next;     }     public void setNext(Node<T> next) {         this.next = next;     }     public Node<T> getPre() {         return pre;     }     public void setPre(Node<T> pre) {         this.pre = pre;     }       }

- doubly linked list 이기 때문에 pre, next 가 선언 되었다

2. DoubleLinkedListDeque<T>.class

1) 초기화

?

1 2 3

Node<T> front; Node<T> rear; int size = 0;

 

- 링크드 리스트로 구현하기 때문에 삽입과 삭제되는 부분을 컨트롤할 front, rear가 필요하다

- size를 지정함으로 유연하게 deque를 컨트롤 한다

2) addFirst(E element), addLast(E element)

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

public void addFront(T element){               Node<T> newNode = new Node<>();           newNode.setData(element);     newNode.setNext(front);           if(front != null){         front.setPre(newNode);     }     if(front == null){         rear = newNode;     }           front = newNode;         size++; }       public void addLast(T element){           Node<T> newNode = new Node<>();     newNode.setPre(rear);     newNode.setData(element);           if(rear != null){         rear.setNext(newNode);     }     if(rear == null){         front = newNode;     }     rear = newNode;     size++; }

 

- deque 이기 때문에 삽입이 자유롭다

3) removeFront(), removeLast()

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

public void removeLast()throws Exception{     if(isNullCheck()){         throw new Exception("List is null");     }else{         Node<T> temp = rear.getPre();                   if(temp != null){             temp.setNext(null);         }         if(temp == null){             front = null;         }         rear = temp;                   temp = null;                   size--;     } }       public void removeFront()throws Exception{           if(isNullCheck()){         throw new Exception("List is null");     }{         Node<T> temp = front.getNext();         if(temp != null){             temp.setPre(null);         }         if(temp == null){             rear = null;         }         front = temp;                   temp = null;                   size--;               } }

 

4) isNullCheck(), toString()

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

public boolean isNullCheck(){     return(size == 0); }   public String toString(){           Node<T> temp = front;     String str = "{";           if(temp != null){         for(int i = 0; i<size-1; i++){             str += temp.getData()+",";             temp = temp.getNext();                       }         str += temp.getData();     }           str += "}";     return str;       }

 

- 큐가 비었는지 체크와 현재 상태를 출력하는 함수 이다

5) main()

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public static void main(String[]args){     DoubleLinkedListDeque<Integer> list = new DoubleLinkedListDeque<>();           try{         list.addFront(1);         list.addFront(2);         list.addFront(3);         list.addLast(4);         list.addLast(5);         list.removeFront();         list.removeLast();         list.removeLast();         list.removeLast();         list.removeLast();         System.out.println(list);     }catch(Exception e){         System.out.println(e.getMessage());     } }