자료구조 undo 구현하기

• DNode

public class DNode<E>{
    DNode next;
    DNode previous;
    E item;

    public DNode(E item,DNode previous, DNode next) {
        this.item = item;
        this.previous = previous;
        this.next = next;
    }

    public DNode getNext() {
        return next;
    }

    public void setNext(DNode next) {
        this.next = next;
    }

    public DNode getPrevious() {
        return previous;
    }

    public void setPrevious(DNode previous) {
        this.previous = previous;
    }

    public E getItem() {
        return item;
    }

    public void setItem(E item) {
        this.item = item;
    }
}

Node클래스를 정의하여 doubleLinkedList에서 사용하도록 구현한다.

• DoubleLinkedList

public class DoubleLinkedList<E>{
    private DNode<E> head;
    private DNode<E> tail;
    int size;

    public void setHead(DNode<E> head) {
        this.head = head;
    }

    public void setTail(DNode<E> tail) {
        this.tail = tail;
    }

    public DNode<E> getHead() {
        return head;
    }

    public DNode<E> getTail() {
        return tail;
    }

    public int getSize() {
        return size;
    }

    public DoubleLinkedList(E newItem) {
        this.head = new DNode<>(newItem,null,null);
        this.tail = head;
        this.size = 0;
    }
}

이중연결 리스트의 head노드와 tail노드에 접근하는 getter, setter를 구현한다. 추가로 size도 정의는 해두었다.

• Deque

public class Deque<E> {
   private DoubleLinkedList<E> list;
   private int size;

   public Deque() {
      list = null;
      size = 0;
   }
   public int size(){
      return size;
   }
   public boolean isEmpty(){
      return size()==0;
   }
   public DoubleLinkedList<E> getList(){
      return list;
   }
   public void insertFront(E newItem){
      if(isEmpty()){
         list = new DoubleLinkedList<>(newItem);
         size++;
         return;
      }
      DNode head = list.getHead();
      DNode newNode = new DNode(newItem,null,head);
      head.setPrevious(newNode);
      list.setHead(newNode);
      size++;
   }
   public void insertLast(E newItem){
      if(isEmpty()){
         list = new DoubleLinkedList<>(newItem);
         size++;
         return;
      }
      DNode tail = list.getTail();
      DNode newNode = new DNode(newItem,tail,null);
      tail.setNext(newNode);
      list.setTail(newNode);
      size++;
   }
   public E deleteFront(){
      if(isEmpty()){
         return null;
      }
      E head = list.getHead().getItem();
      DNode nHead = list.getHead().getNext();
      list.setHead(nHead);
      if(nHead==null){
         list.setTail(null);
      }
      else {
         nHead.setPrevious(null);
      }
      size--;
      return head;
   }
   public E deleteLast(){
      E item = list.getTail().getItem();
      DNode nTail = list.getTail().getPrevious();
      list.setTail(nTail);
      if(nTail==null){
         list.setHead(null);
      }
      else {
         nTail.setNext(null);
      }
      size--;
      return item;
   }
}

과제를 하는 과정에서 핵심적으로 필요한 class인 Deque class를 구현한다.

Deque클래스의 중요 메서드인 insertFront와 insertLast, deleteFront, deleteLast를 순서대로 해보겠다.

public void insertFront(E newItem){
      if(isEmpty()){
         list = new DoubleLinkedList<>(newItem);
         size++;
         return;
      }
      DNode head = list.getHead();
      DNode newNode = new DNode(newItem,null,head);
      head.setPrevious(newNode);//기존 head의 앞에 노드로 지정
      list.setHead(newNode);//새로운 node를 head로 지정
      size++;
   }

먼저 insertFront는 list가 비어있는 경우와 그렇지 않은 경우로 나눌 수 있다.

만약 list가 비어있으면 list를 생성한다.

그렇지 않으면 존재하는 list의 맨 앞부분에 새로운 노드를 집어넣는다.

그러기 위해선 기존 head에서 새로운 노드로 head를 바꾸고 기존 head는 새로운 head의 다음 노드가 된다.

public void insertLast(E newItem){
      if(isEmpty()){
         list = new DoubleLinkedList<>(newItem);
         size++;
         return;
      }
      DNode tail = list.getTail();
      DNode newNode = new DNode(newItem,tail,null);
      tail.setNext(newNode);
      list.setTail(newNode);
      size++;
}

그 다음 마지막에 집어넣는 insertLast는 위의 메서드와 마찬가지로 list가 비어있다면 새로운 list를 만들고, 그렇지 않다면, tail의 다음 노드로 추가하고 tail노드를 새로운 노드로 바꾼다.

public E deleteFront(){
      if(isEmpty()){
         return null;
      }
      E head = list.getHead().getItem();
      DNode nHead = list.getHead().getNext();
      list.setHead(nHead);
      if(nHead==null){
         list.setTail(null);
      }
      else {
         nHead.setPrevious(null);
      }
      size--;
      return head;
   } 

그 다음으로 노드를 삭제하는 deleteFront는 list가 비어있다면 null을 반환하고, 그렇지 않으면 list의 맨 앞인 head의 값을 받아오고, head의 다음 값을 새로운 head로 지정한다. 이때 만약 list에 하나의 요소만 있어서 노드를 지웠을 때, list가 비어있게 된다면 tail 또한 null로 지정한다. 그리고 비어있지 않다면, 기존의 head를 가리키는 부분을 nHead.setPrevious(null)을 사용하여 제거한다.

public E deleteLast(){
      E item = list.getTail().getItem();
      DNode nTail = list.getTail().getPrevious();
      list.setTail(nTail);
      if(nTail==null){
         list.setHead(null);
      }
      else {
         nTail.setNext(null);
      }
      size--;
      return item;
   }

그리고 deleteLast메서드를 구현하면, 위와 유사한 방식으로 tail의 다음 노드를 tail로 지정하고 만약 새로 지정한 tail이 비어있다면 head 또한 null로 지정한다. 그리고 새로 지정한 tail이 비어있지 않다면 기존의 tail과의 연결을 끊어준다.

• LimitedStack

public class LimitedStack<E> {
    private Deque<E> deque;
    int capacity;
    public LimitedStack(int num){
        this.deque = new Deque();
        this.capacity = num;
    }
    public E peek(){
        return (E) deque.getList().getTail().getItem();
    }
    public void push(E newItem){
        if(newItem.equals("U")){
            if(deque.isEmpty()){
                return;
            }
            pop();
        }//입력이 U이면
        else {
            if(deque.isEmpty()){
                deque.insertFront(newItem);
                return;
            }
            else if (deque.size()==capacity) {
                deque.deleteFront();
            }
            deque.insertLast(newItem);
        }//입력이 U가 아니면
    }
    public E pop(){
        return (E) deque.deleteLast();
    }
    public void printAll(){
        DoubleLinkedList<E> list = deque.getList();
        if(list==null){
            System.out.println();
            return;
        }
        DNode<E> pointer = list.getHead();
        while (pointer!=null){
            System.out.print(pointer.getItem()+" ");
            pointer = pointer.getNext();
        }
        System.out.println();
    }
}

이번에는 과제에서 주어진 조건을 수행하기 위한 push, pop 연산을 위한 구현을 하겠다.

public void push(E newItem){
        if(newItem.equals("U")){
            if(deque.isEmpty()){
                return;
            }
            pop();
        }//입력이 U이면
        else {
            if(deque.isEmpty()){
                deque.insertFront(newItem);
                return;
            }
            else if (deque.size()==capacity) {
                deque.deleteFront();
            }
            deque.insertLast(newItem);
        }//입력이 U가 아니면
    }

먼저 U가 입력되는지 다른 것이 입력되는지에 따라 동작이 달라지는 push를 구현했다.

push는 U가 들어왔을 때와 다른 것이 들어왔을 때로 나누고 그 안에서 또 deque가 비었는지 아닌지에 따라서로 또 나누었다.

U가 나왔을 때 deque가 비어있다면 동작없이 메서드를 종료하고, 그게 아니라면 pop연산을 호출한다.

그리고 U가 아닌 것이 들어왔을 때는 deque가 비어있으면 deque에 새로운 요소를 넣고, 만약 capacity만큼 deque가 차있다면 제일 먼저 들어왔던 요소를 제거한 다음 새로운 요소를 집어 넣는다.

public E pop(){
        return (E) deque.deleteLast();
    }

pop는 아주 간단하다. deque에서 요소를 제거하면 된다.

public void printAll(){
        DoubleLinkedList<E> list = deque.getList();
        if(list==null){
            System.out.println();
            return;
        }
        DNode<E> pointer = list.getHead();
        while (pointer!=null){
            System.out.print(pointer.getItem()+" ");
            pointer = pointer.getNext();
        }
        System.out.println();
    }

마지막은 deque의 요소들을 출력하는 메서드를 구현한다.

list가 비어있다면 개행을 출력하여 비어있음을 나타내고, 비어있지 않다면 요소를 출력한다.