ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Python] Deque
    Programming/Python 2023. 6. 3. 15:55
    728x90

     

    list를 이용해서 queue처럼 사용할 수 있습니다.

    queue = [1, 2, 3]
    queue.append(4)    #[1, 2, 3, 4]
    queue.pop(0)       #[2, 3, 4]
    queue.insert(0, 5) #[5, 2, 3, 4]

    하지만 list를 queue처럼 사용하는 것은 성능 측면에서 추천되지 않습니다.

    list는 Random Access에 최적화된 자료구조이기 때문에 pop(0), insert(0, x)는 성능적으로 매우 불리한 연산입니다.

    이 연산의 시간 복잡도는 O(n)입니다.

     

    Deque

    collections 모듈의 deque를 사용해서 queue, stack 자료구조를 구현할 수 있습니다.

    collections에 queue도 있지만 Deque가 훨씬 빠르니 코딩테스트에서는 Deque를 사용하는 것이 좋습니다.

     

    method

    append(item) item을 deque의 맨 뒤(오른쪽 끝)에 삽입한다.
    appendleft(item) item을 deque의 맾 앞(왼쪽 끝)에 삽입한다.
    pop() deque의 오른쪽 끝 element를 가져오는 동시에 deque에서 삭제한다.
    popleft() deque의 왼쪽 끝 element를 가져오는 동시에 deque에서 삭제한다.
    extend(array) 주어진 배열(array)를 순환하면서 deque의 오른쪽에 추가한다.
    extendleft(array) 주어진 배열(array)를 순환하면서 deque의 왼쪽에 추가한다.
    remove(item) item을 deque에서 찾아 삭제한다.
    rotate(num) deque를 num만큼 회전한다.(양수 : 오른쪽, 음수 : 왼쪽)

     

    example

    from collections import deque
    
    n = 3
    m = 4
    queue = deque([1,2,3,4,5])
    queue.rotate(1)             #deque([5, 1, 2, 3, 4])
    
    queue.rotate(-1)            #deque([1, 2, 3, 4, 5])
    
    queue.remove(4)             #deque([1, 2, 3, 5])
    
    arr = [8, 7, 9]
    queue.extend(arr)           #deque([1, 2, 3, 5, 8, 7, 9])
    
    arr = [11, 12, 10]
    queue.extendleft(arr)       #deque([10, 12, 11, 1, 2, 3, 5, 8, 7, 9])
                                #arr앞에서 부터 deque앞에 추가한다.

     

    Queue

    from collections import deque
    
    queue = deque([1, 2])
    queue.append(3)         #deque([1, 2, 3])
    queue.append(4)         #deque([1, 2, 3, 4])
    
    a = queue.popleft()     # a = 1
                            # deque([2, 3, 4])
    b = queue.popleft()     # b = 2
                            # deque([3, 4])

     

    Stack

    from collections import deque
    
    queue = deque([1, 2])
    queue.appendleft(3)     #deque([3, 1, 2])
    queue.appendleft(4)     #deque([4, 3, 1, 2])
    
    a = queue.popleft()     # a = 4
                            # deque([3, 1, 2])
    
    b = queue.popleft()     # b = 3
                            #deque([1, 2])

     

     

    728x90

    댓글

© 2022. code-space ALL RIGHTS RESERVED.