/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[백준] 18258번 - 큐2 : https://www.acmicpc.net/problem/18258
1. 큐(Queue)란?
큐는 스택과는 반대로 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나오는 자료구조(First In First Out / 선입 선출)이다. 이는 우리가 먼저 온 차례대로 줄을 세우는 것과 같다.
큐는 작업을 처리하는 요소에 부하를 주지 않으면서도 처리 능력을 넘어서는 작업들을 놓치지 않고 수용할 수 있게 한다. 이러한 특성으로 큐는 '완충장치(대기열)'로 사용되는 경우가 많다.
큐의 기능
스택과 마찬가지로 큐의 주요 기능도 삽입(Enqueue), 제거(Dequeue)이다. 둘의 차이점은 스택의 제거와는 다르게 큐는 맨 앞(처음)에 있는 데이터를 삭제한다. 스택에서는 삽입(push) / 제거(pop) 이라고 칭하고, 큐에서는 삽입(dequeue) / 제거(enqueue)라 한다.
2. 큐(Queue) 구현 (백준 18258번)
이번에도 백준 18258번 - 큐2 문제를 풀어보면서 큐를 구현해보겠다. 문제는 다음과 같다. (스택 문제와 유사)
문제
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여섯 가지이다.
- push X: 정수 X를 큐에 넣는 연산이다.
- pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- size: 큐에 들어있는 정수의 개수를 출력한다.
- empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
- front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
- back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
입력
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
순환 큐 구현하기 (배열을 이용한 큐)
기본적으로 배열의 앞 부분에 데이터를 추가하는 작업은 모든 데이터를 한 칸씩 밀어내고 빈 앞 자리에 데이터를 추가하는 방식이다. 이는 O(N)의 시간복잡도를 가진다.
이를 해결하기 위해 '순환 배열'을 만들어보자. 링크드 리스트를 headNode 와 lastNode 를 이용해 만든 것과 비슷한 원리이다. 첫 번째 데이터와 마지막 데이터에 바로 접근 할 수 있으므로 O(1)의 시간복잡도를 가진다.
예시인 크기가 10인 배열을 통해 이해해보자.
- 데이터는 배열의 중간인 5에서부터 넣는다. 만약 데이터의 수가 배열의 크기를 초과할 경우 배열 맨 앞자리에 추가한다. 예를 들어 데이터 6개를 추가하는 경우 마지막 데이터는 index가 0인 자리에 추가한다.
- 전단(head)을 배열의 중간으로 설정한다.
- 후단은 데이터가 들어있는 index + 1 (다음 데이터가 들어갈 위치)로 설정한다.
- 배열이 비어있는 경우 / 가득 차 있는 경우를 구분해보자. 두 경우 모두 전단 과 후단이 같다. 그래서 배열이 가득 차 있는 경우를 구분할 때는 후단이 전단 보다 1작은 값을 갖게 될 때로 정한다. (데이터 넣을 공간이 1자리 남았을 때) 이 때는 새 배열을 만들어 데이터를 옮겨주어야 한다.
위 과정을 코드로 구현해보자.
먼저, queue 클래스와 enqueue() 를 구현하면 다음과 같다.
class Queue(var capacity: Int){
var size = 0
var arr = IntArray(capacity)
var front = capacity / 2
var last = front
fun enqueue(element: Int){
//용량이 0 ,1 일 때
when (capacity){
0, 1 -> {
newArrayFromArr()
arr[last] = element
last++
size++
return
}
}
// 꽉찼는지 검사
if(last - front == -1) { // 배열이 꽉 찬 경우 (데이터를 넣을 공간이 1개 남은 경우)
newArrayFromArr()
arr[last] = element
last++
size++
return
}
// emptyArray
if (last == front) {
arr[last] = element
last++
size++
return
}
// 배열에 여유공간 있을 때
if (last < capacity){ // 배열 마지막 index 초과 x
arr[last] = element
last++
size++
}
else { // 배열 마지막 index 초과
last = 0
arr[last] = element
last++
size++
}
}
private fun newArrayFromArr(){
// 데이터 옮기기
capacity += 10
val tmpArr = IntArray(capacity)
front = capacity / 2
last = front
for (element in arr){
if (last < capacity){
if (element != 0){
tmpArr[last] = element
last++
}
}
else {
last = 0
tmpArr[last] = element
last++
}
}
arr = tmpArr
}
}경계조건을 처리하느라 코드가 길어졌다.
배열 용량을 초과 시 자동으로 용량을 추가한다. (default 값 10)
fun dequeue(): Int{
var returnValue: Int
if(front < capacity){
returnValue = arr[front]
arr[front] = 0
front++
size--
}
else {
front = 0
returnValue = arr[front]
arr[front] = 0
front++
size--
}
return returnValue
}문제에서 뺀 값을 요구하므로 returnValue 라는 변수에 담아서 반환한다.
이제 문제 조건에 맞게 main() 함수를 짜고 실행해보자.
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val testTime = br.readLine()!!.toInt()
val queue = Queue(testTime)
repeat(testTime){
val st = StringTokenizer(br.readLine())
val order = st.nextToken()
when (order){
"push" -> {
queue.enqueue(st.nextToken().toInt())
}
"pop" ->{
if(queue.size == 0) bw.write("-1\n") else bw.write("${queue.dequeue()}\n")
}
"front" -> {
if(queue.size == 0) bw.write("-1\n") else bw.write("${queue.arr[queue.front]}\n")
}
"back" -> {
if (queue.size == 0) bw.write("-1\n") else {
if (queue.last != 0) bw.write("${queue.arr[queue.last - 1]}\n") else bw.write("${queue.arr.last()}\n")
}
}
"empty" -> {
if(queue.size == 0) bw.write("1\n") else bw.write("0\n")
}
"size" -> bw.write("${queue.size}\n")
}
}
bw.flush()
bw.close()
}실행 결과 (1656ms / 337336KB)
공부하는 차원에서 배열을 이용해 직접 queue를 만들었지만 코틀린에서는 ArrayDeque<T> (덱)를 지원한다. 이를 이용하면 간단히 작성가능하다.
import java.lang.StringBuilder
import java.util.*
fun main() {
var number = readLine()!!.toInt()
var sb = StringBuilder()
var q = ArrayDeque<Int>()
repeat(number) {
var str = StringTokenizer(readLine()!!, " ")
when(str.nextToken()) {
"push" -> q.offer(str.nextToken().toInt())
"pop" -> sb.append("${q.poll() ?: -1}\n")
"size" -> sb.append("${q.size}\n")
"empty" -> sb.append("${if(q.isEmpty()) 1 else 0}\n")
"front" -> sb.append("${q.peek() ?: -1}\n")
"back" -> sb.append("${q.peekLast() ?: -1}\n")
}
}
print(sb)
}링크드 리스트 큐 구현하기
이번에는 링크드 리스트의 addLast() 기능과 removeFirst() 를 이용하여 큐를 구현해보자.
class QueueByLinkedList {
val list = LinkedList<Int>()
class LinkedList<T> {
data class Node<T>(
var data: T?,
var next: Node<T>?
)
var headNode: Node<T>? = null
var lastNode: Node<T>? = null
var currentSize: Int = 0
fun addLast(data: T) {
val newNode = Node(data, null)
//headNode 가 비어있는 경우 즉, 요소가 없는 경우
if (headNode == null) {
headNode = newNode
lastNode = newNode
currentSize++
return
}
lastNode?.next = newNode
lastNode = newNode
currentSize++
}
fun removeFirst() : T?{
var returnValue: T?
// Empty List
if (headNode == null) {
return null
}
// headNode == lastNode -> 요소 1개
if (headNode == lastNode) { // or headNode.next == null or currentSize == 1
returnValue = headNode?.data
lastNode = null
headNode = null
} else {
returnValue = headNode?.data
headNode = headNode?.next
}
currentSize--
return returnValue
}
}
}실행 결과(2664ms / 354128KB)
capacity를 고려하지 않아도 돼서 배열을 이용한 것보다 구현이 간단하다.
정리
큐(queue)
- 자료의 입력과 출력을 한 쪽 끝으로 제한한 자료구조이다. (FIFO(First In First Out)구조)
- 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기 시킨다.
- 일반적인 큐의 단점 : last(rear)가 배열의 끝에 도달했을 경우. 큐에 빈 메모리가 남아 있어도 꽉 차있는것으로 판단할 수 있음 -> 개선된 순환(원형) 큐 사용
- 순환 큐의 단점 : 메모리 공간은 잘 활용하나 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점이 존재한다. ->링크드리스트로 큐 사용
- 링크드 리스트로 구현한 큐는 큐의 크기가 제한이 없고 삽입, 삭제가 편리하다.
스택 / 큐 구현완료
이제 트리 가보자!
