[Algorithm] 큐 (Queue) - Kotlin

이번 포스팅에서는 큐(Queue)에 대해 정리해보고 큐의 종류 중 원형 큐를 직접 구현해보려 한다.

 

큐는 컴퓨터의 자료 구조의 한 가지로, FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 쉽게 말하면 배열에서 값을 빼낼 때, 가장 먼저 들어온 값을 우선적으로 뺀다고 생각하면 된다.

 

큐에서 기본적인 용어로는 put 또는 insert (값을 넣는 함수), get 또는 delete(값을 꺼내는 함수)를 의미하며 front의 경우는 데이터를 get 할 수 있는 위치를 뜻하며 rear의 경우 데이터를 배열에 넣을 위치를 뜻한다.

 

원형 큐란?

일반적인 선형 큐는 일반적으로 크기가 제한되어 있으며 만약 빈 공간을 사용하여 제한 사항을 보완하려는 경우 모든 자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있다.

원형 큐는 이러한 선형 큐의 단점을 보완하기 위해 나온 것으로 front가 마지막 배열에 도달 후에는 큐의 맨 앞으로 다시 보내서 빈 공간을 다시 사용하는 방법으로 구현된다.

 

원형 큐를 구현할 때, rear과 front가 size 이상인 경우 0으로 초기화시켜주고 rear로 배열에 들어갈 위치를, front로 배열에서 꺼낼위치를 잡아주면 된다.

 

CircleQueue.kt

import java.util.*

// FIFO => First In First Out 가장 먼저 들어간 수를 가장 먼저 빼는 방법
class CircleQueue(private val size: Int) {

    // 0으로 사이즈만큼 초기화
    private val queueArray = Array<Int?>(size = size){ _ -> null}

    // 객체가 들어갈 위치
    private var rear = 0

    // 객체가 나올 위치
    private var front = 0
    
    fun insert(num: Int){
        if(queueArray[rear] != null){ println("배열이 꽉 찼습니다. delete 명렬어를 통해 데이터를 하나 이상 제거해주세요.") }
        else{
            queueArray[rear++] = num
            if(rear>=size) {
                reset("rear")
            }
        }
    }

    fun delete(): Int? {
        // front 가 size와 값이 같은 경우와 다른 경우를 나눠서 기능을 수행한다.
        val result =
            if(front==size) queueArray[front-1]
            else queueArray[front]
        // result 가 null이 아닌경우에만 초기화 시켜준다.
        if(result != null){
            remove()
        }
        return result
    }

    private fun reset(type: String){
        if(type == "rear"){ rear = 0 }
        else { front = 0 }
    }

    private fun remove(){
        // front 위치의 객체를 null로 초기화
        queueArray[front++] = null
        
        // front가 size 보다 크거나 같은 경우 0으로 초기화
        if(front >= size){
            reset("front")
        }
    }

    fun getStatus(){
        println("rear: ${rear}, front: ${front}, queueArray: ${queueArray.toList()}")
    }
}

fun main(){

    val sc = Scanner(System.`in`)
    print("초기화 할 큐 배열의 크기를 입력>> ")
    val circleQueue = CircleQueue(sc.nextInt())
    while (true){
        print("insert, delete, stop 중 1개 선택>> ")
        when(sc.next()){
            "insert" -> {
                print("배열에 넣을 데이터 입력>> ")
                circleQueue.insert(sc.nextInt())
                circleQueue.getStatus()
            }
            "delete" -> {
                println("출력된 값>> "+ (circleQueue.delete() ?: "배열이 비어있습니다. 데이터를 넣어 주세요."))
                circleQueue.getStatus()
            }
            "stop" -> {
                break;
            }
        }
    }
}

 

 

테스트 결과

 큐 배열의 크기를 입력>> 3
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 100
rear: 1, front: 0, queueArray: [100, null, null]
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 494
rear: 2, front: 0, queueArray: [100, 494, null]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 100
rear: 2, front: 1, queueArray: [null, 494, null]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 494
rear: 2, front: 2, queueArray: [null, null, null]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 배열이 비어있습니다. 데이터를 넣어 주세요.
rear: 2, front: 2, queueArray: [null, null, null]
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 4224
rear: 0, front: 2, queueArray: [null, null, 4224]
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 155
rear: 1, front: 2, queueArray: [155, null, 4224]
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 6696
rear: 2, front: 2, queueArray: [155, 6696, 4224]
insert, delete, stop 중 1개 선택>> insert
배열에 넣을 데이터 입력>> 535
배열이 꽉 찼습니다. delete 명렬어를 통해 데이터를 하나 이상 제거해주세요.
rear: 2, front: 2, queueArray: [155, 6696, 4224]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 4224
rear: 2, front: 0, queueArray: [155, 6696, null]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 155
rear: 2, front: 1, queueArray: [null, 6696, null]
insert, delete, stop 중 1개 선택>> delete
출력된 값>> 6696
rear: 2, front: 2, queueArray: [null, null, null]
insert, delete, stop 중 1개 선택>> stop

Process finished with exit code 0

 

 

참조

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전