[자료구조] 큐 Queue

큐(Queue)는 줄(line)이라는 의미를 가지고 있다.

먼저 들어간 데이터가 가장 먼저 출력되는, 선입선출(FIFO - First In First Out) 형태의 자료구조이다.

 

가장 오래전에 입력된 데이터(나갈 차례가 가장 빠른, 데이터 삭제) : front

가장 최근에 입력된 데이터(이제 들어온, 들어오는 곳, 데이터 삽입) : rear

 -> 따라서 큐를 구현하기 위해서는 front와 rear를 관리하는 배열을 이용하거나, front노드와 rear노드를 관리하는 연결 리스트를 이용할         수 있다.   

 

큐의 동작

insert(삽입), remove(추출, 삭제), peek(읽기)

 

1) 삽입 - insert

 새로운 데이터의 삽입은 리스트의 끝 부분을 가리키는 rear에서 발생하며, 데이터가 삽입 될 때 하나 증가시킨 후 새로운 데이터를 삽입하도록 구현한다.

 

2) 삭제 - remove

 큐에서 데이터를 제거하는 작업으로 항상 front에서 발생한다.

 front가 가리키고 있는 데이터를 꺼낸 후, front 값을 하나 증가 시키도록 구현한다.

front값이 rear를 추월하게 되면 더 이상 제거할 데이터가 없는 상태 즉, 자료가 하나도 없는 빈 큐임을 의미한다.

 

3) 읽기 - peek

 큐에서 front가 가리키는 데이터를 읽는 작업을 peek라고 하며, 데이터를 제거하지 않고 읽는 작업만 수행하므로 front 값을 변경시키지 않는다.

 

 

배열을 이용한 큐 구현

package data_structure;

// 배열을 이용한 큐 구현
public class ArrayQueue {
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;

    //생성자
    public ArrayQueue(int maxSize){
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }

    //메서드, insert, remove, peek, empty, full

    //empty
    //비어있다면, front > rear
    public boolean empty(){
        return (front == rear+1);
    }

    //full
    //배열의 마지막 인덱스와 rear이 같을 때
    public boolean full(){
        return (rear == maxSize-1);
    }

    //큐 rear에 데이터 등록
    
    public void insert(Object item){
        if(full()) throw new ArrayIndexOutOfBoundsException();

        queueArray[++rear] = item;

    }

    //큐에서 front데이터 조회
    public Object peek(){

        if(empty()) throw new ArrayIndexOutOfBoundsException();

        return queueArray[front];
    }

    //큐에서 front 데이터 제거
    public Object remove(){
        Object item = peek();

        front++;

        return item;
    }


    public static void main(String[] args) {
        ArrayQueue arrayQ = new ArrayQueue(5);
        arrayQ.insert("A");
        arrayQ.insert("B");
        arrayQ.insert("C");
        arrayQ.insert("D");
        arrayQ.insert("E");


        System.out.println(arrayQ.peek());
        arrayQ.remove();
        System.out.println(arrayQ.peek());
    }
}

 

연결 리스트를 이용한 큐 구현

데이터가 저장될 큐의 크기를 미리 지정하지 않아도 되며 배열처럼 front보다 작은 인덱스 공간(삭제한 공간)을 낭비하지 않아도 된다는 장점을 가지고 있다.

 

package data_structure;

public class ListQueue {

    private class Node{
        //노드는 data와 다음 노드를 가진다.
        private Object data;
        private Node nextNode;

        Node(Object data){
            this.data = data;
            this.nextNode = null;
        }
    }

    private Node front;
    private Node rear;

    //생성자
    public ListQueue(){
        this.front = null;
        this.rear = null;
    }

    public boolean empty(){
        return (front==null);
    }

    //item을 큐의 rear에 넣는다.
    public void insert(Object item){
        Node node = new Node(item);
        node.nextNode = null;

        //큐가 비어있으면 첫번째 노드는 front이면서 rear이다.
        if(empty()){
            rear = node;
            front = node;
        }else {
            //맨 끝 노드인 rear의 다음 노드에 삽입할 노드를 넣는다.
            rear.nextNode = node;
            rear = node;
        }
    }

    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return front.data;
    }

    public Object remove(){
        //현재 꺼낼 노드르 읽어온다.
        Object item = peek();
        //front 다음 노드를 front에 넣는다.
        front = front.nextNode;

		//마지막 노드 였을 경우 큐에 더이상 데이터가 없으므로 rear 값도 초기화 시킨다.
        if(front == null){
            rear = null;
        }

        return item;
    }

    public static void main(String[] args) {

    }
}

 

 

자바에서 큐사용

java.util에 있음.

Queue<제너릭> q = new LinkedList<>();