Given the java code below, add a method which removes the elements in the bottom

Question

Given the java code below, add a method which removes the elements in the bottom half of the stack, call it removeBottomHalf; test the method using the driver program; and determine the time complexity of the new method.

// This class implements a Stack ADT as a linked list
public class LinkedStack {
LinkedNode front; // Reference to the first LinkedNode in the list
int count;         // Number of nodes in the list

// Constructor - initializes the front and count variables
LinkedStack() {
  front = null;
  count = 0;
}

// Implements the push operation
void push(int x) {
  LinkedNode newNode = new LinkedNode(x);
    newNode.next = front;
    front = newNode;
    count++;
}

// Implements the pop operation
int pop() {
  int x = front.x;
  front = front.next;
  count--;
  return x;
}

// Implements the peek operation
int peek() {
  return front.x;
}

// Implements the isEmpty operation
boolean isEmpty() {
  return front==null;
}

// Implements the size operation
int size() {
  return count;  
}

// This method returns a String containing
// a space separated representation of the underlying linked list
public String toString() {
  String str = "";
  
  LinkedNode cur = front;
  while (cur!=null) {
   str += cur.x + " ";
   cur = cur.next;
  }
  
  return str;
}

}

Explanation / Answer

The coding is done based on your requirement and it is given below clearly

code:

/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1;

/**
*
* @author miracle
*/
import java.util.*;
class Node
{
protected int data;
protected Node link;

/* Constructor */
public Node()
{
link = null;
data = 0;
}   
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}   
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}   
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}   
/* Function to get link to next node */
public Node getLink()
{
return link;
}   
/* Function to get data from current Node */
public int getData()
{
return data;
}
}

/* Class LinkedStack */
class LinkedStack
{
protected Node front ;
protected int count ;

/* Constructor */
public LinkedStack()
{
front = null;
count = 0;
}   
/* Function to check if stack is empty */
public boolean isEmpty()
{
return front == null;
}   
/* Function to get the count of the stack */
public int getSize()
{
return count;
}   
/* Function to push an element to the stack */
public void push(int data)
{
Node nptr = new Node (data, null);
if (front == null)
front = nptr;
else
{
nptr.setLink(front);
front = nptr;
}
count++ ;
}   
/* Function to pop an element from the stack */
public int pop()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
Node ptr = front;
front = ptr.getLink();
count-- ;
return ptr.getData();
}   
/* Function to check the front element of the stack */
public int peek()
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception") ;
return front.getData();
}   
/* Function to display the status of the stack */
public void display()
{
System.out.print(" Stack = ");
if (count == 0)
{
System.out.print("Empty ");
return ;
}
Node ptr = front;
while (ptr != null)
{
System.out.print(ptr.getData()+" ");
ptr = ptr.getLink();
}
System.out.println();   
}
}

/* Class LinkedStackCode */
public class LinkedStackCode
{   
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
/* Creating object of class LinkedStack */
LinkedStack ls = new LinkedStack();   
/* Perform Stack Operations */  
System.out.println("Linked Stack Test ");  
char ch;
do
{
System.out.println(" Linked Stack Operations");
System.out.println("1. push");
System.out.println("2. pop");
System.out.println("3. peek");
System.out.println("4. check empty");
System.out.println("5. count");   
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to push");
ls.push( scan.nextInt() );
break;
case 2 :
try
{
System.out.println("Popped Element = "+ ls.pop());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}   
break;
case 3 :
try
{
System.out.println("Peek Element = "+ ls.peek());
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 4 :
System.out.println("Empty status = "+ ls.isEmpty());
break;   
case 5 :
System.out.println("count = "+ ls.getSize());
break;   
case 6 :
System.out.println("Stack = ");
ls.display();
break;   
default :
System.out.println("Wrong Entry ");
break;
}
/* display stack */   
ls.display();   
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);

} while (ch == 'Y'|| ch == 'y');
}
}

Sample Output:

Linked Stack Test


Linked Stack Operations
1. push
2. pop
3. peek
4. check empty
5. size

Hope This Helps, if you have any doubts Please comment i will get back to you, thank you and please thumbs up

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.