In: Computer Science
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.
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