[ kotlin ] 자료구조_Stack, Queue, Deque

서문

자료구조에서 가장 대표적인 stack, queue, deque에 대해 알아보고 사용해 보도록 하겠습니다.

 

혹시라고 위 자료구조를 모르신다면 이전에 C언어 자료구조 파트에서 Array와 LinkedList를 사용해서 구현해 보고 동작방식을 포스팅한 적이 있으니 아래 링크에서 봐주시거나 유튜브에 잘 나와 있으니 사전에 학습해 주시기 바랍니다.

'자료구조/C언어' 카테고리의 글 목록

(유튜브를 추천드립니다. ^^)

---

1. kotlin에서는 stack, queue 기능을 제공하지 않는다.

Kotlin의 철학은 실용성과 간결성인데 기본이 되는 자료구조를 제공하지 않는다는 건 정말 이상합니다.

제공하지 않는다면 C언어처럼 직접 구현해서 사용하라는 것일까요? 당연히 아니겠죠 ㅎㅎ

 

이미 아시겠지만 Kotlin 은 Java와 호환이 가능합니다. 즉 Java에서 구현되어 있는 코드도 접근이 가능하다는 말이고 이는 이전에 포스팅한 적이 있습니다.

그리고 Java 에는 stack, deque 가 이미 구현되어 있습니다. 즉 Kotlin에서는 Java에 있는 클래스를 가져다 사용하면 됩니다.

 

2. Stack 의 사용법(권장 X)

val stack: Stack<String> = Stack()

stack 선언은 이렇게 하면 됩니다. 물론 클래스 타입은 없어도 되지만 데이터 타입은 추론이 불가능합니다.

이유는 초기값을 넣어줄 수 없기 때문입니다. 그래서

val stack = Stack<String>()

이와 같이 해줘야 합니다.

타입추론이 안 되는 이유는 Stack 클래스 내부의 생성자는 파라미터를 받지 않기 때문입니다.

public class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }
    ...
}

실제로 클래스 내부를 보면 이렇게 생성자가 있지만 아무 파라미터도 없고 기능도 구현되어 있지 않습니다.

 

그리고 Vector이라는 클래스를 상속받고 있습니다. 이걸로 유추해 보아 현재 이 Stack 클래스는 Vector라는 클래스를 사용해서 Stack를 구현하고 있다고 볼 수 있습니다. 여기에 심각한 문제가 있습니다.

Vector 클래스는 배열을 동적으로 할당받을 수 있는 클래스입니다. 이를 통해 Stack에 값을 넣을 공간을 할당받을 수 있지만 속도가 느리고 구식이라는 것입니다.

 

종합적으로 분석해서 결론은 사용하지 말자!입니다.

 

그래도 사용은 해 보겠습니다.

val stack = Stack<String>()

stack.push("사과")
stack.push("딸기")

println("전체 항목: $stack")

stack.push("복숭아")

println("전체 항목: $stack")

println("꺼내기: ${stack.pop()}")

println("전체 항목: $stack")

println("확인하기: ${stack.peek()}")

println("꺼내기: ${stack.pop()}")

println("전체 항목: $stack")

 

옛날 클래스 이기는 하지만 요소들을 문자열로 만들어 주는 기능은 구현되어 있네요.

 

3. Stack의 사용법(권장 O)

그러면 Kotlin(Java 포함)에서는 어떻게 Stack을 사용하면 될까요?

위에서 Kotlin 은 Stack와 Queue를 제공하지 않는다고 했습니다. 하지만 ArrayDeque를 제공해 주고 있습니다.

Deque자료구조는 Kotlin와 Stack를 결합한 형태 이기 때문에 Deque을 사용하면 당연히 나머지 2개도 사용할 수 있게 됩니다.

 

*중요*

ArrayDeque 은 Kotlin에서도 따로 구현되어 있지만 동일한 이름으로 Java 에도 존재합니다. 하지만 코틀린에 맞게 제작되었기 때문에 코틀린 컬렉션을 같이 사용할 수도 있으니 코틀린 ArrayDeque 사용을 권장합니다.

 

그럼 실제로 사용해 보겠습니다.

val stack: ArrayDeque<String> = ArrayDeque()

stack.addLast("a")
stack.addLast("b")
println(stack)

stack.addLast("c")
println(stack)

println("후입: ${stack.last()}, 선입: ${stack.first()}")

println("꺼내기: ${stack.removeLast()}")
println(stack)

 

정상적으로 동작은 하지만 코드가 조금 어색합니다... stack는 일반적으로 삽압 함수는 push() 삭제함수는 pop()이지만 위 코드에서는 addLast()가 push()를 대신하고 removeLast()가 pop()를 대신하고 있습니다. 이는 Deque를 사용하니 어쩔 수 없습니다.

---

재미있는 것을 보여 드리겠습니다. Java 에도 동일한 이름의 클래스가 있다고 말씀드렸는데 한번 사용해 보겠습니다.

 

< Java_ ArrayDeque >

val stack: java.util.ArrayDeque<String> = java.util.ArrayDeque(listOf("a", "b"))

stack.push("a")
stack.push("b")
println(stack)

stack.push("c")
println(stack)

println("후입: ${stack.last()}, 선입: ${stack.first()}")

println("꺼내기: ${stack.pop()}")
println(stack)

동일한 코드이지만 push, pop를 사용하고 있습니다. 이 코드가 일반적으로는 훨씬 직관적으로 보입니다.

하지만 Kotlin에서 같은 ArrayDeque 클래스를 제공하고 있는 것을 보면 Koltin에서 제공하는 ArrayDeque를 사용하는 것을 추천하고 있다고 생가할 수 있을 거 같습니다.

 

정확한 이유는 저도 잘 모르겠습니다.

 

 

4. Queue의 사용법

queue 도 물론 Kotlin에서 제공하는 ArrayDeque을 사용해서 구현해야 합니다.

사용법은 위 Stack과 거의 동일합니다.

데이터를 꺼낼 때 removeLast() 대신에 removeFirst()를 사용하면 됩니다.

val queue: ArrayDeque<String> = ArrayDeque() // 혹은 LinkedList()

queue.addLast("a")
queue.addLast("b")
println(queue)

queue.addLast("c")
println(queue)

println("후입: ${queue.last()}, 선입: ${queue.first()}")

println("꺼내기: ${queue.removeFirst()}")
println(queue)
println("꺼내기: ${queue.removeFirst()}")
println(queue)

 

5. Deque의 사용법

deque의 사용법은 위에서 사용해 보았기 때문에 설명이 필요 없겠지만 그래도 한번 사용은 해 보겠습니다.

val deque: ArrayDeque<String> = ArrayDeque() // addFirst, addLast 모두 가능

deque.addLast("a")
deque.addLast("b")
println(deque)

deque.addFirst("c")
deque.addFirst("d")
println(deque)

println("앞쪽: ${deque.last()}, 뒷쪽: ${deque.first()}")

println("앞에서 꺼내기: ${deque.removeLast()}")
println(deque)
println("뒤에서 꺼내기: ${deque.removeFirst()}")
println(deque)

 

---

6. Deque의 추가설명

val deque: ArrayDeque<String> = ArrayDeque(listOf("A", "B", "C")) // addFirst, addLast 모두 가능

deque.addLast("a")
deque.addLast("b")
println(deque)

deque.addFirst("c")
deque.addFirst("d")
println(deque)

println("앞쪽: ${deque.last()}, 뒷쪽: ${deque.first()}")

println("앞에서 꺼내기: ${deque.removeLast()}")
println(deque)
println("뒤에서 꺼내기: ${deque.removeFirst()}")
println(deque)

deque.addAll(3, setOf("D", "E", "E", "F"))
println(deque)

deque는 원래 앞뒤에서만 삽입 삭제가 가능하지만 위 코드를 보면 이상하게 index로 접근해서 중간에 setOf의 컬렉션 타입으로 추가가 가능합니다.

 

이는 명확하게 잘못된 방법이지만 Kotlin에서는 이 기능을 제공하고 있습니다. 사실 제공을 한다기보다는 컬렉션 타입과의 호환을 위해 제거하지 않았다고 생각합니다.

 

ArrayDeque의 내부를 간단하게 살펴보겠습니다.

public class ArrayDeque<E> : AbstractMutableList<E> { ... }

public actual abstract class AbstractMutableList<E> protected actual constructor() : 
MutableList<E>, AbstractList<E>() { ... }

public interface MutableList<E> : List<E>, MutableCollection<E> { ... }

public interface MutableCollection<E> : Collection<E>, MutableIterable<E> {

 

이렇게 내부적으로 내려가면 Collection 인터페이스를 상속받고 있다는 것을 볼 수 있습니다.

즉 ArrayDeque 은 Collection타입과 호환이 가능하도록 설계를 했다고 볼 수 있습니다.

---

이상으로 Kotlin에서의 Stack, Queue, Deque를 알아보고 사용해 보았습니다.

부족한 글이지만 끝까지 읽어 주셔서 감사드립니다.

 

아마 잘못된 부분도 있을 거라고 생각합니다. 잘못된 부분이 있다면 글로 남겨주시면 감사드리겠습니다.