Question

Given a class Stack with the interface

   public void push(char n) // pushes n onto stack

   public char pop() // return the top of the stack, removing element from stack

   public boolean isEmpty() // return true if stack is empty

Write a method

public int removeX(Stack<Character> stack)

which takes a stack of Characters, removes the occurrences of ‘X’ and returns the count of the number of Xs removed. It must restore the stack to its original order (less the Xs). You may use any other internal storage you choose.

For example, input of stack

      Bottom [ A X B C X D] Top

Would return 2 and the stack would now be

       Bottom [A B C D] Top

Answer 1

import static java.lang.System.exit; 
  
// Create Stack Using Linked list 
class StackUsingLinkedlist { 
  
    // A linked list node 
    private class Node { 
  
        char data; // integer data 
        Node link; // reference variable Node type 
    } 
    // create global top reference variable global 
    Node top; 
    // Constructor 
    StackUsingLinkedlist() 
    { 
        this.top = null; 
    } 
  
    // Utility function to add an element x in the stack 
    public void push(char x) // insert at the beginning 
    { 
        // create new node temp and allocate memory 
        Node temp = new Node(); 
  
        // check if stack (heap) is full. Then inserting an 
        //  element would lead to stack overflow 
        if (temp == null) { 
            System.out.print("\nHeap Overflow"); 
            return; 
        } 
  
        // initialize data into temp data field 
        temp.data = x; 
  
        // put top reference into temp link 
        temp.link = top; 
  
        // update top reference 
        top = temp; 
    } 
  
    // Utility function to check if the stack is empty or not 
    public boolean isEmpty() 
    { 
        return top == null; 
    } 
  
    // Utility function to pop top element from the stack 
    public Node pop() // remove at the beginning 
    { 
        // check for stack underflow 
        if (top == null) { 
            System.out.print("\nStack Underflow"); 
            return null; 
        } 
  
        Node temp = top;
        // update the top pointer to point to the next node 
        top = (top).link; 
        return temp;
    } 
  
    public void display() 
    { 
        // check for stack underflow 
        if (top == null) { 
            System.out.printf("\nStack Underflow"); 
            exit(1); 
        } 
        else { 
            Node temp = top; 
            System.out.print("[ ");
            while (temp != null) { 
  
                // print node data 
                System.out.print(temp.data + " "); 
  
                // assign temp link to temp 
                temp = temp.link; 
            }
            System.out.print("]");
        } 
    } 
    
    // Function to delete all X 
    // elements from the stack 
    public void removeX() 
    { 
        StackUsingLinkedlist temp = new StackUsingLinkedlist(); 
  
        // While stack is not empty 
        while (!isEmpty()) { 
            char val = pop().data; 
  
            // If value is odd then push 
            // it to the temporary stack 
            if (val != 'X') 
                temp.push(val); 
        } 
  
        // Tranfer the contents of the temporary stack 
        // to the original stack in order to get 
        // the original order of the elements 
        while (!temp.isEmpty()) 
            push(temp.pop().data); 
    } 
} 
// main class 
public class Main { 
    public static void main(String[] args) 
    { 
        // create Object of Implementing class 
        StackUsingLinkedlist obj = new StackUsingLinkedlist(); 
        // insert Stack value 
        obj.push('D'); 
        obj.push('X'); 
        obj.push('C'); 
        obj.push('B'); 
        obj.push('X'); 
        obj.push('A'); 
  
        // print Stack elements 
        obj.display(); 
        
        obj.removeX();
        System.out.println("\nAfter Removing X: ");   
        obj.display(); 
    } 
} 

Output: