[자료구조] 큐 (Queue)

✅ 큐(Queue) 구조

• 줄을 서는 것과 유사한 자료 구조이다.
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO; First In First Out)를 보인다.
  • 예를 들어, 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일하다.
  • FIFO(First In First Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대이다.

출처 : http://www.stoimen.com/blog/2012/06/05/computer-algorithms-stack-and-queue-data-structure/

 

📌 큐의 장단점

• 장점 : 데이터 접근, 삽입, 삭제가 빠름
• 단점 : 중간에 위치한 데이터에 대한 접근이 불가능함

 

📌 큐의 시간 복잡도

• front와 rear의 위치로 데이터의 삽입 삭제가 이뤄지기 때문에 시간 복잡도는 O(1)

 

📌 큐 관련 용어

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능
• 아래 링크 방문하시면 큐에 대한 대략적인 구조를 이해하실 수 있습니다.

Linked List (Single, Doubly), Stack, Queue, Deque - VisuAlgo

 

📌 파이썬 Queue 라이브러리 활용

• 파이썬의 queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue()를 제공
• 프로그램 작성할 때 적합한 자료 구조를 선택하여 활용하면 된다.
  • Queue() : 가장 일반적인 큐 자료 구조
  • LifoQueue() : 나중에 립력된 데이터가 먼저 출력되는 구조로 스택 구조라고 보면 됨
  • PriorityQueue() : 데이터마다 우선순위를 넣어서, 우선순위가 높은 순으로 데이터를 출력

 

📌 파이썬 Queue 라이브러리 실습

• Queue() 실습 - 가장 일반적인 큐, FIFO

/* 주피터 노트북 활용 */

import queue

data_queue = queue.Queue()

data.queue.put("funcoding")  // 첫 번째 인덱스에 값 추가
data_queue.put(1)  // 두 번째 인덱스에 값 추가

data_queue.qsize()  // 2 리턴 (값이 2개가 추가되었기 때문)

data_queue.get()  // 데이터를 꺼내는 메소드 -> 제일 앞의 값을 가져옴

data_queue.qsize()  // 1 리턴(get으로 첫 번째 값을 빼냈기 때문)

 

• LifoQueue() 실습

import queue

data_queue = queue.LifoQueue()

data_queue.put("funcoding")
data_queue.put(1)

data_queue.qsize()  // 2 return

data_queue.get()  // 1 추출  ->  LIFO 구조를 가지기 때문

 

• PriorityQueue() 실습

import queue

data_queue = queue.PriorityQueue()

data_queue.put((1, "korea"))   // 우선순위 큐를 생성할 때는 입력으로 튜플이 들어간다.
data_queue.put((3, "dahoon"))  // 그리고 튜플 안에는 우선순위, 실제 값이 들어가게 된다.
data_queue.put((2, 1))

data_queue.qsize()  // 3 return

data_queue.get()  // (1, "korea") return -> 우선순위가 가장 높기 때문(숫자가 낮을수록 우선순위가 높음)

 

📌 리스트 변수로 간단하게 Queue 클래스 구현해보기

class Queue : 
    def __init__(self) :
        self.qList = []
    
    # Enqueue 구현
    def enqueue(self, x) :
        self.qList.append(x)
        
    # Dequeue 구현
    def dequeue(self) :
        if len(self.qList) < 1 :
            print("큐가 비었습니다!")
            return False

        data = self.qList[0]
        del self.qList[0]
        return data
    

    
queue_test = Queue()
queue_test.enqueue(1)
print(queue_test.qList)
queue_test.enqueue(2)
queue_test.enqueue(3)
queue_test.enqueue(4)
queue_test.enqueue(5)
queue_test.enqueue(6)
print(queue_test.qList)
queue_test.dequeue()
print(queue_test.qList)
queue_test.dequeue()
queue_test.dequeue()
queue_test.dequeue()
print(queue_test.qList)
queue_test.dequeue()
queue_test.dequeue()
queue_test.dequeue()

 

📌 큐가 많이 쓰이는 경우는?

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용

 

실습 코드는 아래 링크 들어가시면 확인하실 수 있습니다.

GitHub - Dahoonkk/Data_Structures_and_Algorithms