덱 : Deque

double ended queue

양쪽 끝에서 삽입 삭제가 가능한 자료구조로 스택과 큐의 특성을 모두 가지고 있다

push, pop 연산이 빈번한 경우 list보다 빠르다

동작에 따른 시간복잡도

• 원소의 추가/제거 O(1)
• 제일 앞/뒤 원소 확인 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

구현

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

구조

• 원소를 담을 배열
• head : 가장 앞에 있는 원소 인덱스
• tail: 가장 뒤에 있는 원소 인덱스

기능

add() vs offer()

add : 값 추가 성공 시 true 반환 / 실패 시 IllegalStateException 에러 발생

offer : 값 추가 성공 시 true 반환 / 실패 시 false 반환

 

remove() vs poll()

remove : 큐 맨 앞에 있는 값 반환 후 삭제 / 비어있을 경우 NoSuchElementException 에러 발생

poll : 큐 맨 앞에 있는 값 반환 후 삭제 / 비어있을 경우 false 반환

 

kotlin에서 deque

LinkedList 혹은 ArrayDeque로 구현이 가능하다

stack, queue, deque 상속관계

BOJ

10866. 덱

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val n = readLine().toInt()
    val deque: Deque<Int> = ArrayDeque<Int>(n)
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    for (i in 1..n) {
        val tokenizer = StringTokenizer(readLine())
        when (tokenizer.nextToken()) {
            "push_front" -> {
                deque.addFirst(tokenizer.nextToken().toInt())
            }
            "push_back" -> {
                deque.addLast(tokenizer.nextToken().toInt())
            }
            "pop_front" -> {
                bw.write("${deque.pollFirst() ?: -1}\n")
            }
            "pop_back" -> {
                bw.write("${deque.pollLast() ?: -1}\n")
            }
            "size" -> {
                bw.write("${deque.size}\n")
            }
            "empty" -> {
                val result = if (deque.isEmpty()) "1" else "0"
                bw.write("$result\n")
            }
            "front" -> {
                bw.write("${deque.peekFirst() ?: -1}\n")
            }
            "back" -> {
                bw.write("${deque.peekLast() ?: -1}\n")
            }
        }
    }

    bw.close()
}

 

1021 . 회전하는큐

1번연산 - deque.removeFist()

2번연산 - deque.addLast(deque.removeFirst())

3번연산 - deque.addFirst(deque.removeLast())

 

1. 찾고자 하는 수의 인덱스 구하기

2. 전체 deque 사이즈에서 1에서 찾은 인덱스가 중간 혹은 중간보다 앞에 위치하고 있으면 2번, 뒤에 위치하고 있으면 3번을 실행한다

3. 연산 진행 중 수를 찾으면 1번 연산 실행

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

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var tokenizer = StringTokenizer(readLine())
    val n = tokenizer.nextToken().toInt()
    val m = tokenizer.nextToken().toInt()
    val deque: Deque<Int> = ArrayDeque<Int>(n)

    for (i in 1..n) {
        deque.add(i)
    }

    tokenizer = StringTokenizer(readLine())

    var operationCount = 0
    for (i in 1..m) {
        val find = tokenizer.nextToken().toInt()
        val index = deque.indexOf(find)
        val mid = (deque.size / 2.0).toInt()

        if (index <= mid) {
            // 2번 연산
            for (j in deque.indices) {
                if (deque.peekFirst() == find) {
                    deque.removeFirst()
                    break
                }
                deque.addLast(deque.removeFirst())
                operationCount++
            }
        } else {
            // 3번 연산
            for (j in deque.indices) {
                if (deque.peekFirst() == find) {
                    deque.removeFirst()
                    break
                }
                deque.addFirst(deque.removeLast())
                operationCount++
            }
       }
    }

    print(operationCount)
}