Queue

Queue

한 쪽 끝에서는 원소를 넣고 반대쪽 끝에서는 원소를 뺄 수 있는 자료구조

First In First Out 구조다

 

초기화

index
3
2
1
0	head, tail

 

push 12

index
3
2
1	tail
0	12 head

pop 

index
3
2	tail
1	13
0	12 head

index
3
2	tail
1	13 head
0

 

동작에 따른 시간 복잡도

• 원소 추가 / 제거 O(1)
• 제일 앞/뒤 원소 확인 O(1)

양끝이 아닌 나머지 원소들의 확인 / 변경은 원칙적으로 불가능하다

구현

배열, 연결리스트로 구현이 가능하다 

[구성] 

• 원소들을 담을 배열 
• 제일 앞쪽 인덱스 값
• 제일 뒤쪽 인덱스 값(다음 원소가 삽입될 위치)

[성질] 

• 원소가 들어 있는 위치 : data[tail - 1] ~ data[head]
• 실제 큐의 크기 : tail - head

push  

data[tail++] = x

 

pop : 빈 큐에서 호출 금지

head++

 

front : 빈 큐에서 호출 금지

data[head]

 

back : 빈 큐에서 호출 금지

data[tail - 1]

 

배열로 구현 시 push,pop 동작을 반복하면 head와 tail의 증가로 조금씩 뒤로 밀려 결국에는 앞에 사용하지 않는 공간이 생기게 된다

이를 해결하기 위해 배열을 원형 구조를 가지도록 만들어 준 것이 원형큐이다

 

코테에서는 입출력 수가 정해져 있기 때문에 큐의 크기를 push 수보다 크게 만들면 문제 없다

BOJ

10845 . 큐

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()
    val queue = Q(n+1)
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    for (i in 1..n) {
        val tokenizer = StringTokenizer(readLine())
        when (tokenizer.nextToken()) {
            "push" -> {
                queue.push(tokenizer.nextToken().toInt())
            }
            "pop" -> {
                bw.write("${queue.pop()}\n")
            }
            "size" -> {
                bw.write("${queue.size()}\n")
            }
            "empty" -> {
                bw.write("${queue.empty()}\n")
            }
            "front" -> {
                bw.write("${queue.front()}\n")
            }
            "back" -> {
                bw.write("${queue.back()}\n")
            }
        }
    }

    bw.close()
}

class Q (private val size: Int) {
    private val data = Array<Int?>(size) { null }
    private var head = 0
    private var tail = 0

    fun push(x: Int) {
        data[tail++] = x
    }

    fun pop(): Int {
        return if (tail - head == 0) -1
        else data[head++]!!
    }

    fun size(): Int {
        return tail - head
    }

    fun empty(): Int {
        return if (tail - head == 0) 1 else 0
    }

    fun front(): Int {
        return if (tail - head == 0) -1
        else data[head]!!
    }

    fun back(): Int {
        return if (tail - head == 0) -1
        else data[tail-1]!!
    }
}

kotlin 에서의 Queue

코틀린에서는 스택과 마찬가지로 큐를 제공하지 않기 때문에 java.improt.Queue를 사용하거나 ArrayDeque이라는 덱 컬렉션을 사용한다

참고

https://youtu.be/D_fwSy5tRAY