큐 (queue)

오늘은 큐를 알아보자.. 더이상 쓸 짤이 없다...

 

 

 

는 훼이크

 

 

도와줘요 스피드웨건..!

 

 

지금부터 큐를 설멍해보지..!

 

 

 

 

 

 

 

 

 

 

큐 알아보기 

큐는 가장먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 FIFO 이다.

FIFO (Frist in Frist out)  : 가장먼저 넣은 데이터는 가장 먼저 꺼낸다 .

 

용어를 알아보자.

1. 큐에 데이터를 추가하는작업을 : 인큐 (enqueue)
2. 데이터를 꺼내는 작업을 : 디큐 (dequeue)
3. 데이터를 꺼내는 쪽을 : 프론트(front)
4. 데이터를 넣는 쪽을 : 리어(rear)

이걸로 끝낸다..!

 

링 버퍼로 큐 구현하기 

이번에는 디큐할 때 배열 안의 원소를 옮기지 않는 큐를 구현해보겠다. 

이럴 때 사용하는 자료구조가 링 버퍼 이다.

 

이거시 링 버퍼이다..!

어떤 원소가 맨 앞 원소이고, 맨 끝 원소인지 식별하는 변수가 front와 rear이다.

여기에서 프론트와 리어는 논리적인 데디터 순서일 뿐 배열의 물리적 원소의 순서는 아니다. 

프론트 : 맨 앞 원소의 인덱스 
리어 : 맨 끝 원소 바로 뒤의 인덱스(다음 인큐되는 데이터가 저장되는 위치)

 

인큐와 디큐를 수행하면 front, rear의 값은 변한다. 

 

 

예를 들어 size = 6  사이즈인 큐가 있다고 가정하면 

p = 16인 rear

k = 10인 front 

 

a를 추가한다고하면 

a를 추가하고 rear 는 17이 된다 

 

k를 뺀다고 하면 

k를 빼내고 front는 11이 된다 

 

 

 

이런식으로 링버퍼로 큐를 구현하면 원소를 옮길 필요 없이

front, rear의 값을 업데이트 하는 것만으로 인큐와 디큐를 수행할 수 있음 모든 처리의 복잡도는 O(1)

 

 

샷다 내려!

 

 

# 고정 길이 큐 클래스 FixedQueue 구현하기


from typing import Any


class FixedQueue:
    
    class Empty(Exception):
        pass 
    
    class Full(Exception):
        pass 
    
    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

 

 

예외 처리 클래스  [ Empty, Full ]

비어 있는 큐에 deque( ), peek( ) 함수를 호출할 때 내보내는 예외 처리는 Empty 클래스이고.

가득 차 있는 큐에 enque( ) 함수를 호출할 때 내보내는 예외처리 Full

 

초기화하는  __init__( ) 함수 

__init__( ) 함수는 큐 배열을 생성하는 등의 준비 작업을 하며 다음과 같이 5개의 변수에 값을 설정함 

1. que : 큐의 배열로서 밀어 넣는 데이터를 저장하는 list형 배열이다.
2. capacity : 큐의 최대 크기를 나타내는 int형 정수이다. 이 값은 배열 que의 원소 수와 일치함
3. front, rear : 맨 앞의 원소, 맨 끝의 원소를 나타내는 인덱스 
4. no : 큐에 쌓여있는 데이터 개수를 나타내는 int형 정수이기 때문 

 

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

__len__( ) 함수는 큐에 추가한 데이터 개수를 반환한다. no의 값 그대로 반환함 

 

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

큐가 비어 있는지 판단하는 is_full 함수  

 

데이터를 넣는 enque( ) 함수 

enque( ) 함수는 큐에 데이터를 인큐한다. 하지만 큐가 가득 차서 인큐 할 수 없는 경우 예외처리 보냄 

 

 

데이터를 넣는 deque( ) 함수

 deque( ) 함수는 큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환 

 

 

나머지는 스택과 똑같아서 코드를 보면 바로 이해가 될꺼다 바로 이거닷..!

  def enque(self, x: Any) -> None:
        """데이터 x를 인큐"""
        if self.is_full():
            raise FixedQueue.Full  # 큐가 가득 차 있는 예외 처리 발생     
        
        self.que[self.rear] = x  
        self.rear += 1
        self.no += 1
        
        if self.rear == self.capacity:
            self.rear = 0 
            
    def deque(self) -> Any:
        """데이터를 디큐"""
        if self.is_empty():
            raise FixedQueue.Empty
        
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        
        if self.front == self.capacity:
            self.front = 0
        
        return x 
    
    def peek(self) -> Any:
        """큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)"""
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]
    
    def find(self, value: Any) -> Any:
        """큐에서 value를 찾아 인덱스 반환"""
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                return idx 
        return -1 
    
    def count(self, value: Any) -> Any:
        """큐에서 value를 찾아 개수 반환"""
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value:
                c += 1
        return c
    
    def __contains__(self, value: Any) -> bool:
        """큐에 value가 있는지 판단"""
        return self.count(value)
    
    def clear(self) -> None:
        """모든 데이터 지움"""
        self.no = self.front = self.rear = 0
        
    def dump(self) -> None:
        """모든 데이터를 맨 앞부터 맨 끝 순으로 출력"""
        if self.is_empty():
            print("큐가 비어 있음")
        else:
            for i in range(self.no):
                print(self.que[(i + self.front) % self.capacity], end='')
            print()