Create a class LinkedListStackWithHeadNode that implements the interface Stack e
ID: 3583419 • Letter: C
Question
Create a class LinkedListStackWithHeadNode that implements the interface Stack efficiently
using a linked list. Again, to make it interesting, use an empty header node, as shown below:
Create a class LinkedListStackWithHeadNode that implements the interface Stack efficiently using a linked list. Again, to make it interesting, use an empty header node, as shown below: item 1tem item L null head Node null 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
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.