Linked List To Stack Adapter

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 LLToStackAdapter 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. push -> Should accept new data in LIFO manner
3.2. pop -> Should remove and return data in LIFO manner. If not
available, print "Stack underflow" and return -1.
3.3. top -> Should return data in LIFO manner. If not available, print
"Stack underflow" and return -1.
3.4. size -> Should return the number of elements available in the
stack
4. Input and Output is managed for you.

Note -> The intention is to use linked list functions to achieve the purpose of a stack. 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
push 10
push 20
push 5
push 8
push 2
push 4
push 11
top
size
pop
top
size
pop
top
size
pop
top
size
pop
top
size
pop
top
size
pop
top
size
pop
quit
Sample Output
11
7
11
4
6
4
2
5
2
8
4
8
5
3
5
20
2
20
10
1
10


  • Editorial

    A stack is a data structure just like a list but with restricted access. Say for example we have a pile of books, whenever we wish to add a book to the pile we do it at the top of the pile and whenever we wish to remove a book from the pile, removing it from the top seems sensible. Here pile can be referred to as a stack and books can be referred to as elements. It is restricted in the sense that insertion (of elements) or deletion (of elements) can take place only at the top of the stack. Also, users can not access any other data (or node) except the topmost element. This means that stack has a LIFO property (Last InFirst Out).

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

    Our task is to implement LLToStackAdapter 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 LLToStackAdapter() {
                                            list = new LinkedList<>();
                                        } 

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

    Below is the implementation for the same in Java:

    void push(int val) {
                                            list.addFirst(val);
                                        }

    The next function is the size() function which returns the current size of our stack, 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 pop() function whose task is to remove the element present at the top of the stack. In our class we have considered the head node as the top of the stack, 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.Here updation of head and size are taken care of by the in-built LinkedList class we just need to use the functions to get relevant results.

    Below is the implementation for the same in Java:

    int pop() {
                                            if (size() == 0) {
                                                System.out.println("Stack underflow");
                                                return -1;
                                            } else {
                                                int val = list.getFirst();
                                                list.removeFirst();
                                                return val;
                                            }
                                        }

    The next function is the top() function whose task is to return the element present at the top of the stack. In our class we have considered head as the top of the stack, now 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 top() {
                                            if (size() == 0) {
                                                System.out.println("Stack underflow");
                                                return -1;
                                            } else {
                                                int val = list.getFirst();
                                                return val;
                                            }
                                        }

    Time Complexity: O(1)

    The time complexity for every function in our class is linear as the operations involved here are only on the head node and not on the entire list.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name