[알고리즘] 큐 - 먼저하면 먼저, 늦게하면 늦게

큐(Queue)

먼저 집어 넣은 데이터가 먼저 나온다

First In, First Out: FIFO 구조로 저장하는 자료구조

전단(Front), 후단(Rear)이 있다.

 

삽입(Enqueue)

뒤에 집어 넣는거다, 그럼 후단이 새로 들어온애로 바뀌겠지

 

삭제(Dequeue)

제일 먼저 들어온 녀석을 삭제하고, 그 다음 녀석이 전단이 된다.

 

 

배열로 큐를 구현할 때 문제점

앞의 것을 제거하면 나머지를 앞으로 땡겨와야한다.

그래서 배열에 큐 잘 안쓴다

 

 

순환 큐

배열의 끝과 시작이 이어진 것처럼 전단과 후단 관리

 

문제점

전단과 후단이 같은 위치면 비었나, 가득찼나?

 

해결 방법

1. 큐 배열 생성할 때 실제 용량보다 1만큼 크게 만들어
2. 전단과 후단 사이를 비운다
   • 전단과 후단이 같으면 빈 상태
   • 후단이 전단보다 1 작으면 가득찬 상태

 

연결 큐

연결 리스트 기반의 큐

성능은 순환 큐보다 느리지만, 공백/포화 상태 관리가 필요 없다.

연결 리스트처럼 작동한다

 

 

큐 알고리즘 구현

class Queue:
    def __init__(self):
        self.entries = []
        self.length = 0
        self.front = 0

    def __str__(self):
        printed = '<' + str(self.entries)[1:-1] + '>'
        return printed

    def Enqueue(self, item):
        self.entries.append(item)
        self.length += 1

    def Dequeue(self):
        if self.length == 0 :
            return None
        self.length -= 1
        dequeued = self.entries[self.front]
        self.entries = self.entries[self.front+1:]
        return dequeued


if __name__ == '__main__':
    queue = Queue()
    queue.Dequeue()
    print(queue)               // <>
    queue.Enqueue(100)
    queue.Enqueue(200)
    queue.Enqueue(300)
    queue.Enqueue(400)
    print(queue)               // <100, 200, 300, 400>
    print(queue.Dequeue())     //  100
    print(queue.Dequeue())     //  200
    print(queue)               // <300, 400>