[백엔드 과정][자바 기초] - 큐 구현하기 (3.DoubleLinkedList를 이용한 구현)

---

• FIFO(First-In-First-Out)으로 먼저 저장한 데이터가 먼저 나오는 구조를 가집니다.(선입선출)
• 즉, 저장된 데이터중 가장 앞에 있는 데이터만 접근 가능함을 나타냅니다.
• 음식점에서 주문을 위해 줄을 서고, 가장 앞에서부터 주문함으로 예로 들 수 있습니다.

---

DoubleLinkedList

• A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.

📌출처: https://www.geeksforgeeks.org/doubly-linked-list/

---

[Queue Interface]

package arrays;

public interface Queue {
    public boolean isEmpty();
    public void add(Integer element);
    public Integer element();
    public Integer remove();
    public int size();

}

Basic Operations on Queue: 

• enqueue(): Inserts an element at the end of the queue i.e. at the rear end.(끝에 요소 추가)
• dequeue(): This operation removes and returns an element that is at the front end of the queue. (맨 앞에 요소를 삭제하고 돌려준다.)
• front(): This operation returns the element at the front end without removing it.(삭제 없이 맨 앞 요소를 돌려줌)
• rear(): This operation returns the element at the rear end without removing it.(삭제 없이 맨 뒤 요소를 돌려줌)
• Empty(): This operation indicates whether the queue is empty or not.(queue가 비어있는지 확인 메소드)
• size(): This operation returns the size of the queue i.e. the total number of elements it contains.  

📌출처: https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/

---

[DoubleLinkedList로 구현한 Queue]

package arrays;


import java.util.NoSuchElementException;

public class DoubleLinkedQueue implements Queue{


    static class LinkedNode{
        Integer data;
        LinkedNode pre;
        LinkedNode next;

        public LinkedNode() {
            this.data = 0;
            this.pre = this;
            this.next = this;
        }

        public LinkedNode(Integer data, LinkedNode pre, LinkedNode next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }

        public Integer getData() {
            return data;
        }

        public LinkedNode getPre() {
            return pre;
        }

        public LinkedNode getNext() {
            return next;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public void setPre(LinkedNode pre) {
            this.pre = pre;
        }

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

    LinkedNode head;
    int cnt;

    public DoubleLinkedQueue() {
        this.head = new LinkedNode();
        this.cnt = 0;
    }

    @Override
    public boolean isEmpty() {
        //초기화를 head 자신으로 두었기에 head 자신이 next로 오면 doubleLinkedQueue가 비었다고 할 수 있다.
        return this.head.getNext() == this.head;
    }

    @Override
    public void add(Integer element) {
        LinkedNode newNode = new LinkedNode(element,this.head.getPre(),this.head);
        this.head.getPre().setNext(newNode);
        this.head.setPre(newNode);
        this.cnt++;
    }

    @Override
    public Integer element() {

        if(this.isEmpty()) {
            throw new NoSuchElementException();
        }
        return this.head.getNext().getData();
    }

    @Override
    public Integer remove() {
        if(this.isEmpty()) {
            throw new NoSuchElementException();
        }

        LinkedNode target = this.head.getNext();
        Integer data = target.getData();

        target.getPre().setNext(target.getNext());
        target.getNext().setPre(target.getPre());
        this.cnt--;
        return element();
    }

    @Override
    public int size() {
        return this.cnt;
    }
    @Override
    public String toString() {
        StringBuilder line = new StringBuilder();
        LinkedNode node = this.head.getNext();
        while(node != this.head) {
            line.append((line.length() != 0?" ":"") + node.getData());
            node = node.getNext();
        }

        return	line.toString();
    }
}