Question

Instructions:

SLLQueue (13 pts)

● Using the three properties below, implement the

queue interface using the SLLNode class from Lab 2:

○ head_node → SLLNode object or None

○ tail_node → SLLNode object or None

○ size → int, keep track of queue size

● Implement enqueue( ), dequeue( ), front( )

● Use SLLNode methods:

get_item( ), set_item( ), get_next( ), set_next( )

● (5 pts) In enqueue(item):

○ Add new SLLNode (with item) after tail_node

○ Update tail_node and size properties

○ If first item, update head_node property too

● (6 pts) In dequeue( ):

○ If empty, raise Exception('Empty queue: cannot dequeue')

○ Remove head node and return its item

○ Remove any links from old head node

○ Update head_node and size properties

○ If queue becomes empty, reset head_node, tail_node

● (2 pts) In front( ):

○ If empty, raise Exception(Empty queue: no front')

○ Return head node’s item

Code:

class SLLQueue:
   def __init__(self):
       # NOTE: DO NOT EDIT THIS CODE
       # constructor: set properties head_node, tail_node, size
       self.head_node = None
       self.tail_node = None
       self.size = 0

   def __repr__(self):
       # NOTE: DO NOT EDIT THIS CODE
       # string representation of SLLQueue object
       display = []
       node = self.head_node
       while node != None:
           display.append(str(node.get_item()))
           node = node.get_next()
       display = ', '.join(display)
       return 'front [' + display + ']'

   def is_empty(self):
       # NOTE: DO NOT EDIT THIS CODE
       # check if queue is empty
       return self.size == 0

   def enqueue(self,item):
       # TODO: Write your code here...
       # TODO: add new node (with item) after tail_node
       # TODO: update tail_node and size properties
       # TODO: if this is the first node added, update head_node too
      
       pass # TODO: remove this line
      
   def dequeue(self):
       # TODO: Write your code here...
       # TODO: if empty, raise Exception('Empty queue: cannot dequeue')
       # TODO: remove head_node and return its item
       # TODO: remove any links from old head_node (Hint: set to None)
       # TODO: update head_node and size properties
       # TODO: if queue becomes empty, reset head_node and tail_node
      
       pass # TODO: remove this line

   def front(self):
       # TODO: Write your code here...
       # TODO: if empty, raise Exception('Empty queue: no front')
       # TODO: return head_node's item

       pass # TODO: remove this line

Answer 1

# SLLNode class 
class SLLNode:
    def __init__(self,item=None,next_node=None):
        self.item = item
        self.next_node = next_node
    
    def set_item(self,item):
        self.item = item0
    
    def get_item(self):
        return self.item
    
    def get_next(self):
        return self.next_node
    
    def set_next(self,new_node):
        self.next_node = new_node

# SLLQueue class        
class SLLQueue:
    def __init__(self):
       # constructor: set properties head_node, tail_node, size
       self.head_node = None
       self.tail_node = None
       self.size = 0

    def __repr__(self):
       # string representation of SLLQueue object
       display = []
       node = self.head_node
       while node != None:
           display.append(str(node.get_item()))
           node = node.get_next()
       display = ', '.join(display)
       return 'front [' + display + ']'

    def is_empty(self):
       # check if queue is empty
       return self.size == 0

    def enqueue(self,item):
       # add new node (with item) after tail_node
        new_item = SLLNode(item)
        if self.head_node is None: 
            # if this is the first node added, update head_node
            # update tail_node and size properties
            self.head_node = new_item
            self.tail_node = new_item
            self.size = 1
        else:
            self.tail_node.set_next(new_item) # add new node (with item) after tail_node
            self.tail_node = new_item
            self.size = self.size + 1
      
    def dequeue(self):
        if self.is_empty():
            # if empty, raise Exception('Empty queue: cannot dequeue')
            return "Empty queue: cannot dequeue"
        else:
            current = self.head_node
            self.head_node = self.head_node.get_next() # remove and update head_node
            current.set_next(None) # remove any links from old head_node
            self.size = self.size - 1 # update size properties
            if self.is_empty():
                self.tail_node = None # if queue becomes empty, reset tail_node
                self.head_node = None # reset head_node
            return current.get_item() # return the removed item

    def front(self):
        if self.is_empty():
            # if empty, raise Exception('Empty queue: no front')
            return "Empty queue: no front" 
        else:
            return self.head_node.get_item() # return head_node's item

# Testing code           
q = SLLQueue()

q.enqueue("User1")
q.enqueue("User2")
q.enqueue("User3")
q.enqueue("User4")
q.enqueue("User5")
print(q.__repr__())
print(q.dequeue())
print(q.__repr__())
print(q.front())

Hope this will help you !!