데이터 구조 및 알고리즘: 대기열

대기열은 줄을 서서 기다리는 것과 같습니다.



여기서 첫 번째 사람에게 가장 높은 우선 순위가 부여됩니다[FIFO: First inter first out] . 먼저 도착한 사람이 먼저 나옵니다(대기열에서 빼기).




또한 마지막에 사람이 추가됩니다(Enqueue).





이제 Linked List에서 Enqueue & Dequeue가 필요한 위치를 알아봅시다.





오른쪽에서 제거하면 O(n)이 발생합니다.
Linked List의 마지막 노드를 삭제하려면 헤드가 비어 있는지 확인해야 합니다. 비어 있지 않으면 비어 있는지 다음 헤드를 확인하십시오. head next가 비어 있으면 head를 해제하고 그렇지 않으면 목록의 두 번째 마지막 노드로 이동합니다. 그런 다음 마지막 두 번째 노드 다음 노드를 NULL로 연결하고 마지막 노드를 삭제합니다.



그러나 다시 추가하는 것은 단지 O(1)입니다.



다시 말하지만 왼쪽/처음에서 제거하는 것은 노드를 추가하기 때문에 O(1)입니다.


또한 다시 추가하는 것은 O(1)



따라서 O(n) [Dequeue]를 사용하기 때문에 마지막 노드에서 노드를 제거하고 싶지 않지만 O(1) [Enqueue]이기 때문에 노드를 추가할 수 있습니다.

다시,
목록의 시작 부분에는 O(1) 이 필요하기 때문에 둘 다 제거하고 추가할 수 있습니다.

목록 O(1) 의 마지막 항목에서 추가할 것이므로 이제 첫 번째 O(1)에서 제거합니다.

따라서 오른쪽 끝에서 대기열에 넣기(마지막) 및 왼쪽 끝에서 대기열에서 빼기(시작)

Linked List와 비교하여 Queue를 다음과 같이 가정합니다.



건설자

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

class Queue:
    def __init__(self, value):
        new_node = Node(value) #creating a node
        #pointing the first & last to the new node
        self.first = new_node 
        self.last = new_node
        self.length = 1

    #Prints the queue untill it finds None
    def print_queue(self):
        temp = self.first
        while temp is not None:
            print(temp.value)
            temp = temp.next

전체 코드는 다음과 같습니다.

#Creating a node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Queue:
    def __init__(self, value):
        new_node = Node(value) #creating a node
        #pointing the first & last to the new node
        self.first = new_node 
        self.last = new_node
        self.length = 1

    #Prints the queue untill it finds None
    def print_queue(self):
        temp = self.first
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creates a queue with node 4
my_queue = Queue(4)

my_queue.print_queue()

대기열에 넣기
마지막으로 노드 추가
이것

이에



사례 1:
대기열에 아무것도 없을 때.








사례 2:
이미 목록에 항목이 있습니다.







따라서 이에 대한 코드는

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


class Queue:
    def __init__(self, value):
        new_node = Node(value)
        self.first = new_node
        self.last = new_node
        self.length = 1

    def print_queue(self):
        temp = self.first
        while temp is not None:
            print(temp.value)
            temp = temp.next
    #Adding a node at last of queue    
    def enqueue(self, value):
        new_node = Node(value)
        #If there are no nodes in the queue
        if self.first is None:
            self.first = new_node
            self.last = new_node
        #If there are nodes in the queue    
        else:
            self.last.next = new_node
            self.last = new_node
        self.length += 1

#Creating a queue with node 1
my_queue = Queue(1)
#Adding a node 2 at the last of queue
my_queue.enqueue(2)

my_queue.print_queue()

대기열에서 빼기
연결된 목록의 시작 부분에서 제거


이에



사례 1:
대기열에 아무것도 없을 때



사례 2:
노드가 1개일 때






사례 3:
대기열에 노드가 많을 때




그래서 전체 코드는

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


class Queue:
    def __init__(self, value):
        new_node = Node(value)
        self.first = new_node
        self.last = new_node
        self.length = 1

    def print_queue(self):
        temp = self.first
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def enqueue(self, value):
        new_node = Node(value)
        if self.first is None:
            self.first = new_node
            self.last = new_node
        else:
            self.last.next = new_node
            self.last = new_node
        self.length += 1
        return True

    def dequeue(self):
        #When we have no nodes in the queue
        if self.length == 0:
            return None
        temp = self.first
        #When we have only one node in the queue
        if self.length == 1:
            self.first = None
            self.last = None
        #When we have more than one node in the queue
        else:
            self.first = self.first.next
            temp.next = None
        self.length -= 1
        return temp


my_queue = Queue(1)
my_queue.enqueue(2)

# (2) Items - Returns 2 Node
print(my_queue.dequeue())
# (1) Item -  Returns 1 Node
print(my_queue.dequeue())
# (0) Items - Returns None
print(my_queue.dequeue())