Solution For LRU Stack

The objective is to implement a stack using LinkedList. You need to implement push and pop function. When push is called, insert the items in list at the head. When the stack is empty and pop is called return 0 The maximum stack size allowed is 5 Whenever a push is called

Case 1: Value is NOT present in stack: If the stack is full (has 5 items) then remove the oldest pushed item on the stack and push the new item. If the stack is not full, then push the new item

Case 2: Value is already present in stack: Since the item is already present in the stack move it to the top of the stack.

Algorithm

Step 1 :- Create a class(or structure ,depends on the programming language) with a data members for the creation of linked list.

Step 2:- Implement push and pop function using a linked list as we do normally.

Step 3:- In push function before pushing the element to stack check the size of the stack.

->if size is less than 5 ,then push the element normally.

->else then check if the element to be pushed into the stack is already present in the stack.

                    ->if the element is present already ,then move that node to the head of the stack that is to the top of the stack.

                    ->else push the element and remove the last element

This makes to maintain the size of stack.

Step 4:- end.

Time Complexity is O(n)

  

Space Complexity is O(n)

Program

public class LLStack {

    static class Node
    {
    int num;
    Node next;
    Node(int data)
        {
            num=data;
            next=null;
        }
    }
    Node head=null;
    public void push(int data)
    {
        Node newnode=new Node(data);
        if(head==null)
        {
            head=newnode;
        }
        else
        {
            if(count(head)>=5)
            { 
                if(check(head,data))
                {
                    Node temp=head;
                    Node current=null;
                    while(temp!=null)
                    {
                        if(temp.num==data)
                            break;
                        current=temp;
                        temp=temp.next;
                    }
                    current.next=temp.next;
                    newnode.next=head;
                    head=newnode;
                }
                else
                {
                    newnode.next=head;
                    head=newnode;
                    Node temp=head;
                    Node current=null;
                    while(temp.next!=null)
                    {   
                        current=temp;
                        temp=temp.next;
                    }
                    current.next=null;
                }
            }
            else
            {
                newnode.next=head;
                head=newnode;
            }
        }
        System.out.println(" ");
        display();
    }
    public void display()
    {
        Node temp=head;
        while(temp!=null)
        {
            System.out.print(temp.num +"->");
            temp=temp.next;
        }
    }
    public int pop()
    {
        if(head==null)
            return 0;
        int x=head.num;
        head=head.next;
        System.out.println(" ");
        display();
        return x;
    }
    public int count(Node start)
    {
        int count=0;
        Node temp=start;
        while(temp!=null)
        {
            count++;
            temp=temp.next;
        }
        return count;
    }
    public boolean check(Node start,int data)
    {
        Node temp=start;
        while(temp!=null)
        {
            if(temp.num==data)
                return true;
            temp=temp.next;
        }
        return false;
    }
    public static void main(String[] args)
    {
        LLStack st=new LLStack();
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        st.push(5);
        st.push(6);
        st.push(7);
        st.push(8);
        st.push(5);
        st.push(4);
        st.pop();
        st.pop();
        st.pop();

}

}

Output  

1->
2->1->
3->2->1->
4->3->2->1->
5->4->3->2->1->
6->5->4->3->2->
7->6->5->4->3->
8->7->6->5->4->
5->8->7->6->4->
4->5->8->7->6->
5->8->7->6->
8->7->6->

7->6->