Redirecting to
NADOS

Linked List To Queue Adapter

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are required to complete the code of our LLToQueueAdapter class. 
2. As data members, you've a linkedlist available in the class.
3. Here is the list of functions that you are supposed to complete
     3.1. add -> Should accept new data in FIFO manner
     3.2. remove -> Should remove and return data in FIFO manner. If not available, 
     print "Queue underflow" and return -1.
     3.3. peek -> Should return data in FIFO manner. If not available, print "Queue 
     underflow" and return -1.
     3.4. size -> Should return the number of elements available in the queue
4. Input and Output is managed for you.

Note -> The intention is to use linked list functions to achieve the purpose of a queue. All the functions should work in constant time.
Input Format 
Input is managed for you
Output Format 
Output is managed for you
Question Video
Constraints 
None
Sample Input 
add 10
add 20
add 30
add 40
add 50
add 60
peek
remove
peek
remove
peek
remove
peek
remove
peek
remove
peek
remove
quit
Sample Output 
10
10
20
20
30
30
40
40
50
50
60
60


  • Editorial

    A queue is a data structure just like a list but with restricted access. Say for example we have a queue of customers at a shop, here the first person who comes in gets out first and the later ones follow. This representation is similar to the queue data structure wherein an element is inserted at the end of the list and removed from the beginning. It is restricted in the sense that insertion (of elements) or deletion (of elements) can take place only at the specific positions. Also, users can not access any other elements (or nodes) except the frontmost element. This means that the queue has a FIFO property (FirstIn First Out).

    The problem here deals with modifying a linked list to create a queue.

    Our task is to implement LLToQueueAdapter class, so for that first, we need to have a list to store data, so our data member in this class would be a linked list.

    Below is the implementation for the same in Java:

    LinkedList list;

    As we know that every class has a constructor, here we will write our constructor which will initialize our list.

    Below is the implementation for the same in Java:

    public LLToQueueAdapter() {
                                        list = new LinkedList<>();
                                    }

    Now the first function which we wish to implement is the add() function which takes a single argument valwhich contains the element that needs to be added at the end of the queue. For that, we simply add the element at the end of our list by using the in-build addLast() function.

    Below is the implementation for the same in Java:

    void add(int val) {
                                        list.addLast(val);
                                    }

    The next function is the size() function which returns the current size of our queue, for that we can simply use the in-built size() function of the LinkedList class and return it.

    Below is the implementation for the same in Java:

    int size() {
                                        return list.size();
                                    }

    The next function is the remove() function whose task is to remove the element present at the front of the queue. In our class we have considered the head node as the front of the queue, now we simply need to remove the node at the head of the linked list and we also need to handle the condition when our list is empty as we can not retrieve any information from an empty list.

    Below is the implementation for the same in Java:

    int remove() {
                                        if (size() == 0) {
                                            System.out.println("Queue underflow");
                                            return -1;
                                        } else {
                                            return list.removeFirst();
                                        }
                                    }

    The next function is the peek() function whose task is to return the element present at the front of the queue. We simply need to return the data present at the head of the linked list and we also need to handle the condition when our list is empty as we can not retrieve any information from an empty list.

    Below is the implementation for the same in Java:

    int peek() {
                                    if(size() == 0){
                                    System.out.println("Queue underflow");
                                    return -1;
                                    } else {
                                    return list.getFirst();
                                    }
                                }

    Time Complexity: O(1)

    The time complexity for every function in our class is linear as the operations involved here are insertion at the tail, removal at head, size incrementation or decrementation which are all constant operations.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name