Итеративные башни Ханоя используют очередь, но обратная функция говорит, что она не определена - PullRequest
Новая
       30

Итеративные башни Ханоя используют очередь, но обратная функция говорит, что она не определена

1 голос
/ 14 марта 2019 
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

    def __str__(self):
        return "Node({})".format(self.value)

    __repr__ = __str__


class Queue:
    def __init__(self):
        #Constructor take head and tail
        self.head=None
        self.tail=None

    def __str__(self):
        #proper format
        temp=self.head
        out=[]
        while temp:
            out.append(str(temp.value))
            temp=temp.next
        out=' '.join(out)
        return ('Head:{}\nTail:{}\nQueue:{}'.format(self.head,self.tail,out))

    __repr__=__str__

    def isEmpty(self):
        #check if the queue is empty
        return (self.head == None)
    def len(self):
        #check the length of queue
        current = self.head
        len = 0
        while current != None:
            len += 1
            current = current.next

        return len

    def enqueue(self, value):
        #add a node to the end of queue
        node = Node(value)
        if self.isEmpty():
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    def dequeue(self):
        #delete a node from the beginning of queue
        if self.isEmpty():
            return 'Queue is empty'
        elif (self.head == self.tail):
            pop = self.head.value
            self.head = None
            self.tail = None
            return pop
        else:
            popped = self.head.value
            self.head = self.head.next
            return popped

    def peek(self):
        #show the first node
        return self.head.value
class QueueTower:
    def __init__(self, numDisks, A=Queue(), B=Queue(), C= Queue()):
        self.numDisks = numDisks
        self.A = Queue()
        self.B = Queue()
        self.C = Queue()
        for i in (numDisks, 0, -1):
            self.A.enqueue(i)

    def reversequeue(q):
        #reverse the queue without using stack
        if q.isEmpty() == False:
            data = q.peek()
            q.dequeue()
            q = reversequeue(q)  #recurssion
            q.enqueue(data)
            return q
        return Queue()

    def validMove(self, a, b):
        if not a.len():
            c = reversequeue(b)
            a.enqueue(c.dequeue())
        elif not b.len():
            d = reversequeue(a)
            b.enqueue(d.dequeue())
        elif int(a.peek()) > int(b.peek()):
            e = reversequeue(b)
            a.enqueue(e.dequeue())
        else:
            f = reversequeue(a)
            b.enqueue(f.dequeue())


    def hanoi(self, n):
        if n%2 == 0:
            self.B, self.C = self.C, self.B
        move = 2**n
        for i in range(1, move):
            if i%3==1:
                self.validMove(self.A, self.C)
            if i%3==2:
                self.validMove(self.A, self.B)
            if i%3==0:
                self.validMove(self.B, self.C)
        print("rod " + str(self.A)+ " has " + str(self.A.len()), "rod B " + str(self.B.len()), "rod C "+ str(self.C.len()))
        print("move needed is " + str(move-1))
tower1 = QueueTower(3)
tower1.hanoi(3)

Я проверил, чтобы кодировать функцию reversequeue. Это хорошо работает для другого примера, но я не могу заставить его работать для этого. Возвращает, что обратная очередь не определена. Я поместил функцию внутри класса. Пожалуйста, помогите мне понять проблему.

Должен ли я поместить функцию в класс Queue. Что мне делать в этой ситуации?

Большое спасибо за помощь.

1 Ответ

1 голос
/ 14 марта 2019

Вы забыли себя: 

class QueueTower:
    def __init__(self, numDisks, A=Queue(), B=Queue(), C= Queue()):
        self.numDisks = numDisks
        self.A = Queue()
        self.B = Queue()
        self.C = Queue()
        for i in (numDisks, 0, -1):
            self.A.enqueue(i)

    def reversequeue(self, q):
        #reverse the queue without using stack
        if q.isEmpty() == False:
            data = q.peek()
            q.dequeue()
            q = self.reversequeue(q)  #recurssion
            q.enqueue(data)
            return q
        return Queue()

    def validMove(self, a, b):
        if not a.len():
            c = self.reversequeue(b)
            a.enqueue(c.dequeue())
            # code continues
...