Implement Stack With Linked List

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
106 upvotes
Asked in companies
AmazonCiscoDell Technologies

Problem statement

You must implement the Stack data structure using a Singly Linked List.


Create a class named 'Stack' which supports the following operations(all in O(1) time):


getSize: Returns an integer. Gets the current size of the stack

isEmpty: Returns a boolean. Gets whether the stack is empty

push: Returns nothing. Accepts an integer. Puts that integer at the top of the stack

pop: Returns nothing. Removes the top element of the stack. It does nothing if the stack is empty.

getTop: Returns an integer. Gets the top element of the stack. Returns -1 if the stack is empty
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of the input will contain the number of queries, 'q'.

The next 'q' lines will contain the queries. They can be of the following five types:

'1': Print the current size of the stack

'2': Find whether the stack is empty. Print "true" if yes, and "false" otherwise.

'3': This query will be like "3 val," where 'val' can be any non-negative integer. Put 'val' on the top of the stack. Print nothing

'4': Remove the top element of the stack. Print nothing

'5': Print the top element of the stack. If the stack is empty, print -1

Output format:

Print the result of each query on a separate line. If the query is '3' or '4', print nothing (not even an empty line)

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
4
3 5
3 4
1
2
Sample Output 1:
2
false    
Explanation for Sample Output 1:
The first two queries ('3') push 5 and 4 on the stack. So the size of the stack becomes 2. 

Therefore the third query ('1') prints the size, and since the stack is not empty, the fourth and final query ('2') outputs "false"
Sample Input 2:
4
3 5
3 4
4
5
Sample Output 2:
5   
Explanation for Sample Output 2:
The first two queries ('3') push 5 and 4 on the stack.

The third query ('4') removes the top element of the stack, which is 4.

The fourth and final query ('5') prints the top element of the stack, 5
Constraints:
1 <= q <= 10^6
1 <= type <= 5
1 <= Data <= 2^31 - 1

Where 'type' is the type of query and 'Data' is the values getting pushed and popped from the stack. 

Time Limit: 1sec
Hint

Usually, insertion/deletion from a linked list takes O(n) time. But that happens because we insert/elements anywhere from the head to the tail. What if we only do those operations at the head?

Approaches (1)
Best Approach
  1. Maintain a linked list. Keep track of its head, and size at all times, and update them accordingly whenever a new operation is performed.
  2. Following is the way we can implement all functions of the stack using linked list:
    1. First, initialize a head node, and the size of the list as NULL and 0 respectively.
    2. Then for push function, insert new elements at the head of the list, i.e. the new element will become the new head of the list and the previous head will become the next of new head. Also, increase the size by 1.
    3. For pop, just move the head to its next and delete the original head(if required). Also, decrease the size by 1. If the head was null or None (i,e, the list is empty), do nothing.
    4. For getTop, simply return the head’s data or -1 if the list is empty.
    5. For getSize, simply return the size of the list
    6. For isEmpty, return true if the size is 0, otherwise, return false
Time Complexity

O(1)

Since we are inserting and deleting elements from the head of the list itself, constant time is spent on pop and push functions. The other functions are also simply returning a value, so they also take constant time.

Space Complexity

O(N) where ‘N’ is the number of elements pushed in the stack.

We can add a maximum of ‘N’ elements in the stack.

Code Solution
(100% EXP penalty)
Implement Stack With Linked List
Full screen
Console