Question

1. You are given Stack.java, an interface class for Stacks.

/* Use an array to implement the Stack.java in a class called ArrayStack.java that uses Generics. Write a main function that creates two stacks, one containing 10 Integers and a different one containing 10 Strings, and reverses there contents using a method called reverse that takes as a paramater a Generic array. You will need to implement all the methods of Stack.java as well as create a toString method in ArrayStack.

Requirement: If the stack is full, you need to use double growth to create a new stack and test this in the main. You may want to accomplish this also using a method.

Java Language

Answer 1

// Stack.java

public interface Stack<T>

{

/**

* @return true if the stack is empty

*/

public boolean isEmpty();

/**

* @return true if the stack is full

*/

public boolean isFull();

/**

* @return the element at top without removing it, null if stack is empty

*/

public T peek();

/**

* @return the element at top after removing it, null if stack is empty

*/

public T pop();

/**

* pushes the item into the stack, no changes will be made if stack is full

*/

public void push(T item);

/**

* resets the stack to empty

*/

public void clear();

/**

* @return the size of the stack

*/

public int size();

/**

* reverses the stack using another stack

*/

public void reverse();

/**

* display the contents of the stack from front to the rear (top)

*/

public void display();

}

// ArrayStack.java

public class ArrayStack<T> implements Stack<T>

{

private int max;// maximum size

private T[] stack;// array of elements

private int size;// current number of elements

public ArrayStack(int max_capacity)

{

max = max_capacity;

// initializing array of T elements

stack = (T[]) (new Object[max]);

size = 0;

}

@Override

public boolean isEmpty()

{

return size == 0;

}

@Override

public boolean isFull()

{

return size == stack.length;

}

@Override

public T peek()

{

if (!isEmpty())

{

// returning the element without removing it

return stack[size - 1];

}

return null;

}

@Override

public T pop()

{

if (!isEmpty())

{

// returning the element after removing it

T removedData = stack[size - 1];

size--;

return removedData;

}

return null;

}

@Override

public void push(T item) {

if (!isFull()) {

// adding to the end of the array if array is not null

stack[size] = item;

size++;

}

}

@Override

public void clear()

{

// resetting

stack = (T[]) (new Object[max]);

size = 0;

}

@Override

public int size() {

return size;

}

@Override

public void reverse()

{

/**

* creating another stack

*/

ArrayStack<T> tmpStack = new ArrayStack<T>(max);

/**

* removing all elements from this stack and adding to the newly created

* stack

*/

while (!isEmpty()) {

tmpStack.push(this.pop());

}

/**

* updating the stack and size variables to that of the newly created

* stack (moving the variables)

*/

this.stack = tmpStack.stack;

this.size = tmpStack.size;

}

@Override

public void display()

{

if (!isEmpty())

{

System.out.println(toString());

} else

{

System.out.println("--Empty--");

}

}

@Override

public String toString() {

String data = "";

//appending all values to a string

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

data += stack[i] + " ";

}

return data;

}

}

// ListStack.java

public class ListStack<T> implements Stack<T>

{

private int max;

private Node<T> head;// points to the front node

private Node<T> top;// points to the rear node

private int size;

public ListStack(int max_capacity)

{

max = max_capacity;

size = 0;

head = null;

top = null;

}

@Override

public boolean isEmpty() {

return size == 0;

}

@Override

public boolean isFull() {

return size == max;

}

@Override

public T peek()

{

if (!isEmpty())

{

// returning without removing

return top.data;

}

return null;

}

@Override

public T pop() {

if (!isEmpty()) {

T removedData = top.data;

if (head == top)

{

/**

* removing first element

*/

head = null;

top = null;

size = 0;

}

else

{

Node<T> tmp = head;

/**

* looping until the next node is top

*/

while (tmp.next != top) {

tmp = tmp.next;

}

// setting current top node to null

tmp.next = null;

// updating top node

top = tmp;

size--;

}

return removedData;

}

return null;

}

@Override

public void push(T item) {

if (!isFull()) {

Node<T> node = new Node<T>(item);

if (isEmpty()) {

// first entry

head = node;

top = head;

size++;

} else {

// appending to the last node

top.next = node;

top = node;

size++;

}

}

}

@Override

public void clear()

{

// resetting

head = null;

top = null;

size = 0;

}

@Override

public int size()

{

return size;

}

@Override

public void reverse()

{

// same technique used in array stack

ListStack<T> tmpStack = new ListStack<T>(max);

while (!isEmpty())

{

tmpStack.push(this.pop());

}

// updating variables

this.head = tmpStack.head;

this.top = tmpStack.top;

this.size = tmpStack.size;

}

@Override

public void display()

{

if (!isEmpty())

{

System.out.println(toString());

}

else

{

System.out.println("--Empty--");

}

}

@Override

public String toString() {

String data = "";

Node<T> tmp = head;

while (tmp != null) {

data += tmp.data + " ";

tmp = tmp.next;

}

return data;

}

/**

* a private inner class to represent one Node in the list

*/

private class Node<T>

{

T data;

Node next;

public Node(T data)

{

this.data = data;

}

}

}

// QuestionOne.java

public class QuestionOne

{

public static void main(String[] args)

{

//creating An array stack and list stack of 20 capacity

ArrayStack<Integer> arrayStack = new ArrayStack<Integer>(20);

ListStack<Integer> listStack = new ListStack<Integer>(20);

for (int i = 1; i <= 20; i++)

{

//pushing 1-20 into array stack

arrayStack.push(i);

//pushing 20-1 into list stack

listStack.push(21 - i);

}

System.out.println("Array Stack:");

/**

* performing required operations in proper order

*/

// display

arrayStack.display();

// reverse

arrayStack.reverse();

// display

arrayStack.display();

// peek

System.out.println(arrayStack.peek());

// pop

System.out.println(arrayStack.pop());

// pop

System.out.println(arrayStack.pop());

// reverse

arrayStack.reverse();

// size

System.out.println(arrayStack.size());

// isFull

System.out.println(arrayStack.isFull());

// isEmpty

System.out.println(arrayStack.isEmpty());

// display

arrayStack.display();

// clear

arrayStack.clear();

// display

arrayStack.display();

// isEmpty

System.out.println(arrayStack.isEmpty());

System.out.println("\nList Stack:");

/**

* performing the same operations for list stack in proper order

*/

// display

listStack.display();

// reverse

listStack.reverse();

// display

listStack.display();

// peek

System.out.println(listStack.peek());

// pop

System.out.println(listStack.pop());

// pop

System.out.println(listStack.pop());

// reverse

listStack.reverse();

// size

System.out.println(listStack.size());

// isFull

System.out.println(listStack.isFull());

// isEmpty

System.out.println(listStack.isEmpty());

// display

listStack.display();

// clear

listStack.clear();

// display

listStack.display();

// isEmpty

System.out.println(listStack.isEmpty());

}

}

/*OUTPUT*/

Array Stack:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1

1

2

18

false

false

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

--Empty--

true

List Stack:

20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

20

20

19

18

false

false

18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

--Empty--

true