[자료구조] 큐(Queue)

큐(Queue) 란?

• 선입선출(FIFO, First In First Out) 형식을 갖는 자료구조 → 먼저 들어간 입력이 먼저 나옴

종류

• 선형 큐(Linear Queue)
  • 일반적인 리스트 형태를 갖으며, 선입선출 형식을 갖음
• 원형 큐(Circular Queue)
  • 처음과 끝이 있는 것이 아닌, 회전하며 인덱싱
  • 삽입, 출력에 있어 메모리 효율을 높일 수 있음 
• 우선순위 큐(Priority Queue)
  
  • 먼저 입력한 순서가 아닌, 우선순위를 두고 우선순위가 높은 순서로 출력

구현

리스트 생성

• list의 append를 활용하여 구현

queue = []

•  index를 이용한 구현

front = 0
rear = -1

queue = [0 for _ in range(N)]

삽입(EnQueue)

• list의 append를 활용하여 구현

queue.append(num)

•  index를 이용한 구현

rear += 1
queue[rear] = num

삭제(DeQueue)

• list의 append를 활용하여 구현

if queue:
	return queue.pop(0)

•  index를 이용한 구현

queue[front]=0
front +=1

 

Code

• list의 append를 활용하여 구현

class Queue:
	def __init__(self) -> None:
    	self.que = []
        self.length = 0
    
    def enqueue(self, num:int) -> None:
        self.que.append(num)
        self.length += 1
    
    def dequeue(self) -> int or str:
    	if self.length <= 0:
       		return "underflow"
            
        self.length -= 1
        return self.que.pop(0)

•  index를 이용한 구현

class Queue:
	def __init__(self, maxlen:int) -> None:
    	self.que = [0] * maxlen
        self.maxlen = maxlen
        self.length = 0
    	self.front = 0
        self.rear = -1
    
    def enqueue(self, num:int) -> str or None:
    	if self.length + 1 >= self.maxlen:
        	return "overflow"
    	self.rear = (self.rear + 1) % self.maxlen
        self.que[self.rear] += 1
        self.length += 1
    
    def dequeue(self) -> int:
    	if self.length <= 0:
        	return "underflow"
    	output = self.que[self.front]
        self.que[self.front] = 0
        self.front = (self.front + 1) % self.maxlen
        self.length -= 1
        return output

 

참고

Deque를 이용한 Queue 구현

• Deque란?
  • Queue가 선입선출이라면, 양방향 입출력이 가능한 Dequeue
  • Queue보다 효용성이 높으며, 파이썬 Collections 라이브러리에 포함되어 있어 사용하기 편함

from collections import deque

class Queue:
	def __init__(self):
    	self.que = deque()
    
    def enqueue(self, num:int):
    	self.que.append(num)
    
    def dequeue(self) -> int:
    	self.que.popleft()