Question

"""linkedQueue.py implements LinkedQueue"""

class Node(object):
def __init__(self, e, nextNode):
self.item, self.next = (e, nextNode)
def __str__(self): return str(self.item)
  
class LinkedQueue(object):
def __init__(self): #O(1)
self._front, self._rear =(None, None)
self._size = 0
  
def enqueue(self, e): # add e to the rear of the queue.
newTail = Node(e, None)
if self.isEmpty():
self._front = newTail
else:
self._rear.next = newTail
self._rear = newTail
self._size += 1

def front(self): # raise exception if it is empty, otherwise return front element
if self.isEmpty():
raise Exception("call LinkedQueue.front() with an empty queue")
return self._front.item

""" raise exception if it is empty, otherwise remove and return
the front element"""
def dequeue(self):
if self.isEmpty():
raise Exception("call LinkedQueue.dequeue() with an empty queue")

data = self._front.item
self._front = self._front.next
if self._size == 1: #only one node, after dequeue it, the queue is empty
self._rear = None
self._size -= 1

def isEmpty(self):
return self._size == 0
def __len__(self) :
return self._size
  
def __str__(self):
  
  
"""def clear(self):
_____________"""

def test(QueueType):
q = QueueType()
for i in range(5):
q.enqueue(10*(i+1))
print(q)
for i in range(3):
print("dequeue: ", q.dequeue())
print (q)

def main():
test(ListQueue)

if __name__ == '__main__':
main()
  

Answer 1

Here is the completed code for this problem. Since you did not mention anything specific, I have completed the str and clear methods, also fixed dequeue method, and the whole indentation of the code. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

Note: Please maintain proper code spacing (indentation), just copy the code part and paste it in your compiler/IDE directly, no modifications required.

EDIT: Added time complexities of all methods. Every method except __str__ has a time complexity of O(1) or constant time. str has O(n) time as it needs to traverse the entire queue to create a string of all elements. For some reason I'm unable to reply via comments. Some technical error. So I'm responding here.

#code

class Node(object):
    def __init__(self, e, nextNode): #time complexity: O(1)
        self.item, self.next = (e, nextNode)

    def __str__(self): #time complexity: O(1)
        return str(self.item)


class LinkedQueue(object):
    def __init__(self): #time complexity: O(1)
        self._front, self._rear = (None, None)
        self._size = 0

    def enqueue(self, e): #time complexity: O(1)
        newTail = Node(e, None)
        if self.isEmpty():
            self._front = newTail
        else:
            self._rear.next = newTail
        self._rear = newTail
        self._size += 1

    def front(self): #time complexity: O(1)
        if self.isEmpty():
            raise Exception("call LinkedQueue.front() with an empty queue")
        return self._front.item

    def dequeue(self): #time complexity: O(1)
        if self.isEmpty():
            raise Exception("call LinkedQueue.dequeue() with an empty queue")
        data = self._front.item
        self._front = self._front.next
        if self._size == 1:
            self._rear = None
        self._size -= 1
        return data  # returning removed data

    def isEmpty(self): #time complexity: O(1)
        return self._size == 0

    def __len__(self): #time complexity: O(1)
        return self._size

    def __str__(self): #time complexity: O(n)
        # creating an empty string
        data = ''
        node = self._front  # taking reference to first node
        while node != None:  # looping until node is None
            data += str(node.item)  # appending data of node to data string
            node = node.next  # advancing to next node
            if node != None:  # if it is not empty
                data += ", "  # appending a comma and space
        return data

    def clear(self): #time complexity: O(1)
        self._front, self._rear = (None, None)  # resetting front, rear
        self._size = 0  # resetting size


def test(QueueType):
    q = QueueType()
    for i in range(5):
        q.enqueue(10 * (i + 1))
    print(q)
    for i in range(3):
        print("dequeue: ", q.dequeue())
    print(q)


def main():
    test(LinkedQueue)  # testing LinkedQueue


if __name__ == '__main__':
    main()

#output

10, 20, 30, 40, 50
dequeue:  10
dequeue:  20
dequeue:  30
40, 50