파이썬과 자료구조(큐)

이승혜·2021년 3월 11일

자료구조 큐 파이썬

파이썬과 자료구조

목록 보기

2/5

📒 큐(Queue)

줄을 서는 행위와 유사함
운영체제(OS)에서 프로세스 스케쥴링을 구현하는데 사용
가장 먼저 넣은 데이터를 가장 먼저 꺼내는 구조
- FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대
Enqueue : 큐에 데이터를 넣는 기능
Dequeue : 큐에 데이터를 꺼내는 기능

✅ 파이썬 queue 라이브러리 활용

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

Queue()로 큐 만들기

import queue

data_queue = queue.Queue()

data_queue.put(1)
data_queue.put(25)
data_queue.put(8)
data_queue.put(37)
data_queue.put(7)

print(data_queue) # <queue.Queue object at 0x000001D91AA75FD0>
print(data_queue.qsize()) # 5

# 먼저 넣은 데이터가 먼저 출력되는 것을 볼 수 있음
print(data_queue.get()) # 1
print(data_queue.get()) # 25
print(data_queue.get()) # 8
print(data_queue.get()) # 37
print(data_queue.get()) # 7

LifoQueue()로 큐 만들기

import queue

data_queue = queue.LifoQueue()

data_queue.put(1)
data_queue.put(25)
data_queue.put(8)
data_queue.put(37)
data_queue.put(7)

print(data_queue) # <queue.LifoQueue object at 0x000001FC63F05FD0>
print(data_queue.qsize()) # 5

# 나중에 입력된 데이터가 먼저 출력되는 것을 볼 수 있음
print(data_queue.get()) # 7
print(data_queue.get()) # 37
print(data_queue.get()) # 8
print(data_queue.get()) # 25
print(data_queue.get()) # 1

PriorityQueue()로 큐 만들기

import queue

data_queue = queue.PriorityQueue()

data_queue.put((3, 1))
data_queue.put((2, "seunghye"))
data_queue.put((4, True))
data_queue.put((10, 10.23))
data_queue.put((7, "Hi"))

print(data_queue) # <queue.PriorityQueue object at 0x000001E26EE45FD0>
print(data_queue.qsize()) # 5

# 우선순위에 따라 출력이 되는 것을 볼 수 있음
print(data_queue.get()) # (2, 'seunghye')
print(data_queue.get()) # (3, 1)
print(data_queue.get()) # (4, True)
print(data_queue.get()) # (7, 'Hi')
print(data_queue.get()) # (10, 10.23)

✅ 구현 연습

리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현하기

# 빈 리스트 생성
queue_list = list()
print(queue_list) # []

def enqueue(data):
    # append는 배열 맨 뒤 원소에 data를 추가해 줌
    queue_list.append(data)

def dequeue():
    # data는 리스트의 가장 첫 번째
    data = queue_list[0]
    # 꺼내진 원소는 삭제
    del queue_list[0]
    return data


# 0부터 15까지 2씩 증가하며 enqueue
for index in range(0, 15,2):
    enqueue(index)

print(queue_list) # [0, 2, 4, 6, 8, 10, 12, 14]


# 먼저 들어온 원소부터 빠져나가는 것을 볼 수 있음
print(dequeue()) # 0
print(queue_list) # [2, 4, 6, 8, 10, 12, 14]

print(dequeue()) # 2
print(queue_list) # [4, 6, 8, 10, 12, 14]

print(dequeue()) # 4
print(queue_list) # [6, 8, 10, 12, 14]

Queue를 class로 구현하기 (append, pop 이용)

class Queue(list):
    enqueue = list.append

    def dequeue(self):
        return self.pop(0) # 첫번째 인덱스 항목을 제거하고 제거된 항목을 반환
    
    def is_empty(self):
        if not self:
            return True
        else:
            return False 

queue = Queue()

queue.enqueue(1) 
print(queue) # [1]
queue.enqueue(2) 
print(queue) # [1, 2]
queue.enqueue(3)
print(queue) # [1, 2, 3]
queue.enqueue(4)
print(queue) # [1, 2, 3, 4]

print(queue.is_empty()) # False

queue.dequeue()
print(queue) # [2, 3, 4]
queue.dequeue()
print(queue) # [3, 4]
queue.dequeue()
print(queue) # [4]
queue.dequeue()
print(queue) # []

print(queue.is_empty()) # 리스트가 비어 있으므로 True

리스트를 사용했을 경우, enqueue(추가)의 시간복잡도는 O(1)이며, dequeue(삭제)의 시간복잡도는 O(N)이다. 추가의 경우 큐의 맨 끝에서 일어나지만, 큐의 첫 번째 원소를 삭제할 경우에는 두 번째 원소부터 맨 마지막 원소까지 모든 원소들의 위치를 한 칸씩 옮겨주어야 하기 때문