6. 큐

1. 큐

- 선형자료구조

- 먼저 들어간 것이 먼저 나옴(선입선출)

- 은행 고객이나 마트에서 계산을 기다리는 고객에 대한 일의 처리 순서라고 생각하자

2. 큐 ADT

- init(self, size)

- 큐를 초기화 한다

- 큐의 사이즈를 지정한다

- enqueue(self, data)

- 큐에 데이터를 저장한다

- dequeue(self)

- 큐의 첫 데이터를 반환 하고 삭제한다.

- is_full(self)

- 큐가 가득 차 있는지 확인한다

- is_empty(self)

- 큐가 비어 있는지 확인한다

- peek(self)

- 큐의 첫 데이터를 반환 한다.

- count(self)

- 큐에 모든 데이터 수를 반환 한다.

class Queue:
    def __init__(self, size):
        self.list = []
        self.size = size
        self.total = 0

    def enqueue(self, data):
        if self.is_full():
            return False
        self.list.append(data)
        self.total += 1
        return True

    def dequeue(self):
        if self.total:
            return False
        pop_data = self.list.pop(0)
        self.total -= 1
        return pop_data

    def is_full(self):
        if self.list == self.size:
            return True
        return False

    def is_empty(self):
        if self.total == 0:
            return True
        return False

    def peek(self):
        return self.list[0]

    def count(self):
        return self.total

q = Queue(size=5)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
q.enqueue(5)
print(f'front : {q.peek()}')
print(f'dequeue : {q.dequeue()}')
print(f'front : {q.peek()}')
print(f'count: {q.count()}')

---------------------------------------

front : 1
dequeue : 1
front : 2
count: 4

3. 원형 큐

- 직선 큐에서 디큐 되었을 때 디큐 된 데이터 뒤의 요소들을 한 칸 씩 당겨줘야 한다.

- 10000개의 데이터가 있을때 제일 앞의 데이터가 디큐 된다면 9999번의 이동이 발생한다.

- 만약 이동을 시켜주지 않게 된다면 큐에서 사용할 수 있는 공간이 점점 줄어들게 된다.

- 이러한 단점들을 보완하기 위한게 원형 큐다.

- 원형큐는 처음과 끝을 논리적으로 연결시켜 이러한 문제를 해결한다.

- 원형큐는 공백, 포화 상태를 쉽게 알기 위해서 자리를 하나 비워둔다. 즉 데이터 저장 공간의 수가 4개가 필요하다면 실제로는 5개가 필요하다

- 포화 상태는 (rear + 1) % size = front, 공백 상태는 front == rear 이다

class CircularQueue:
    def __init__(self, size):
        self.list = [None] * (size + 1)
        self.front = 0
        self.rear = 0
        self.size = size + 1

    def enqueue(self, data):
        if self.is_full():
            return False
        self.list[self.rear] = data
        self.rear = (self.rear + 1) % self.size
        return True

    def dequeue(self):
        if self.is_empty():
            return False
        self.list[self.front] = None
        self.front = (self.front + 1) % self.size
        return True

    def is_full(self):
        if (self.rear + 1) % self.size == self.front:
            return True
        return False

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

    def peek(self):
        if self.is_empty():
            return False
        return self.list[self.front]


cq = CircularQueue(4)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(2)
cq.enqueue(2)
print(f'is_full: {cq.is_full()}')
print(f'peek: {cq.peek()}')
cq.dequeue()
cq.dequeue()
cq.dequeue()
cq.dequeue()
print(f'is_empty: {cq.is_empty()}')

------------------------------------------

is_full: True
peek: 1
is_empty: True

4. 큐(Linked List)

- 직선 큐의 문제점을 해결 하기 위한 방법에는 큐를 링크드 리스트로 만들면 메모리 문제를 해결할 수 있다.

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


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

    def enqueue(self, data):
        new_node = Node(data)
        if not self.front:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node
        self.total += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return False
        self.front = self.front.next
        self.total -= 1
        return True

    def is_empty(self):
        if not self.total:
            return True
        return False

    def peek(self):
        if self.is_empty():
            return False
        return self.front.data

    def count(self):
        return self.total


q = Queue()
print(f'is_empty : {q.is_empty()}')
q.enqueue(1)
print(f'peek : {q.peek()}')
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
print(f'is_empty : {q.is_empty()}')
print(f'count : {q.count()}')
q.dequeue()
print(f'peek : {q.peek()}')
q.dequeue()
q.dequeue()
q.dequeue()
print(f'count : {q.count()}')

------------------------------------

is_empty : True
peek : 1
is_empty : False
count : 4
peek : 2
count : 0