Show how to implement a Stack class that implements the usual push , pop , and i
ID: 649773 • Letter: S
Question
Show how to implement a Stack class that implements the usual push, pop, and isEmpty functions plus a min function that returns the minimum item in the stack. All the functions must run in constant time (the execution time should be same regardless of the number of items on the stack. In other words, the functions should run just as fast on a stack with 1000 elements as on a stack with 1 element.) The requirement that the functions run in constant time means that you cannot implement the min function by searching over the elements in stack
Explanation / Answer
import java.io.*;
import java.util.Stack;
public class Stacks
{
static void showpush(Stack st, int a)
{
st.push(new Integer(a));
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
}
static void showpop(Stack st)
{
System.out.print("pop -> ");
Integer a = (Integer) st.pop();
System.out.println(a);
System.out.println("stack: " + st);
}
public static void main(String args[])throws IOException
{
DataInputStream k=new DataInputStream(System.in);
Stack r=new Stack();
for(int i=1; i<=3; i++)
{
System.out.print(" ");
System.out.print("Enter a value to PUSH: ");
int x=Integer.parseInt(k.readLine());
r.showpush (new Integer(x) );
System.out.print("Stacked: "+r+" ");
}
System.out.println("STACK IS FULL!");
do
{
for(int i=1; i<=3; i++)
{
System.out.print(" ");
System.out.print("Enter a value to POP: ");
int x=Integer.parseInt(k.readLine());
r.showpop();
System.out.print("Stacked: "+r+" ");
}
}while(!r.empty());
System.out.println("STACK IS EMPTY!");
}
}