[자료구조] 큐 (Queue) 구현 (JAVA)

큐란 선입선출(FIFO) 구조를 갖는 자료구조이다. 큐에 대한 자세한 설명은 전 포스팅을 참고하기 바란다.

2024.06.15 - [CS/자료구조] - [자료구조] 큐 (Queue)

[자료구조] 큐 (Queue)

 

큐 구현 방법

---

큐를 구현하는 것은 크게 두 가지 방법이 있다.

• 배열(Array) 기반 큐: 고정 크기의 배열을 사용하여 큐를 구현한다. 간단하지만 큐의 크기가 고정되어 있다는 단점이 있는 방법이다.
• 연결 리스트(Linked-List) 기반 큐: 동적으로 크기를 변경할 수 있는 연결 리스트를 사용하여 큐를 구현한다. 메모리 효율적이며 크기 제한이 없는 방법이다.

 

배열(Array) 기반 큐 구현 (JAVA)

---

public class ArrayQueue {
    private int front;
    private int rear;
    private int capacity;
    private Object queue[];

    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.front = this.rear = -1;
        this.queue = new Object[capacity];
    }

    public void enqueue(Object data) {
        if (isFull()) {
            System.out.println("Queue is full");
            return;
        }
        if (isEmpty()) {
            front = 0;
        }
        queue[++rear] = data;
    }

    public Object dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }
        Object data = queue[front];
        queue[front] = null;
        if (front == rear) {
            front = rear = -1;
        } else {
            front++;
        }
        return data;
    }

    public Object front() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }
        return queue[front];
    }

    public Object rear() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return null;
        }
        return queue[rear];
    }

    public boolean isEmpty() {
        return front == -1;
    }

    public boolean isFull() {
        return rear == capacity - 1;
    }
    public static void main(String[] args) throws Exception {
    }
}

ArrayQueue 클래스: 큐를 구성하는 데 필요한 멤버변수와 enqueue 메소드, dequeue 메소드, front 메소드, rear 메소드, isEmpty 메소드, isFull 메소드로 구성되어 있다.

public static void main(String[] args) throws Exception {
        ArrayQueue queue = new ArrayQueue(5);
        queue.dequeue(); // Queue is empty
        queue.front(); // Queue is empty
        queue.rear(); // Queue is empty

        queue.enqueue(1);
        queue.enqueue("2");
        queue.enqueue(3);
        System.out.println(queue.front()); // 1
        queue.enqueue("4");
        queue.enqueue(5);
        System.out.println(queue.rear()); // 5

        queue.enqueue("full queue"); // Queue is full

        System.out.println(queue.dequeue()); // 1
        System.out.println(queue.dequeue()); // 2
        System.out.println(queue.dequeue()); // 3
        System.out.println(queue.dequeue()); // 4
        System.out.println(queue.dequeue()); // 5

        queue.dequeue(); // Queue is empty
    }

메인함수는 큐를 테스트 및 이해하기 위해 크기 5의 큐를 만들고 큐의 주요 연산을 수행하는 코드이다. 큐가 제대로 구성되어 있다면 주석과 같이 출력이 나올 것이다.

Queue is empty
Queue is empty
Queue is empty
1
5
Queue is full
1
2
3
4
5
Queue is empty

예상과 같은 출력값이 나왔다. 큐는 선입선출 구조이므로 먼저 들어간 데이터인 1부터 나오는 것을 볼 수 있다.

 

연결리스트 (Linked-List) 기반 큐 구현

---

class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

노드 클래스

import java.util.NoSuchElementException;

public class LinkedListQueue<T> {
    private Node<T> front;
    private Node<T> rear;
    private int size;

    public LinkedListQueue() {
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    public void enqueue(T data) {
        Node<T> newNode = new Node<>(data);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        T data = front.data;
        front = front.next;
        size--;
        if (isEmpty()) {
            rear = null;
        }
        return data;
    }

    public T front() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return front.data;
    }

    public T rear() {
        if (isEmpty()) {
            throw new NoSuchElementException("Queue is empty");
        }
        return rear.data;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        
        System.out.println(queue.front()); // 1
        System.out.println(queue.rear()); // 3

        System.out.println(queue.dequeue()); // 1
        System.out.println(queue.dequeue()); // 2
        System.out.println(queue.dequeue()); // 3
    }
}

LinkedListQueue 클래스 및 메인 함수. 실행 결과는 다음과 같다.

1
3
1
2
3

예상했던 것과 같은 출력값이 나온다. 큐의 기능에 맞게 잘 실행되는 것을 알 수 있다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!