[Data Structure] 큐

Queue는 한쪽 끝(rear)에서는 enqueue, 또 다른 끝(front)에서는 dequeue 연산을 하는 유한 순서리스트이다.
Queue는 FIFO(First in First out) 리스트이다.

Queue ADT

ADT Queue 데이타:0개 이상의 원소를 가진 유한 순서 리스트 연산: queue ∈ Queue;
item ∈ Element;
createQ() ::= create an empty queue;

enqueue(queue, item) ::= insert item at the rear of queue;

isEmpty(queue) ::= if (queue is empty) then return true else return false;

dequeue(queue) ::= if (isEmpty(queue)) then return error else {
    delete and return the front item of queue
};

delete(queue) ::= if (isEmpty(queue)) then return error else {
    delete the front item of queue
};

peek(queue) ::= if (isEmpty(queue)) then return error else {
    return the front item of queue
};
End Queue

front는 dequeue할 위치를 기록하고 rear은 enqueue할 위치를 기록한다.

Queue 클래스

front와 rear는 -1로 초기화 시킨다.

public class Queue {
    private Object[] q;
    private int front,rear;
    private int n = 10;
    public Queue() {
        q = new Object[n];
        front = rear = -1;
    }

    // methods

isEmpty 연산자

front와 rear가 같으면 큐는 비었다는 의미와 같다.

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

enque 연산자

rear는 입력할 데이터의 인덱스를 가리키기에 큐의 마지막 인덱스라면 더이상 원소를 집어넣을 수 없기에 에러를 발생시킨다. 그렇지 않다면 그 다음 인덱스에 원소를 넣는다.

public void enque(Object item) {
    if (rear == n - 1) 
        throw new QueueFullException(); // 런타임에러
    rear += 1;
    q[rear] = item;
}

deque 연산자

큐가 비었다면(rear == front) 빼낼 원소가 없기에 에러를 발생시키고 deque할 원소를 기록할 front를 1 더해준다.

public Object deque() {
    if(isEmpty())
        throw new QueueEmptyException(); // 런타임에러
    front += 1;
    return q[front];
}

peek, delete 연산

deque 연산과 비슷한 방식이다.
peek: front가 가리키는 원소를 리턴한다.
delete: front가 가리키는 원소를 삭제한다.(front + 1)

public Object peek() {
    if (isEmpty()) throw new QueueEmptyException();
    return q [front + 1];
}

public void delete() {
    if (isEmpty()) 
        throw new QueueEmptyException();
    front += 1;
}

순차표현의 문제점: 크기가 8인 배열에서 rear = 7, front = 3일때 0,1,2 인덱스는 비었지만 사용하지 못한다.

순차표현의 문제를 해결하기 위해 원형 큐 고안
rear를 하나 증가시켰을 때 rear = front 라면 가득찼다는 의미와 같다.

n = queue.length;
rear = (rear + 1) % n;
front = (front + 1) % n;

원형큐의 deque, enque

public class CircularQueue {
    private static final int SIZE = 10;
    private Object[] q = new Object[SIZE];
    private int rear = 0;
    private int front = 0;

    public void enqueu(Object item) {
        rear = (rear + 1) % SIZE;
        if (front == rear) 
            throw new QueueFull();
        q[rear] = item;
    }

    public Object dequeue() {
        if (front == rear) 
            throw new QueueEmpty();
        front = (front + 1) % SIZE;
        return q[front];
    }
}

원형 큐는 순차표현 큐에 비해 빈공간을 남기지 않아 메모리 공간을 잘 활용하지만 배열로 구현되기에 큐의 크기는 제한된다는 단점이 있다.

한정된 크기를 개선하기 위해 연결리스트 큐 고안.

리스트 노드의 구조

public class ListNode {
Object data;
ListNode Link;
}

리스트큐 구현

연결리스트 표현으로 바뀌었지만 내부 동작은 순차표현 큐와 비슷하다.

public class ListQueue implements Queue {
    private ListNode front; // 큐에서의 front 원소
    private ListNode rear; // 큐에서의 rear 원소
    private int count; // 큐의 원소 수

    /** 공백 큐를 생성 */
    public ListQueue() {
        front = null;
        rear = null;
        count = 0;
    }
    public boolean isEmpty() {
        return (count == 0);
    }

    /** 큐에 원소 x 를 삽입 */
    public void enqueue(Object x) {
        ListNode newNode = new ListNode();
        newNode.data = x;
        newNode.link = null;
        if (count == 0) { // 큐(리스트)가 공백인 경우 front = rear = newNode;
        } 
        else {
            rear.link = newNode;
            rear = newNode;
        }
        count++;
    }

    /** 큐에서 원소를 삭제하고 반환 */
    public Object dequeue() {
        if (count == 0) 
            return null;
        Object item = front.data;
        front = front.link;
        if (front == null) { // 리스트의 노드를 삭제 후 공백이 된 경우
            rear = null;
        }
        count--;
        return item;
    }
    21
    /** 큐에서 원소를 삭제 */
    public void delete() {
        if (count == 0) 
            return null;
        front = front.link;
        if (front == null) { // 리스트의 노드를 삭제 후 공백이 된 경우
            rear = null;
        }
        count--;
    }
    public Object peek() {
        return (count == 0) ? null : front.data;
    }
}

참고자료

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Data%20Structure/Stack%20%26%20Queue.md

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖