큐 Queue

큐란?

영어 단어 큐는 줄을 의미하는 단어이며, 데이터를 이러하게 줄을 서듯이 넣고 빼는 자료구조 방식을 큐라고 한다. 그리고 가장 먼저 들어온 것이 가장먼저 나간다는 선입선출구조를 가진다.(FIFO)

큐의 맨 앞에 있는 원소를 front라 하고, 맨 뒤에 있는 원소를 tail이라고 한다. 큐에서 삽입할 때는 해당 원소를 알려 주어야 하지만 삭제할 때는 단순히 삭제하라고 한다. 무조건 맨 앞에 있는 것을 삭제하기 때문이다.

배열 큐

배열 큐의 객체구조

큐를 위핸 배열과 큐의 맨 앞 원소의 인덱스를 가르키는 front 그리고 맨뒤에 있는 원소의 인덱스를 가리키는 tail이 존재한다. 또한, 큐의 총 원소수를 나타내는 numItems 까지 총 4가지의 필드가 존재한다.

package queue;

public class ArrayQueue<E> implements QueueInterface<E> {
    
    private E queue[];
    private int front, tail, numItems;
    private static final int DEFAULT_CAPACITY = 64;
    private final E ERROR = null; //임의의 에러값

    public ArrayQueue() { // 생성자 1
        queue = (E[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        tail = DEFAULT_CAPACITY - 1;
        numItems = 0;
    }

    public ArrayQueue(int n) { // 생성자 2
        queue = (E[]) new Object[n];
        front = 0;
        tail = n - 1;
        numItems = 0;
    }

    // 큐에 원소 삽입하기
    public void enqueue(E newItem) {
        if (isFull()) { System.out.println("Queue is full!"); } 
        else {
            tail = (tail + 1) % queue.length;
            queue[tail] = newItem;
            numItems++;
        }
    }

    // 큐가 꽉 찼는지 확인하기
    public boolean isFull() {
        return (numItems == queue.length);
    }
    
    // 큐에서 원소 삭제하기
    public E dequeue() {
        if (isEmpty()) return ERROR;
        else {
            E queueFront = queue[front];
            front = (front + 1) % queue.length;
            numItems--;
            return queueFront;
        }
    }
 
    // 큐에서 맨 앞의 원소 알려주기
    public E front() {
        if (isEmpty()) return ERROR;
        else return queue[front];
    }

    // 큐가 비었는지 확인하기
    public boolean isEmpty() {
        return (numItems == 0);
    }

    // 큐 비우기
    public void dequeueAll() {
        queue = (E[]) new Object[queue.length];
        front = 0;
        tail = queue.length - 1;
        numItems = 0;
    }
}

연결 리스트 큐

연결리스트 큐의 객체구조

단방향 원형 연결리스트는 맨 뒤의 노드에 대한 래퍼런스만 있으면 관리할 수 있다. 따라서 연결리스트를 이용하여 설계한 큐 객체는 레퍼런스 tail하나만 있으면 된다.

package queue;
import list.Node;

public class LinkedQueue<E> implements QueueInterface<E> {
    private Node<E> tail;
    private final E ERROR = null; //임의의 에러 값

    public LinkedQueue() {
        tail = null;
    }

    //큐에 원소 삽입하기
    public void enqueue(E newItem) {
        Node<E> newNode = new Node<>(newItem);
        if (isEmpty()) {
            newNode.next = newNode;
            tail = newNode;
        } else {
            newNode.next = tail.next;
            tail.next = newNode;
            tail = newNode;
        }
    }

    //큐에 원소 삭제하기
    public E dequeue() {
        if (isEmpty()) return ERROR;
        else {
            Node<E> front = tail.next;
            if (front == tail)  // only one item in queue
                tail = null;
            else  // more than one Item
                tail.next = front.next;
            return front.item;
        }
    }

    // 큐 맨 앞의 원소 알려주기
    public E front() {
        if (isEmpty()) return ERROR;
        else return tail.next.item; //tail.next: front
    }

    // 큐가 비었는지 확인하기
    public boolean isEmpty() {
        return (tail == null);
    }

    // 큐 깨끗이 비우기
    public void dequeueAll() {
        tail = null;
    }
}