We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Queue using Two Stacks
  2. Discussions

Queue using Two Stacks

  • robbie_chambers1
     + 0 comments

    I am quite new to coding so I just used the knowledge on linked lists i gained from the previous exercise. This passed all the tests but could someone help me diagnose the complexity of my solution:

    # Enter your code here. Read input from STDIN. Print output to STDOUT
class LinkedListNode():
    data: int = None
    next: 'LinkedListNode' = None


class Queue():
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, x):
        final_element = LinkedListNode()
        final_element.data = x
        # Handle empty queue case
        if not self.head:
            self.head = final_element
            if not self.tail:
                self.tail = final_element
        else:
            self.tail.next = final_element
            self.tail = self.tail.next

    def dequeue(self):
        # Handle empty queue case
        if not self.head:
            return None
        dequeue_value = self.head.data
        self.head = self.head.next
        # If queue is empty, remove tail
        if self.head is None:
            self.tail = None
        return dequeue_value

    def handle_query(self, query):
        query_type = query[0]
        # Enqueue query
        if query_type == 1:
            x = query[1]
            self.enqueue(x)
        # Dequeue query
        elif query_type == 2:
            return self.dequeue()
        # Print query
        elif query_type == 3:
            if self.head.data:
                print(self.head.data)
            else:
                print(None)

if __name__ == "__main__":
    q = int(input())
    queue = Queue()
    for _ in range(q):
        query = list(map(int, input().split()))
        queue.handle_query(query)