[자료구조] Queue 의 특징 및 활용예제

큐는 스택 자료구조와 달리 FIFO (First-In First-Out)- 선입 선출 특징으로

 

1. 넣을 때에는 한 쪽 끝에서 밀어 넣어야 한다. -> enqueue 연산
2. 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야하는 제약 -> dequeue 연산

즉 enqueue로 삽입된 원소가 가장 나중에 dequeue로 빠져나온다는 것이다.

 

 

추상적 자료구조 구현

method

1. size() - 현재 큐에 들어 있는 데이터 원소의 수 O(1)
2. isEmpty() - 현재 큐가 비어 있는지 판단 O(1)
3. enqueue(x) - 데이터 원소 큐에 추가 O(1)
4. dequeue - 큐에 맨 앞에 저장된 데이터 원소 제기 or 반환 O(n)
5. peek() - 큐의 맨앞에 저장된 데이터 원소 반환(제거 x) O(1)

• dequeue 시간 복잡도 - 20, 37, 58, 65, 72, 91
  > 맨앞에 요소를 뺌으로 인덱스가 순차적으로 앞으도 당겨와서 시간 복잡도가 O(n) 리스트가 길면 길수록 오래 걸린다.

Array로 구현

-> Python list Built-in method

 

class ArrayQueue:

    def __init__(self):
        self.data = [] 

    def is_Empty(self):
        return if not self.data

    def size(self):
        return len(self.data)

    def enqueue(self, item):
        self.data.append(item)

    def dequeue(self):
        return self.data.pop(0)
    
    def peek(self):
        return self.data[0]

DoublyLinkedList로 구현

class LinkdeListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def is_Empty(self):
        return self.data.getLength == 0

    def size(self):
        return self.data.getLength()

    def enqueue(self, item):
        newNode = Node(item)
        self.data.insertAt(self.data.nodeCount + 1, newNode)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.getAt(1).data

선행 배열 or 연결 리스트중 머가 더 유리할까?

• 시간적인 측면은 연결 리스트가 유리.
• 메모리 측면에서는 선형 배열이 유리함.

시간을 우선순위를 두고 채택하는 경우가 많음.

 

큐 활용

1. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우

2. 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 이용하는 경우.
   consumer <- product <- producer
   consumer <- product <- producer1, producer2
   consumer1, consumer2 <- product <- producer

3. 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

4. 환형 큐
   - 정해진 개수의 저장 공간을 빙 돌려가며 이용.
   - 큐 길이를 기억하고 있어야 한다. (정해진 개수)
   - front, rear

5. priority queue
   → 큐가 FIFO 방식을 따르지 않고 원소드르이 우선순위에 따라 큐에서 빠져나오는 방식.
   활용 예 - 운영체제의 cpu 스케쥴러
   
   방식 1. enqueue 할 때 우선순위 순서를 유지하도록
   방식 2. dequeue 할 때 우선순위 높은 것을 선택 → 어느 것이 유리 할까?
   
   - 1번이 유리함. (무작위로 들어 갔을 때 dequeue 할때 원소를 다 찾아야함으로 오래 걸림)

환형 큐 코드 구현

class CircularQueue:

    def __init__(self, counts):
        self.data = [None] * counts
        self.front = -1
        self.rear = -1
        self.maxCount = counts
        self.count = 0

    def is_Empty(self):
        return self.count == 0

    def size(self):
        return self.count
    
    def isFull(self):
        return self.maxCount == self.count

    def enqueue(self, item):
        if self.isFull():
            raise IndexError('Queue full')
        
        self.rear = (self.rear + 1) % (self.maxCount)
        self.data[self.rear] = item
        self.count += 1
        
    def dequeue(self):
        if self.is_Empty():
            raise IndexError('Queue empty')

        self.front = (self.front + 1) % (self.maxCount)
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.is_Empty():
            raise IndexError('Queue empty')
        return self.data[(self.front + 1) % (self.maxCount)]

 

우선순위 큐 코드 구현

 

# from DoublyLinkedList.DoublyLinkedList import Node, DoublyLinkedList

class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()

    def size(self):
        return self.queue.getLength()

    def is_Empty(self):
        return self.queue.nodeCount == 0

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head

        while curr.next != self.queue.tail and x < curr.next.data:
            curr = curr.next
        '''
         while x < curr.next.data and curr.next != self.queue.tail
         -> 만약 curr.next.data 가 None인 경우 TypeError: '<' not supported between instances of 'int' and 'NoneType'
         하지만 while curr.next.data != None and x < curr.next.data
         이런 순서로 할 경우에는 curr.next.data == None인 경우 뒤에 조건을 무시해 오류를 피해 갈 수 있다.
        '''
        self.queue.insertAfter(curr, newNode)
    
    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())
    
    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data