Q1) Creating the stack classes You are required to write your own generic stack
ID: 3907437 • Letter: Q
Question
Q1) Creating the stack classes
You are required to write your own generic stack implementation in Java that you will use in questions 2 and 3.
a. Create a stack interface Stack that uses a generic type T and has the following abstract methods:
- isEmpty, isFull, peek (returns T), pop(returns T), void push(T), void clear() to clear the contents of the stack0, and int size (returns the number of elements in the stack). - void reverse() reverses the contents of the stack ( in your implementation you can use an additional local stack in your method to help you with the reverse operation.) - void display() prints out the contents of the stack (Hint: you can obtain the contents of your stack elements using toString())
b. Write your two stack implementations (ArrayStack and ListStack) using the stack interface.
c. Your stack implementations must have all instance variables as private.
d. Both implementations must a constructor that initializes the capacity of the stack. For the ListStack, the stack is full when the size reaches the initial capacity.
e. You must also implement public String toString() in both classes. It returns a String representation of the stack contents.
f. Create a simple main class QuestionOne that creates two stacks of Integers of capacity=20 one that uses the ArrayStack and the other uses the ListStack implementations. Push 20 values in each: in the first (1,2,3,…,20) and in the second (20, 19,..,13,.., 1). Call the following methods for both stacks in the given order: display, reverse, display, peek, pop, pop, reverse, size, isFull, isEmpty, display, clear, display, isEmpty.
Deliverable: folder Q1
Stack.java
ArrayStack.java
ListStack.java
QuestionOne.java
Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
EDIT: I’m getting troubles submitting the answer without losing the format. Showing character limit exceeded error. So I have to paste it as a plain text, which will cause the loss of code formatting and indentations. Sorry for the trouble. If you are using eclipse ,copy the code and press ctrl+shift+F to format the code
// 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(" List 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
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.