Queue

매번 철자가 헷갈리는 Queue .. 

 

개념

먼저 집어 넣은 데이터가 먼저 나오는 선입선출(First In First Out)구조로 저장하는 방식

데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용됨

외국에서 사람들이 버스 정류장에 선 줄을 Queue라고 하는데 먼저 선 사람들이 한명씩 버스에 타는 걸 상상하면 스택이랑 헷갈리지 않을 것이다. (스택은 그릇쌓기)

Java에서 LinkedList를 이용해 구현 할 수 있다.

 

큐의 용어

put	큐에 자료를 넣는 것
get	큐에서 자료를 꺼내는 것
front	데이터를 get할 수 있는 위치
rear	데이터를 put할 수 있는 위치
peek	front 데이터 반환
poll	front 데이터 삭제 및 반환
Overflow	큐가 꽉 차서 자료를 넣을 수 없는 경우
Underflow	큐가 비어있어 자료를 꺼낼 수 없는 경우

 

큐의 종류

선형 큐	막대 모양의 큐
환형 큐	데이터 공간이 있어도 오버플로우가 발생하는 선형 큐의 문제점을  보완 front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 해결

 

 

리스트로 구현한 큐

public class Queue {
    public static void main(String[] args) {

        int size=3;
        ListQueue listQueue=new ListQueue(size);

        listQueue.enqueue("A");
        listQueue.print();

        listQueue.enqueue("B");
        listQueue.print();

        listQueue.peek();
        listQueue.print();

        listQueue.enqueue("C");
        listQueue.print();

        listQueue.enqueue("D");
        listQueue.print();

        listQueue.dequeue();
        listQueue.print();

        listQueue.clear();
        listQueue.print();

        listQueue.clear();

        listQueue.dequeue();
        listQueue.print();

    }
}
class Node{
    private String data;
    public Node link;

    public Node(String data) {
        this.data = data;
        this.link = null;
    }
    public Node(String data, Node link) {
        this.data = data;
        this.link = link;
    }

    public String getData() {
        return this.data;
    }
}

class ListQueue{
    private Node head;
    private Node front;
    private Node rear;
    private int size;

    public ListQueue(int size){
        head=null;
        front=null;
        rear=null;
        this.size=size;
    }

    public boolean isEmpty(){
        return (front ==null && rear==null);
    }

    public boolean isFull(){
        if(isEmpty()) return false;
        else{
            int nodeCnt=0;
            Node tmpNode=head;

            while (tmpNode.link!=null){
                nodeCnt++;
                tmpNode=tmpNode.link;
            }
            return (this.size -1==nodeCnt);
        }
    }
//입력
    public void enqueue(String data){
        Node newNode=new Node(data);

        if(isFull()){
            System.out.println("Queue is full");
            return;
        }else if(isEmpty()){
            this.head=newNode;
            this.front=this.head;
            this.rear=this.head;
        }else{
            rear.link=newNode;
            rear=newNode;
        }

    }

    //출력

    public void dequeue(){
        Node tmpNode;
        if(isEmpty()){
            System.out.println("Queue is empty");
            return;
        }

        if(front.link==null){
            head=null;
            front=null;
            rear=null;
        }else{
            tmpNode=front.link;
            head=tmpNode;
            front.link=null;
            front=head;
        }
    }

    public void peek(){
        if(isEmpty()){
            System.out.println("Queue is empty");
            return;
        }
        else{
            System.out.println(front.getData());
        }
    }
    public void clear(){
        if(isEmpty()){
            System.out.println("already empty");
            return;
        }else{
            head=null;
            front=null;
            rear=null;
        }
    }

    public void print(){
        if(isEmpty()){
            System.out.println("empty");
            return;
        }else{
            Node tmpNode=this.front;
            while (tmpNode !=null){
                System.out.print(tmpNode.getData()+" ");
                tmpNode=tmpNode.link;
            }
            System.out.println();
        }
    }
}