JAVA PROGRAMING 1) Create a class BackwardsArrayStack that Implements the interf
ID: 3575056 • Letter: J
Question
JAVA PROGRAMING
1) Create a class BackwardsArrayStack that Implements the interface Stack efficiently using an array. The stack should be at the end of the array. The top will be at stackItems.length()-1 or. stackItems.length() - stackSize. Choose the top location that allows for an efficient implementation of push(T item) and pop(). Create a class LinkedListStackWithHeadNode that implements the interface Stack efficiently using a linked list , use an empty header node. Choose a top note that allows for an efficient implementation of both push(T item) and pop(). If necessary, you may include a separate reference to the last node in the linked list.
Explanation / Answer
The Stack Interface:
public interface Stack {
int cap = 1000; // Max Capacity
boolean push(Item item);
Object pop();
}
class Item {
Object value;
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
}
_____________________________
Array Implementation
public class BackwardsArrayStack implements Stack {
Item[] stackItems = new Item[cap];
int top = cap; // Max Capacity
@Override
public boolean push(Item item) {
if (top == 0)
// Stack overflow
return false;
else {
stackItems[--top] = item;
return true;
}
}
@Override
public Object pop() {
if (top == cap) {
// Stack is empty
return Boolean.FALSE;
} else {
return stackItems[top--];
}
}
}
_____________________________
Linked List Implementation
public class LinkedListStackWithHeadNode implements Stack {
Node head = null;
Node top = null;
@Override
public boolean push(Item item) {
Node n = new Node();
n.item = item;
n.next = null;
if (top == null) { // First element
top = n;
head = n;
} else {
top.next = n;
top = n;
}
return true;
}
@Override
public Object pop() {
if (top == null)
// Empty
return Boolean.FALSE;
else {
Item poppedItem = top.item;
if (head.next == null) { // there was only one element
head = top = null;
} else { // More than one element
Node i = head;
while (i.next.next != null) {
i = i.next;
}
// Remove last element
i.next = null;
top = i;
}
return poppedItem;
}
}
}
class Node {
Item item;
Node next;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.