For this lab, we will be learning how to build and use linear data structures like stacks andqueues. Stacks and queues are very common data structures in the CS world. In this lab, we willfocus on implementing these data structures using the linked list data structure as a base.Core Tasks:1.Write the queue class.2.Write the stack class3.Test your classes with the provided main function.Program Requirements:Task 1: Write the queue class.For task 1, you will need to write a Queue class. The class is detailed as follows:●__init__(self, capacity) → NoneoComplexity: O(1)oValid Input: An integer in (0, ∞]. Use a default, valid capacity on invalid input.oThis is the constructor for the class. You will need to store the following here:▪The head pointer▪The tail pointer▪A variable maxSize▪A variable currentSize▪Any other instance variables you want.●enqueue(self, ticket) → booleanoComplexity: O(1)oValid Input: An object of type: MealTicket. Return False on invalid input.oThis is the enqueue method. It will add a meal ticket to the queue. It will thenreturn True/False depending on if the enqueue was successful (Hint: Add a newticket at the tail of the queue).●dequeue(self) → MealTicket/ booleanoComplexity: O(1)oThis is the dequeue method. It will remove the ticket at the front of the queue andreturn it or False if the queue is empty. (Hint: Dequeue a ticket at the head of theQueue).●front(self) → MealTicket/ boolean oComplexity: O(1)oThis method lets the user peak at the ticket at the front of the queue withoutdeleting it. It will either return a meal ticket or false if the queue is empty.●isEmpty(self) → booleanoComplexity: O(1)oThis method will return True/False depending on if the queue is empty or not.●isFull(self) → booleanoComplexity: O(1)oThis method will return True/False depending on if the queue is full or not,Note: See Figure 1 at the bottom of this section for a sample test run of the Queue class. Yourprogram must perform exactly as shown in the figure. Note 2: All methods in the queue classhave a hard complexity upper bound of O(1). Your implementation must be in O(1). Note 3: Forthis assignment you must make and use your own linked list as the base data structure. Usinglists, dictionaries or any other data structure will result in a 0 for the assignment.Task 2: Write the stack classFor task 2, you will need to write a Stack class. The class is detailed as follows:●__init__(self, capacity) → NoneoComplexity: O(1)oValid Input: An integer in (0, ∞]. Use a default, valid capacity on invalid input.oThis is the constructor for the class. You will need to store the following here:▪The head pointer▪A variable maxSize▪A variable currentSize▪Any other instance variables you want.●push(self, ticket) → booleanoComplexity: O(1)oValid Input: An object of type: MealTicket. Return False on invalid input.oThis is the push method. It will take a ticket and push it at the top of the stack. Itwill then return True/False depending on if the push was successful (Hint: Add aticket at the head of the Stack).●pop(self) → MealTicket/ booleanoComplexity: O(1)oThis is the pop method. It will remove the ticket at the top of the stack and returnit or False if the stack is empty (Hint: Pop a ticket from the head of the Stack).●peek(self) → MealTicket/ booleanoComplexity: O(1)oThis method lets the user peak at the ticket at the top of the stack without deletingit.●isEmpty(self) → booleanoComplexity: O(1) oThis method will return True/False depending on if the stack is empty or not.●isFull(self) → booleanoComplexity: O(1)oThis method will return True/False depending on if the stack is full or not,Note: See Figure 2 at the bottom of this section for a sample test run of the Stack class. Yourprogram must perform exactly as shown in the figure. Note 2: All methods in the stack classhave a hard complexity upper bound of O(1). Your implementation must be in O(1). Note 3: Forthis assignment you must make and use your own linked list as the base data structure. Usinglists, dictionaries or any other data structure will result in a 0 for the assignment.I/O Specifications:For this assignment 2 files are provided: lab1-main.py and mealticket.py. You are free to use themain provided or to make your own. Warning: I will be testing your code with a more robustmain that will check all of the corner cases and uses a wider variety of tickets. Keep this in mindwhile developing your data structures. The provided main tests some of the corner cases but notall of them. You will need to use the methodology discussed in lab to figure out all corner casesand account for them. Your programs must be robust (i.e. do not crash when given bad input ortold to peak/front when the stack/queue is empty etc.)