[TIL] 큐 Queue Python

큐 Queue 

스택과 같이 데이터를 임시 저장하는 자료 구조
First In First Out 선입선출 FIFO 구조  

 

일상 예시, 카페에서 계산하고 커피를 받는 줄 

Buffer (완충기억기) - 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역 
컴퓨터 장치들 사이에서 data 를 주고 받을 때, 각 장치 사이에서 존재하는
속도 차이나 시간 차이를 극복하기 위해 임시 기억 자치의 자료 구조로 Queue 를 사용한다 

 

 

 

큐 작업

Enqueue 큐에 데이터를 추가하는 작업

Dequeue 데이터를 꺼내는 작업

Front 데이터를 꺼내는 쪽

Rear 데이터를 넣는 쪽 

 

배열로 큐 구현하기

디큐를 할 때 배열에서 2번째 이후의 모든 원소를 하나씩 앞으로 옮긴다 

인큐 처리 복잡도는 O(1) 디큐 처리 복잡도는 O(n) 

 

링 버퍼로 큐 구현하기

원소를 옮길 필요 없이 Front 와 Rear 의 값을 업데이트하면서

인큐와 디큐를 수행할 수 있기 때문에, 모든 처리 복잡도는 O(1) 

 

큐 함수

예외 처리 클래스 Empty 와 Full

초기화하는 __init__() 함수

추가한 데이터 개수를 알아내는 __len__()

큐가 비어 있는지를 판단하는 is_empty() 함수

큐가 가득 차 있는지를 판단하는 is_full() 함수

 

from typing import Any

class FixedQueue:
    
    class Empty(Exception):
        pass # Empty 예외 처리

    class Full(Exception):
        pass # Full 예외 처리

    def __init__(self, capacity: int) -> None:
        self.no = 0                     # 현재 데이터 개수 
        self.front = 0                  # 맨 앞 원소 커서 
        self.rear = 0                   # 맨 끝 원소 커서
        self.capacity = capacity        # 큐의 크기 
        self.que = [None] * capacity    # 큐의 본체 

    def __len__(self) -> int:
        return self.no # 큐에 있는 모든 데이터 개수 반환
    
    def is_empty(self) -> bool:
        return self.no <= 0 # 큐가 비어 있는지 판단
    
    def is_full(self) -> bool:
        return self.no >= self.capacity # 큐가 가득차 있는지 판단
        
# que 큐의 배열로서 밀어 넣는 데이터를 저장하는 list 형 배열
# capacity 큐의 최대 크기를 나타내는 int 형 정수, 배열 que 의 원소 수와 일치
# front 큐에 넣은 데이터 중에 가장 처음에 넣은 맨 앞 원소의 인덱스
# rear 가장 마지막에 넣은 맨 끝 원소의 바로 다음 인덱스, 다음에 인큐할 때 데이터를 저장하는 원소의 인덱스
# no 큐에 쌓여 있는 데이터 개수를 나타내는 int 형 정수, 변수 front 와 rear 의 값이 같을 경우
#    큐가 비어 있는지 가득 차 있는지 구분이 필요하기 떄문에 no 가 필요하다 
#    큐가 비어 있는 경우 no == 0, 가득 차 있는 경우 no == capacity

 

데이터를 넣는 enque() 함수

def enque(self, x: Any) -> None:
    if self.is_full():
            raise FixedQueue.Full # 예외 처리
    # rear 에 데이터를 저장하고 rear, no +1 
    self.que[self.rear] = x
        self.rear += 1
        self.no += 1
        # rear 까지 차 있으면 rear 를 인덱스 0 으로 되돌림 
        if self.rear == self.capacity:
            self.rear = 0

 

데이터를 꺼내는 deque() 함수

def deque(self) -> None:
    if self.is_empty():
        raise FixedQueue.Empty # 예외 처리
    # Front 에서 x 를 꺼내고 front ++ no -- 
    x = self.que[self.front]
    self.front += 1
    self.no -= 1
    # Front 의 값이 Capacity 와 같은 경우
    # index 를 0 으로 되돌려서 다음 디큐 예비
    if self.front == self.capacity:
        self.front = 0
    return x

 

데이터를 들여다보는 peek() 함수

검색하는 find() 함수

데이터 개수를 세는 count() 함수

데이터가 포함되어 있는지를 판단하는 __contains__() 함수

큐의 전체 원소를 삭제하는 clear() 함수

큐의 전체 데이터를 출력하는 dump() 함수 # 맨 앞부터 맨 끝 쪽으로 순서대로 출력

# peek() 함수
def peek(self) -> Any
	if self.is_empty():
    		raise FixedQueue.Empty # 비어 있는 경우 예외 처리
	return self.que[self.front]
    
# find() 함수
def find(self, value: Any) -> Any
	for i in range(self.no):
            idx = ( i + self.front ) % self.capacity
            if self.que[idx] == value: # 검색 성공 
                return idx 
    return -1	# 검색 실패 
    
# count() 함수
def count(self, value: Any) -> int:
	c = 0
    	for i in range(self.no): # 큐 데이터 선형 검색
    		idx = ( i + self.front ) % self.capacity
	        if self.que[idx] == value: # 검색 성공 
    	    	c += 1 
	    return c
    
# __contains()__ 함수
def __contains__(self, value: Any) -> bool:
	return self.count(value)
    
# clear() 함수
def clear(self) -> None:
	self.no = self.front = self.rear = 0
    
def dump(self) -> None:
	if self.is_empty(): # 비어 있음
    	print(" Empty Queue ")
    else:
    	for i in range(self.no):
        	print(self.que[(i + self.front) % self.capacity], end = ' ')
    	print()

 

큐를 사용한 문제 해결

* BFS (너비 우선 탐색) - 큐를 사용하여 현재 레벨의 노드를 모두 탐색하고, 다음 레벨의 노드를 큐에 추가

* 레벨 순회 (Level Order Traversal) - 트리의 모든 노드를 레벨 순서대로 탐색하는 방법

* 미로 탐색 - 미로에서 출구를 찾기 위해 BFS 사용, 큐를 사용하여 각 위치를 탐색하여 최단 경로 계산 

 요 부분은 추가 공부하기

 

스택은 https://helloahram.tistory.com/entry/TIL-%EC%8A%A4%ED%83%9D-Stack