[Backend] 데이터 구조 (Queue)

Queue

package org.example.Queue

class Queue(private val capacity: Int) {
    private var data: Array<Int?> = arrayOfNulls(capacity)
    private var size: Int = 0
    private var front: Int = 0
    private var rear: Int = 0

    fun isFull(): Boolean = size == capacity
    fun isEmpty(): Boolean = size == 0
    fun size(): Int = size

    fun enque(value: Int) {
        if(isFull()) {
            throw IllegalStateException("Queue is full")
        }

        data[rear] = value
        rear = (rear + 1) % capacity
        size++
    }

    fun deque(): Int {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        val element = data[front]!!
        data[front] = null
        front = (front + 1) % capacity
        size--

        return element
    }

    fun getFront(): Int {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        return data[front]!!
    }

    fun getRear(): Int {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        return data[rear]!!
    }

    fun clear() {
        for (i in 0 until size) {
            data[i] = null
        }

        front = 0
        rear = 0
        size = 0
        this.data = arrayOfNulls(capacity)
    }
}

 

결과

fun main() {
    val queue = Queue(10)

    println("1. Data insertion")
    println("Initial size : ${queue.size()}")
    for (i in 0..9) {
        queue.enque(i)
    }
    println("First element : ${queue.getFront()}, Last element : ${queue.getRear()}")
    println("Updated size : ${queue.size()}")

    println("\n2. Data removal")
    println("Removed Element : ${queue.deque()}")
    println("Decreased size : ${queue.size()}")

    println("\n3. Check queue is full")
    try {
        queue.enque(10)
        queue.enque(11)
    } catch (_: IllegalStateException) {
        println("Error check : Queue is full")
    }

    println("\n4. Check queue is empty")
    try {
        queue.clear()
        queue.deque()
    } catch (_: NoSuchElementException) {
        println("Error check : Queue is empty")
    }
}

/*
1. Data insertion
Initial size : 0
First element : 0, Last element : 0
Updated size : 10

2. Data removal
Removed Element : 0
Decreased size : 9

3. Check queue is full
Error check : Queue is full

4. Check queue is empty
Error check : Queue is empty
*/

---

Queue (in Generic<T>)

package org.example.Queue

class GenericQueue<T>(private val capacity: Int) {
    @Suppress("Unchecked_cast")
    private var data: Array<T?> = arrayOfNulls<Any?>(capacity) as Array<T?>
    private var size: Int = 0
    private var front: Int = 0
    private var rear: Int = 0

    fun isFull(): Boolean = size == capacity
    fun isEmpty(): Boolean = size == 0
    fun size(): Int = size

    fun enque(value: T) {
        if(isFull()) {
            throw IllegalStateException("Queue is full")
        }

        data[rear] = value
        rear = (rear + 1) % capacity
        size++
    }

    fun deque(): T {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        val element = data[front]!!
        data[front] = null
        front = (front + 1) % capacity
        size--

        return element
    }

    fun getFront(): T {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        return data[front]!!
    }

    fun getRear(): T {
        if(isEmpty()) {
            throw NoSuchElementException("Queue is empty")
        }

        return data[rear]!!
    }

    fun clear() {
        for (i in 0 until size) {
            data[i] = null
        }

        front = 0
        rear = 0
        size = 0
        this.data = arrayOfNulls(capacity)
    }
}

 

---

참고 자료

 - Queue Data Structure - GeeksforGeeks