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

---

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

---

LinkedList

 

• A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations.(linked list는 선형데이터 구조로 연속적 공간에 값을 저장하지 않는다.)
• The elements in a linked list are linked using pointers as shown in the below image

---

[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/

---

[LinkedList로 구현한 Queue]

package arrays;

import java.util.NoSuchElementException;

public class LinkedListQueue implements Queue{
    static class LinkedNode{
        Integer data;
        LinkedNode next;


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

        public Integer getData() {
            return data;
        }

        public LinkedNode getNext() {
            return next;
        }

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

    LinkedNode head;
    LinkedNode tail;
    int cnt;

    @Override
    public boolean isEmpty() {
        return this.cnt == 0;
    }

    @Override
    public void add(Integer element) {

        if(this.isEmpty()){
            /** LinkedList로 구현하는 큐에 처음으로 요소를 삽입할 경우
             * 1. head 설정 : 입력받은 element를 data로 넣고 다음 값엔 Null처리를 해준다.
             * 2. tail 설정: 이때까진 요소가 하나라 head와 tail이 동일하다.**/
            this.head = new LinkedNode(element, null);
            this.tail = this.head;
        } else{
            //node가 기존에 있을 경우엔 tail 뒤에 붙이고 새로운 노드를 tail로 한다.
            this.tail.setNext(new LinkedNode(element, null));
            this.tail = this.tail.getNext();
        }
        this.cnt ++; //큐에 데이터가 들어와 그만큼 사이즈가 늘어남.
    }


    @Override
    public Integer element() {
        if(this.isEmpty()){
            throw new NoSuchElementException();
        }
        return this.head.getData();
    }

    @Override
    public Integer remove() {
        if(this.isEmpty()){
            throw new NoSuchElementException();
        }
        Integer value = this.head.getData();
        if(this.cnt == 1){
            this.head = null;
            this.tail = null;
        } else {
            //삭제하고 돌려줄 때 큐에 요소가 1개보다 많다면 다음 노드를 head로 설정
            this.head = this.head.getNext();
        }
        this.cnt--;
        return value;
    }

    @Override
    public int size() {
        return this.cnt;
    }

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

• LinkedList를 사용할 땐 ArrayList와 달리 사이즈를 구할 방법이 없기 때문에 따로 변수를 설정해 값을 구해주는 것이 편리하다.