덱(Deque) 개념 및 구현

이번에는 덱이라는 자료구조에 대해서 알아보겠습니다.

 

덱은 head 와 tail 에서 삽입 및 제거가 모두 가능한 자료구조 입니다.

 

 

• 덱의 추상 자료형

 

 

 

• Kotlin Deque 코드 구현

 

import java.util.*

fun main() {

    val d : Deque<Int> = LinkedList<Int>()

    d.addFirst(1) // [1]
    d.addFirst(2) // [2,1]
    d.addFirst(3) // [3,2,1]
    d.addLast(4)  // [3,2,1,4]

    println(d) // printAll()

    d.removeFirst() // [2,1,4]
    d.removeLast()  // [2,1]

    println(d) // printAll()

    println("isEmpty : ${d.isEmpty()}")

}

 

• 결과

 

 

 

덱은 스택과 큐를 생각하면 쉽게 이해할 수 있습니다.

 

덱을 이용해서 스택을 생각한다면 addFirst() , removeFirst() 통해서 head를 기점으로 push 및 pop 을 생각할 수 있습니다.

 

덱을 이용해서 큐를 생각해본다면 addFirst() , removeLast() 통해서 head 를 기점으로 enqueue 하고 tail 기점으로 dequeue 한다고 생각할 수 있습니다.