큐(Queue)란?

한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조
FIFO(First In First Out) 먼저 넣은게 먼저 나온다.
입력과 삭제가 다른 위치에서 된다.

순서대로 처리해야 할 때 사용

큐 파이썬으로 구현하기

class Node:
    def __init__(self,val,next=None ):
        self.val = val
        self.next = next

class Queue:
    def __init__(self):
        self.front = None

    def push(self, value): 
        if not self.front:
            self.front = Node(value, None)
            return

        node = self.front   #front가 맨처음 들어온걸 가르킴
        while node.next:	#삽입시 next를 탐색하여 끝에다 추가
            node = node.next 
        node.next = Node(value, None)

    def pop(self):
        if not self.front:
            return None

        node = self.front
        self.front = self.front.next
        return node.item

    def is_empty(self):
        return self.front is None

원형 큐란?

선형 큐의 문제 점인 삽입과 삭제를 반복하다 보면 앞에 있는 인덱스가 비어있음에도 꽉 차 있다고 생각하는데 이를 해결하기 위해 삭제시 뒤에 있는 요소들을 한칸씩 땡겨야하는 작업이 필요한데 원형 큐에서는 front와 rear가 삽입 삭제시 움직이며 이런 문제를 해결한다.

작동방식

처음에는 front와 rear가 같은 인덱스를 가르킨다
삽입시에 rear가 움직이며 데이터를 삽입하고
삭제시에 front가 움직이며 데이터가 삭제된다.

원형큐 파이썬으로 구현하기

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None


class Circulrator_Queue:
    def __init__(self):
        self.front = None
        self.rear = None 

    def isEmpty(self):
        if self.front == self.rear:
            return True
        return False

    def enQueue(self, val):
        if not self.front:
            node = Node(val)
            self.front = node  
            self.rear = node	#front와 rear가 같은 노드를 보고있다.

        self.rear.next = Node(val) 	#rear.next에 만들고
        self.rear = self.rear.next  #rear 옮기고
        
    def deQueue(self):
        if self.front == None:
            return None
        data = self.front.val
        self.front = self.front.next	#front에 front.next 바꿔주기

        if self.front == None:
            self.rear = None
            return data
        return data

이미지 출처: https://www.codingem.com/what-is-a-fifo-queue/
https://yjg-lab.tistory.com/115