Circular_queue

Circular_queue

배열로 구현이 되지만 배열의 단점을 극복한 것입니다.

원형 큐 또한 큐이기 때문에 선입선출방식입니다.

고정된 크기의 배열로 구현되고 원이기 때문에 수열적 생각도 좋습니다.

활용

*삽입

데이터가 처음 삽입될 때 rear방향으로 삽입됩니다.

데이터가 끝 위치에 다닿으면 다음에는 다시 처음인 0번째 인덱스부터 쌓습니다.

*추출

데이터를 추출할 때도 front방향으로 하나씩 추출됩니다.

*원형 큐의 꽉찬 상태

하나 남은 상태에서 front = rear + 1이라면 꽉찬 상태입니다.

*메서드

isFull() :꽉 찬 상태

isEmnpty(): 비어있는 상태

CODE

class CircularQueue: #원형 큐 구현
    def __init__(self, max_size): #첫 시작은 국룰로 __init__!!, 최대 사이즈를 인자
        self.elements = [None] * (max_size + 1) #인자는 최대 사이즈보다 한 칸 더 갈 수 있디
        self.front = 0 # front부분 0으로 초기화
        self.rear = 0 # rear부분을 0으로 초기화
        self.max_size = max_size + 1 #최대 사이즈의 +1 한 것이 최대 사이즈

    def is_full(self): #다 채워져있을 때
        return (self.rear + 1) % self.max_size == self.front #rear의 한 칸 더 간 게 front와 맞다면 full!!

    def is_empty(self): #비어있을 때
        return self.front == self.rear #front와 rear가 한 공간일 때

    def clear(self): # 비우는 함수(초기화)
        self.front = 0 #front를 0으로 초기화
        self.rear = 0 #rear을 0으로 초기화

    def offer(self, data): #삽입 함수로 data가 인자이다
        if self.is_full(): #만약 full 이라면
            raise RuntimeError("Queue is full") #큐가 다 채워졌다라고 말하기

        self.rear = (self.rear + 1) % self.max_size #rear + 1 =front상태고 다 꽉 찬 상태입니다.
        self.elements[self.rear] = data #rear에 데이터가 있을 겁니다.

    def poll(self): #데이터를 추출하는 함수
        if self.is_empty(): #비어있다면
            raise RuntimeError("Queue is empty") #큐는 비어있다고 호출
        self.front = (self.front + 1) % self.max_size #front가 곧 최대크기
        return self.elements[self.front] # front = 0

    def size(self): #길이
        if self.front <= self.rear: #rear 부분이 인덱스가 더 크다면
            return self.rear - self.front #rear- front로 추출
        return self.max_size - self.front + self.rear #front가 더 길다면 최대 길이 - -front + rear

if __name__ == "__main__": #main.py함수이다
    q = CircularQueue(5) #매번 CicrularQueue를 사용할 수 없기에 q를 이용하여 할당하고 size =5
    for e in range(5): #0~4까지의 숫자 넣기
        print(f"is_full: {q.is_full()}, is_empty:{q.is_empty()}, size: {q.size()}") #꽉 찼는지 확인, 비었는지 확인, 사이즈 확인
        q.offer(e) #숫자 삽입
        print(f"q.offer({e})") # 잘 들어갔나 확인
        print(f"is_full: {q.is_full()}, is_empty: {q.is_empty()}, size:{q.size()}") #다시 한번 꽉 찼는지 확인, 비었는지 확인, 사이즈 확인

    print("-------------------------------") # 줄 방지
    while q.size() > 0: #size가 0보다 크다면
        print(f"is_full: {q.is_full()}, is_empty: {q.is_empty()}, size: {q.size()}")#다시 한번 꽉 찼는지 확인, 비었는지 확인, 사이즈 확인
        print(f"q.poll(): {q.poll()}")#숫자 뻬기