[Coding Test] Python Queue 정리 및 List Based Queue

※ Queue란 ?

데이터를 선형으로 저장하는 자료구조로, FIFO(First In, First Out) 방식으로 작동한다.

주요 Method로는 Enqeue(데이터를 Queue의 뒤쪽에 추가), Dequeue(데이터를 Queue 앞에서 제거)가 있다.

1. Python Method 사용법

append(x=)

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q

deque([1, 2, 3, 4])

appendleft(x=)

q = deque()
q.appendleft(1)
q.appendleft(2)
q.appendleft(3)
q.appendleft(4)

q

deque([4, 3, 2, 1])

extend(iterable=)

기존 Queue에 다른 Iterable 한 객체의 원소를 이어붙인다

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q.extend([5,6,7])
q

deque([1, 2, 3, 4, 5, 6])

extendleft(iterable=)

Iterable한 객체도 extend될 때 방향이 반대로 바뀌게 된다.

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q.extendleft([5,6,7])
q

deque([7, 6, 5, 1, 2, 3, 4])

index(x=,start=,stop=)

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q.index(3)

[0, 5, 1, 2, 3]

insert(index=, x=)

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q.insert(1, -1)
q

deque([1, -1, 2, 3, 4])

pop()

List와 달리 Index로 지정하는 것이 아닌 마지막 원소만을 pop 하게된다.

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

print(q.pop())
q

4
deque([1, 2, 3])

popleft()

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

print(q.popleft())
q

1
deque([2, 3, 4])

remove(value=)

Queue에 Value가 존재하지 않으면 Error

q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)

q.remove(3)
print(q)

q.remove(5)

deque([1, 2, 4])
---------------------------------------------------------------------------
ValueError
Traceback (most recent call last)
Cell In[16], line 10
7 q.remove(3)
8 print(q)
---> 10 q.remove(5)
ValueError: 5 is not in deque

Python의 List의 Method과 굉장히 유사헌 것을 알 수 있습니다.

Python의 "queue" 라이브러리의 Queue를 사용할 수도 있지만 deque는 양방향 Qeue를 제공하고 있으므로 deque를 사용하는 것이 좋아보입니다.

또한, Queue는 enqueue와 dequeue의 시간복잡도가 O(1)으로 잦은 삽입, 제거를 해결하는 문제에 적합한 자료구조입니다.

2. List based Queue 구현

class ListQueue(object):
    def __init__(self):
        self.list = []
    
    # enqueue : O(1)
    def enqueue(self, val):
        self.list.append(val)

    # dequeue : O(n), 왜냐하면 list 원소를 다 이동시켜 줘야함
    def dequeue(self):
        return self.list.pop(0)

q = ListQueue()

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

1
2
3

List를 기반으로 Queue를 구현하면 구현은 쉽지만 dequeue 과정에서 list().pop()을 사용하므로 시간복잡도 O(n)이 걸리게됩니다. 이는 Queue의 장점을 살리지 못하는 구현 방식으로 부적합하다고 볼 수 있습니다.

3. Linked List based Queue 구현

1) Node 정의

class Node(object):
    def __init__(self, val=0, next=None, prev=None):
        self.val = val
        self.next = next
        self.prev = prev

2) Linked List 정의

class LinkedList(object):
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_back(self, value):
        new_node = Node(value)
        if self.head == None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node    
    
    def remove_front(self):
        if self.head is not None:
            return_val = self.head.val
            self.head = self.head.next
            return return_val
        return None

Linked List에는 더 다양한 Method가 있지만 Queue를 구현하기 위한 최소한의 Method만 사용하였습니다.

3) Linked List Based Queue 구현

class LinkedListQueue(object):
    def __init__(self):
        self.linkedList = LinkedList()
    
    # O(1)
    def enqueue(self, val):
        self.linkedList.insert_back(val)
    # O(1)
    def dequeue(self):
        return self.linkedList.remove_front()

q = LinkedListQueue()

q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

1
2
3

Linked List를 통해 Queue를 구현하게 되면 enqueue, dequeue 모두 시간복잡도 O(1)으로 사용할 수 있습니다.

하지만 Linked List를 구현하는데 좀 더 복잡하고 각 Node에 데이터 외에도 Pointer가 필요하므로 추가 메모리가 필요하다는 단점이 있습니다.

저작자표시 비영리 변경금지

어떻게든 되겠지~