큐 | My Blog

큐?

스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다.스택을 프링글스통 이라고 한다면 큐는 그 프링글스 통의 바닥부분을 뻥 뚫어놓은 것.즉 스택과는 다르게 먼저 넣은 데이터를 먼저 꺼내는 선입선출(FIFO, LILO)의 구조이다.

큐의 효율

배열을 이용하여 큐를 만들수 있지만 디큐를 할때 데이터를 꺼내고 그 다음 데이터들을 위치이동 시키는 처리를 해야한다. 데이터를 꺼낼때마다 이런 처리를 하게되면 효율이 떨어진다

이를 해결하기 위해 보통 링 버퍼로 큐를 만들게 된다. 배열의 처음과 끝을 연결되었다고 논리적으로 보는 자료구조이다. 링 버퍼에서 프런트와 리어는 추가적인 의미를 가진다.

프런트 : 맨 처음 요소의 인덱스(디큐 시 가장 먼저 나갈 데이터 가리킴)
리어 : 맨 끝 요소의 인덱스 + 1 (인큐 시 저장할 데이터의 위치를 미리 가리킴)

인큐 및 디큐 시 이 프런트와 리어를 업데이트 해줌으로써 요소 이동 문제를 해결 가능하다.

인큐 / 디큐 처리할 때 복잡도배열로 만든 일반 큐 : 복잡도 O(n)배열로 만든 원형 큐 : 복잡도 O(1)

큐의 구현

fun main(args:Array<String>){

    var q : Queue<Int> = LinkedList() // 큐로 선언하고 LinkedList 로 할당

    q.add(1)    // 객체를 큐에 추가 (큐가 가득찬 상태이면 illegalStateException 발생)
    q.offer(3)  // 객체를 큐에 추가 (큐가 가득찬 상태이면 false 반환)
    println(q)

    println(q.element())    // 맨 앞 객체 리턴 (큐가 비어있는 상태이면 NoSuchElementException 발생)
    println(q.elementAt(1)) // 인덱스 값의 객체 리턴
    println(q.peek())   // 맨 앞 객체 리턴 (큐가 비어있는 상태이면 false 반환)

    q.remove()  // 삭제하면서 객체 반환 (큐가 비어있는 상태이면 NoSuchElementException 발생)

    var tmp = q.poll()  // 삭제하면서 객체 반환 (큐가 비어있는 상태이면 false 반환)
    println(q)
    println("두번째 삭제한 객체 : $tmp")

}

덱

양쪽 끝에서만 자료를 넣고 양쪽 끝에서만 뺄 수 있는 자료구조

스택과 큐를 합친 형태로 double-ended queue 의 약자이다.

push_front : 덱의 앞에 자료를 넣는 연산
push_back : 덱의 뒤에 자료를 넣는 연산
pop_front : 덱의 앞에서 자료를 빼는 연산
pop_back : 덱의 뒤에서 자료를 빼는 연산
front : 덱의 가장 앞에 있는 자료를 보는 연산
back : 덱의 가장 뒤에 있는 자료를 보는 연산