자료구조

[자료구조] 큐(Queue)

JunsuKim 2023. 9. 30.

728x90

큐(Queue)

큐는 양 끝이 뚫린 파이프를 생각하면 된다.

한 쪽으로 데이터를 계속 해서 추가할 때, 다른 한 쪽으로 데이터를 빼내려 한다면 제일 처음 넣은 값부터 차례대로 나오게 된다.

즉, 처음 넣은 값이 처음 나오게 되는 First Input First Output(FIFO) 원리를 갖는다.

구현

큐의 기능은 다음과 같다.

push: 큐에 데이터를 넣는다.
pop 또는 poll: 큐에서 가장 앞에 있는 데이터를 빼고 반환한다.
size: 큐에 들어있는 데이터의 갯수를 반환한다.
isEmpty: 큐가 비어있는지를 반환한다.
front 또는 peek: 큐의 가장 앞에 있는 원소를 반환한다.
back: 큐의 맨 뒤에 있는 값을 반환해준다. 자바에는 존재하지 않는 내장함수로, c++에 존재한다.

class Queue {
    companion object {
        const val MAX = 10000
    }

    private val arr = IntArray(MAX)
    private var front = 0
    private var rear = 0

    fun push(data: Int) {
        if(rear == MAX) println("Queue is full")
        else arr[rear++] = data
    }

    fun pop(): Int {
        return if(isEmpty()) -1
        else arr[front++]
    }

    fun size(): Int = rear - front

    fun isEmpty(): Boolean = front == rear

    fun peek(): Int {
        return if(isEmpty()) -1
        else arr[front]
    }

    fun back(): Int {
        return if(isEmpty()) -1
        else arr[rear - 1]
    }
}

큐는 스택과 달리 한 쪽으로 추가/삭제를 하는 것이 아니라, 한 쪽끝에서 데이터를 추가, 다른 끝에서 데이터를 뽑아내므로 앞, 뒤를 나타낼 변수 2개가 필요하다.

나는 구현에서 front와 rear이라는 변수를 선언하였다.

push

큐에 데이터를 추가하는 함수이다. 데이터가 들어가게 되며 rear의 값을 증가시켜준다.

만약 rear이 MAX와 같다면 큐가 꽉 찼다는 의미이므로 따로 처리를 해준다.

pop

큐에서 맨 앞에 있는 데이터를 빼낸 후 반환하는 함수이다.

즉, 배열의 front 인덱스의 값을 반환시킨 후, front를 증가시켜주면 된다.

size

큐에 들어있는 데이터의 갯수를 반환한다.

즉, rear에서 front를 뺀 값을 반환하면 된다.

isEmpty

큐가 비어있는지 확인하는 함수이다.

front와 rear가 같다면, 큐가 빈 것이 된다.

peek

큐의 맨 앞에 있는 데이터를 반환하는 함수이다.

즉, front 인덱스를 반환해주면 된다.

back

큐의 맨 뒤에 있는 데이터를 반환하는 함수이다.

push를 할 때마다 rear++로 rear의 값을 뒤로 이동시키므로

마지막 값을 확인하기 위해서는 rear - 1의 인덱스를 반환하면 된다.

여기까지 확인해봤을 때 front랑 rear는 계속해서 증가하기만 하고, 줄어들지 않는 것을 확인할 수 있다.

즉, 계속 push, pop을 반복하다 보면 큐가 꽉 차지 않았는데도 불구하고 꽉 찼다는 문구가 나오게 될 수 있다는 것이다.

여기서 잠깐 자바, 코틀린의 큐 사용법을 보면 다음과 같다.

import java.util.*

fun main() {
    val que: Queue<Int> = LinkedList()
}

Queue는 인터페이스로만 되어있고, LinkedList를 이용해서 생성하게 된다.

LinkedList를 통해 큐를 구현하게 되는 경우, 크기를 따로 지정해주지 않아도 되며, 원하는 대로 재정의가 가능하다는 장점이 있다.

Queue 인터페이스를 상속받아 재정의를 하며 구현해보기 위해 기본 틀을 잡아보면 다음과 같다.

class Que<T>: Queue<T> {
    override fun add(element: T?): Boolean {
        TODO("Not yet implemented")
    }

    override val size: Int
        get() = TODO("Not yet implemented")

    override fun addAll(elements: Collection<T>): Boolean {
        TODO("Not yet implemented")
    }

    override fun clear() {
        TODO("Not yet implemented")
    }

    override fun iterator(): MutableIterator<T> {
        TODO("Not yet implemented")
    }

    override fun remove(): T {
        TODO("Not yet implemented")
    }

    override fun contains(element: T?): Boolean {
        TODO("Not yet implemented")
    }

    override fun containsAll(elements: Collection<T>): Boolean {
        TODO("Not yet implemented")
    }

    override fun isEmpty(): Boolean {
        TODO("Not yet implemented")
    }

    override fun remove(element: T?): Boolean {
        TODO("Not yet implemented")
    }

    override fun removeAll(elements: Collection<T>): Boolean {
        TODO("Not yet implemented")
    }

    override fun retainAll(elements: Collection<T>): Boolean {
        TODO("Not yet implemented")
    }

    override fun offer(e: T?): Boolean {
        TODO("Not yet implemented")
    }

    override fun poll(): T {
        TODO("Not yet implemented")
    }

    override fun element(): T {
        TODO("Not yet implemented")
    }

    override fun peek(): T {
        TODO("Not yet implemented")
    }
}

각 구현은 LinkedList 포스팅을 참고해서 각 기능을 구현하면 된다.