Python Круговая очередь с использованием связанного списка - PullRequest
Новая
       3

Python Круговая очередь с использованием связанного списка

0 голосов
/ 20 января 2020

Я пытаюсь реализовать циклическую очередь (без ограничения буфера) в python. Когда я звоню display после enqueue, это не работает. Тем не менее, он работает нормально, когда вызывается в других случаях.

Его реализация аналогична функции get_size, которая работает, как и ожидалось.

Ниже приведена реализация: 

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

class LinkedCircularQueue(object):
    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail

    def enqueue(self, item):
        """
        Add the node to the back of the queue and set its next pointer to
        self.head
        """
        if self.tail is not None:
            self.tail.next = item
        else:
            self.head = item

        self.tail = item
        item.next = self.head
        return self.tail.value

    def dequeue(self):
        """
        Remove the oldest node (from the front) by copying the value and
        making the preceding node as the new head
        """
        if self.head is not None:
            deleted = self.head.value
            self.head = self.head.next
        else:
            deleted = None
            print("Circular queue is empty !!")
        return deleted

    def display(self):
        """
        Traverse from front to back and show elements
        """
        front = self.head
        back  = self.tail
        if front is not None and back is not None:
            while back.next != front:
                print(front.value, end="  ")
                front = front.next
        else:
            print("Circular queue is empty !!")

    def get_size(self):
        """
        Traverse from front to back and count elements
        """
        size = 0
        if self.head is not None and self.tail is not None:
            while self.tail.next != self.head:
                size += 1
                self.head = self.head.next
        return size

    def peek_front(self):
        front = self.head
        return front.value

    def peek_back(self):
        back = self.tail
        return back.value

    def is_empty(self):
        first = self.head
        last  = self.tail
        if first is None and last is None:
            return True
        else:
            return False

def main():
    # Initialize elements
    element1 = Node(1)
    element2 = Node(2)
    element3 = Node(3)
    element4 = Node(4)
    element5 = Node(5)
    linked_circular_queue = LinkedCircularQueue()

    # Initial tests
    linked_circular_queue.display()
    print(linked_circular_queue.is_empty())
    print(linked_circular_queue.get_size())
    print()

    # Test enqueue
    linked_circular_queue.enqueue(element5)
    linked_circular_queue.enqueue(element3)
    linked_circular_queue.enqueue(element1)
    linked_circular_queue.enqueue(element4)
    linked_circular_queue.enqueue(element2)
    linked_circular_queue.display()             # doesn't work
    print()

    # Test dequeue
    linked_circular_queue.dequeue()
    linked_circular_queue.dequeue()
    linked_circular_queue.display()
    print()

    # Test peek
    print(linked_circular_queue.peek_front())
    print(linked_circular_queue.peek_back())
    print()

    # Final tests
    print(linked_circular_queue.is_empty())
    print(linked_circular_queue.get_size())

if __name__ == '__main__':
    main()

Токовый выход: 

Circular queue is empty !!
True
0


1  4  2  
1
2

False
3

Ожидаемый результат: 

Circular queue is empty !!
True
0

5  3  1  4  2

1  4  2  
1
2

False
3

1 Ответ

0 голосов
/ 20 января 2020

Измените while l oop с функции display на следующее: 

while back != front:
    print(front.value, end=" ")
    front = front.next
print(back.value)        # print(front.value) also works
...