Data Structure - Queue

Data Structure - Queue

Queue

큐는 가장 대표적인 자료구조 중 하나이므로 잘 알아두자!!!

일명 맛집이라는 식당에 가면 줄을 서게된다. 먼저 줄을 서면 먼저 음식점에 들어가고, 늦게 줄을 서면 늦게 들어간다.

큐는 줄서기과 같은 구조이다.
먼저 들어온 데이터가 먼저 나가고, 늦게들어온 데이터는 늦게 나간다.
FIFO(First-In, First-Out), LILO(Last-In, Last-Out)

파이썬에서는 queue라이브러리를 활용해서 큐를 사용할수 있다.
queue라이브러리에는 Queue(), LifoQueue(), PriorityQueue()등이 있다.

• Queue()
  일반적인 큐

• LifoQueue()
  스택과 구조가 비슷하다

• PriorityQueue()
  데이터마다 우선순위가 있어, 우선순위가 높은 것부터 출력
  

큐에 데이터를 넣는 것을 enqueue, 데이터를 꺼내는 것은 dequeueu라고 한다.

import queue

# Queue()
queue = queue.Queue()
queue.put("hi")
queue.put(1)
queue.qsize() => 2

queue.get() => "hi"
queue.qsize() => 1

queue.get() => 1
queue.qsize() => 0


#LifoQueue()
queue = queue.LifoQueue()
queue.put("hi")
queue.put(1)

queue.get() => 1
queue.size() => 1

queue.get() => "hi"
queue.size() => 0


#PriorityQueue()
#queue.put((우선순위, 데이터))
queue = queue.PriorityQueue()
queue.put((2,"hi"))
queue.put((10, "who"))
queue.put((5,"this"))

queue.get() => (2, "hi")
queue.get() => (5, "this")
queue.get() => (10, "who")

큐의 경우 멀티테스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해서 많이 사용된다.

enqueue, dequeue구현하기

파이썬의 리스트를 활용해서 enqueue, dequeue를 구현하자.

enqueue는 데이터를 넣는 메서드
dequeue는 데이터를 빼내는 메서드

큐는 FIFO라는 점을 유의해서 구현해보자.

방법1

# 클래스를 이용한 MyQueue구현
# 클래스안에 enqueue()와 dequeue()를 구현했다.
class MyQueue:    
    def __init__(self):
        self.queue_list = []

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

    def dequeue(self):
        if len(self.queue_list) > 0: 
            self.queue_list.pop()
        else:
            return None

    def size(self):
        if len(self.queue_list)> 0:
            print(len(self.queue_list))
        else: 
            print(0) 


queue = MyQueue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

queue.size()


queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.dequeue()
queue.size()

방법2

# 리스트와 리스트 내의 
queue_list =[]

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    queue_list.remove(data)
    

enqueue(10)
enqueue(20)

print(queue_list)
dequeue()
print(queue_list)


print("=====")
# 리스트의 경우 pop()하면 맨 마지막 요소가 나가게 된다.
lst = []
lst.append(10)
lst.append(20)
lst.pop()

print(lst)

참고

https://www.fun-coding.org/daveblog.html