Question

In: Computer Science

Stack Variations-JAVA-self implemented As discussed in the section, instead of having our stack methods throw exceptions...

Stack Variations-JAVA-self implemented

As discussed in the section, instead of having our stack methods throw exceptions in the case of "erroneous" invocations, we could have the stack methods handle the situation themselves. We define the following three "safe" methods:

-boolean safePush (T element) - pushes element onto the stack; returns true if element successfully pushed, false otherwise.

-boolean safePop () - removes the top element of the stack; returns true if element successfully popped, false otherwise.

- T safeTop() - if the stack is not empty returns the top element of the stack otherwise returns null.

a) Add these operations to the ArrayBoundedStack class.

//----------------------------------------------------------------
// ArrayBoundedStack.java by Dale/Joyce/Weems Chapter 2
//
// Implements StackInterface using an array to hold the
// stack elements.
//
// Two constructors are provided: one that creates an array of a
// default size and one that allows the calling program to
// specify the size.
//----------------------------------------------------------------

package ch02.stacks;

public class ArrayBoundedStack<T> implements StackInterface<T>
{
protected final int DEFCAP = 100; // default capacity
protected T[] elements; // holds stack elements
protected int topIndex = -1; // index of top element in stack

public ArrayBoundedStack()
{
elements = (T[]) new Object[DEFCAP];
}

public ArrayBoundedStack(int maxSize)
{
elements = (T[]) new Object[maxSize];
}

public void push(T element)
// Throws StackOverflowException if this stack is full,
// otherwise places element at the top of this stack.
{
if (isFull())
throw new StackOverflowException("Push attempted on a full stack.");
else
{
topIndex++;
elements[topIndex] = element;
}
}

public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (isEmpty())
throw new StackUnderflowException("Pop attempted on an empty stack.");
else
{
elements[topIndex] = null;
topIndex--;
}
}

public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element of this stack.
{   
T topOfStack = null;
if (isEmpty())
throw new StackUnderflowException("Top attempted on an empty stack.");
else
topOfStack = elements[topIndex];
return topOfStack;
}

public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
return (topIndex == -1);
}

public boolean isFull()
// Returns true if this stack is full, otherwise returns false.
{
return (topIndex == (elements.length - 1));
}
}

Create a test driver application to demonstrate that the added code works correctly.

b) Add these operations to the ArrayListStack class.

//----------------------------------------------------------------------
// ArrayListStack.java by Dale/Joyce/Weems Chapter 2
//
// Implements an unbounded stack using an ArrayList.
//----------------------------------------------------------------------

package ch02.stacks;

import java.util.ArrayList;

public class ArrayListStack<T> implements StackInterface<T>
{
protected ArrayList<T> elements; // ArrayList that holds stack elements

public ArrayListStack()
{
elements = new ArrayList<T>();
}

public void push(T element)   
// Places element at the top of this stack.
{
elements.add(element);
}

public void pop()   
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (isEmpty())
throw new StackUnderflowException("Pop attempted on an empty stack.");
else
elements.remove(elements.size() - 1);
}

public T top()   
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element of this stack.
{
T topOfStack = null;
if (isEmpty())
throw new StackUnderflowException("Top attempted on an empty stack.");
else
topOfStack = elements.get(elements.size() - 1);
return topOfStack;
}

public boolean isEmpty()   
// Returns true if this stack is empty, otherwise returns false.
{
return (elements.size() == 0);
}
  
public boolean isFull()
// Returns false - an ArrayList stack is never full.
{
return false;
}

}

Create a test driver application to demonstrate that the added code works correctly.

c) Add these operations to the LinkedStack class.

//----------------------------------------------------------------------
// LinkedStack.java by Dale/Joyce/Weems Chapter 2
//
// Implements StackInterface using a linked list to hold the elements.
//-----------------------------------------------------------------------

package ch02.stacks;

import support.LLNode;

public class LinkedStack<T> implements StackInterface<T>
{
protected LLNode<T> top; // reference to the top of this stack

public LinkedStack()
{
top = null;
}

public void push(T element)
// Places element at the top of this stack.
{
LLNode<T> newNode = new LLNode<T>(element);
newNode.setLink(top);
top = newNode;
}   

public void pop()
// Throws StackUnderflowException if this stack is empty,
// otherwise removes top element from this stack.
{
if (isEmpty())
throw new StackUnderflowException("Pop attempted on an empty stack.");
else
top = top.getLink();
}

public T top()
// Throws StackUnderflowException if this stack is empty,
// otherwise returns top element of this stack.
{   
if (isEmpty())
throw new StackUnderflowException("Top attempted on an empty stack.");
else
return top.getInfo();
}

public boolean isEmpty()
// Returns true if this stack is empty, otherwise returns false.
{
return (top == null);
}

public boolean isFull()
// Returns false - a linked stack is never full
{
return false;
}

}

Create a test driver application to demonstrate that the added code works correctly.  

Solutions

Expert Solution

Here is the completed code for three types of Stacks and Test program, which perform basic tests to ensure that new methods are working properly. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

// ArrayBoundedStack.java

package ch02.stacks;

public class ArrayBoundedStack<T> implements StackInterface<T> {

      protected final int DEFCAP = 100; // default capacity

      protected T[] elements; // holds stack elements

      protected int topIndex = -1; // index of top element in stack

      public ArrayBoundedStack() {

            elements = (T[]) new Object[DEFCAP];

      }

      public ArrayBoundedStack(int maxSize) {

            elements = (T[]) new Object[maxSize];

      }

      public void push(T element)

      // Throws StackOverflowException if this stack is full,

      // otherwise places element at the top of this stack.

      {

            if (isFull())

                  throw new StackOverflowException("Push attempted on a full stack.");

            else {

                  topIndex++;

                  elements[topIndex] = element;

            }

      }

      public void pop()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise removes top element from this stack.

      {

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Pop attempted on an empty stack.");

            else {

                  elements[topIndex] = null;

                  topIndex--;

            }

      }

      public T top()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise returns top element of this stack.

      {

            T topOfStack = null;

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Top attempted on an empty stack.");

            else

                  topOfStack = elements[topIndex];

            return topOfStack;

      }

      public boolean isEmpty()

      // Returns true if this stack is empty, otherwise returns false.

      {

            return (topIndex == -1);

      }

      public boolean isFull()

      // Returns true if this stack is full, otherwise returns false.

      {

            return (topIndex == (elements.length - 1));

      }

      // newly implemented methods

      public boolean safePush(T element) {

            // pushing if not full, and returning true

            if (!isFull()) {

                  push(element);

                  return true;

            }

            // returning false if full

            return false;

      }

      public boolean safePop() {

            // popping if not empty

            if (!isEmpty()) {

                  pop();

                  return true; // success

            }

            return false; // empty, not successful

      }

      public T safeTop() {

            // returning top element if not empty

            if (!isEmpty()) {

                  return top();

            }

            // returning null if empty

            return null;

      }

}

// ArrayListStack.java

package ch02.stacks;

import java.util.ArrayList;

public class ArrayListStack<T> implements StackInterface<T> {

      protected ArrayList<T> elements; // ArrayList that holds stack elements

      public ArrayListStack() {

            elements = new ArrayList<T>();

      }

      public void push(T element)

      // Places element at the top of this stack.

      {

            elements.add(element);

      }

      public void pop()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise removes top element from this stack.

      {

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Pop attempted on an empty stack.");

            else

                  elements.remove(elements.size() - 1);

      }

      public T top()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise returns top element of this stack.

      {

            T topOfStack = null;

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Top attempted on an empty stack.");

            else

                  topOfStack = elements.get(elements.size() - 1);

            return topOfStack;

      }

      public boolean isEmpty()

      // Returns true if this stack is empty, otherwise returns false.

      {

            return (elements.size() == 0);

      }

      public boolean isFull()

      // Returns false - an ArrayList stack is never full.

      {

            return false;

      }

      // newly implemented methods

      public boolean safePush(T element) {

            // pushing if not full, and returning true

            if (!isFull()) {

                  push(element);

                  return true;

            }

            // returning false if full

            return false;

      }

      public boolean safePop() {

            // popping if not empty

            if (!isEmpty()) {

                  pop();

                  return true; // success

            }

            return false; // empty, not successful

      }

      public T safeTop() {

            // returning top element if not empty

            if (!isEmpty()) {

                  return top();

            }

            // returning null if empty

            return null;

      }

}

// LinkedStack.java

package ch02.stacks;

import support.LLNode;

public class LinkedStack<T> implements StackInterface<T> {

      protected LLNode<T> top; // reference to the top of this stack

      public LinkedStack() {

            top = null;

      }

      public void push(T element)

      // Places element at the top of this stack.

      {

            LLNode<T> newNode = new LLNode<T>(element);

            newNode.setLink(top);

            top = newNode;

      }

      public void pop()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise removes top element from this stack.

      {

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Pop attempted on an empty stack.");

            else

                  top = top.getLink();

      }

      public T top()

      // Throws StackUnderflowException if this stack is empty,

      // otherwise returns top element of this stack.

      {

            if (isEmpty())

                  throw new StackUnderflowException(

                              "Top attempted on an empty stack.");

            else

                  return top.getInfo();

      }

      public boolean isEmpty()

      // Returns true if this stack is empty, otherwise returns false.

      {

            return (top == null);

      }

      public boolean isFull()

      // Returns false - a linked stack is never full

      {

            return false;

      }

      // newly implemented methods

      public boolean safePush(T element) {

            // pushing if not full, and returning true

            if (!isFull()) {

                  push(element);

                  return true;

            }

            // returning false if full

            return false;

      }

      public boolean safePop() {

            // popping if not empty

            if (!isEmpty()) {

                  pop();

                  return true; // success

            }

            return false; // empty, not successful

      }

      public T safeTop() {

            // returning top element if not empty

            if (!isEmpty()) {

                  return top();

            }

            // returning null if empty

            return null;

      }

}

// Test.java (for the sake of submission, created within same package)

package ch02.stacks;

public class Test {

      public static void main(String[] args) {

            // creating stacks of all three types

            ArrayBoundedStack<Integer> stk1 = new ArrayBoundedStack<Integer>();

            ArrayListStack<Integer> stk2 = new ArrayListStack<Integer>();

            LinkedStack<Integer> stk3 = new LinkedStack<Integer>();

            // testing safePop method on empty stack. should not cause any

            // exceptions

            stk1.safePop();

            stk2.safePop();

            stk3.safePop();

            // testing safeTop() method on empty stack, should not cause any

            // exceptions, and should display null values

            System.out.println("stk1 safeTop: " + stk1.safeTop()); // null

            System.out.println("stk2 safeTop: " + stk2.safeTop()); // null

            System.out.println("stk3 safeTop: " + stk3.safeTop()); // null

            // adding 1000 elements to array bounded stack, which is way above its

            // capacity, but since we are using safePush, it should not cause any

            // exceptions.

            for (int i = 0; i < 1000; i++) {

                  stk1.safePush(i);

            }

            // displaying that safePush returns false when array is full in array

            // bounded stack

            System.out.println("stk1 safePush(1234): " + stk1.safePush(1234));

            // if no exceptions occurred, we can say that the test is success

      }

}

//OUTPUT

stk1 safeTop: null

stk2 safeTop: null

stk3 safeTop: null

stk1 safePush(1234): false


Related Solutions

*OBJECT ORIENTED PROGRAMMING* JAVA PROGRAMMING GOAL: will be able to throw and catch exceptions and create...
*OBJECT ORIENTED PROGRAMMING* JAVA PROGRAMMING GOAL: will be able to throw and catch exceptions and create multi-threaded programs. Part I Create a class called Animal that implements the Runnable interface. In the main method create 2 instances of the Animal class, one called rabbit and one called turtle. Make them "user" threads, as opposed to daemon threads. Some detail about the Animal class. It has instance variables, name, position, speed, and restMax. It has a static boolean winner. It starts...
Suppose the interface and the class of stack already implemented, Write application program to ( java)...
Suppose the interface and the class of stack already implemented, Write application program to ( java) 1- insert 100 numbers to the stack                         2- Print the even numbers 3- Print the summation of the odd numbers
Define empty methods in Stack class using LinkedList class in Java ------------------------------------------------------------------------------- //Stack class public class...
Define empty methods in Stack class using LinkedList class in Java ------------------------------------------------------------------------------- //Stack class public class Stack{ public Stack(){ // use LinkedList class } public void push(int item){ // push item to stack } public int pop(){ // remove & return top item in Stack } public int peek(){ // return top item in Stack without removing it } public boolean isEmpty(){ // return true if the Stack is empty, otherwise false } public int getElementCount(){ // return current number...
1. a) Write two algorithms of different time complexity implemented in Java methods in complete Java...
1. a) Write two algorithms of different time complexity implemented in Java methods in complete Java program to reverse a stack of characters. Make your own assumption and your own design on the methods signature, inputs, outputs, and the full main program.
Requirements Both the stack and queue were implemented correctly according data structure and java standard practices....
Requirements Both the stack and queue were implemented correctly according data structure and java standard practices. The stack was used to implement a post-fix calculator using push, pop, peek and other stack concepts. The queue was used to implement the palindrome using add, remove, insert and other queue concepts. Both implementations produced the expected output. All submission requirements were followed. Test Harness for the first part: public class StackCalcTest { public static void main(String[] args) { StackCalc stackCalc = new...
**** All these methods should be implemented using RECURSIVE solutions (no looping statements) // Java //...
**** All these methods should be implemented using RECURSIVE solutions (no looping statements) // Java // This method takes an integer array as well as an integer (the starting // index) and returns the sum of the squares of the elements in the array. // This method uses recursion. public int sumSquaresRec(int[] A, int pos) { // TODO: implement this method        return -1; // replace this statement with your own return }    // This method takes a...
rite a java program that uses the methods written in this section to do the following:Prompt...
rite a java program that uses the methods written in this section to do the following:Prompt the user for a number of grades using the getValidInput method. Ensure the number of grades is greater than 1 and less than 30. The error message is “You must enter a number between 1 and 30, please re-enter:”Prompt the user to enter the requested grades and total marks using the calculateLetterGrade method. The grades should be between 0 and 100. Display an appropriate...
Code in Java Create a stack class to store integers and implement following methods: 1) void...
Code in Java Create a stack class to store integers and implement following methods: 1) void push(int num): This method will push an integer to the top of the stack. 2) int pop(): This method will return the value stored in the top of the stack. If the stack is empty this method will return -1. 3) void display(): This method will display all numbers in the stack from top to bottom (First item displayed will be the top value)....
Program in Java Create a stack class to store integers and implement following methods: 1- void...
Program in Java Create a stack class to store integers and implement following methods: 1- void push(int num): This method will push an integer to the top of the stack. 2- int pop(): This method will return the value stored in the top of the stack. If the stack is empty this method will return -1. 3- void display(): This method will display all numbers in the stack from top to bottom (First item displayed will be the top value)....
Create in Java Create a stack class to store integers and implement following methods: 1- void...
Create in Java Create a stack class to store integers and implement following methods: 1- void push(int num): This method will push an integer to the top of the stack. 2- int pop(): This method will return the value stored in the top of the stack. If the stack is empty this method will return -1. 3- void display(): This method will display all numbers in the stack from top to bottom (First item displayed will be the top value)....
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT