Web browsers commonly allow you to navigate through a \"history\" of web pages t
ID: 3907818 • Letter: W
Question
Web browsers commonly allow you to navigate through a "history" of web pages that have previously been visited. The mechanism is somewhat like a stack, in that the most recently visited pages are at the top of the history and revisited when the "back" button is pressed.
However, the history does not necessarily have unbounded capacity. In reality, there may exist a fixed limit on the size of the history. The issue arises as to what should happen when the capacity is exhausted and a new item is pushed onto the stack. One possibility is to throw an exception. But this is not how a Web browser behaves. If it only has room to save 50 pages in its history and yet you visit more pages, it will make room in the history for a new page by throwing away the page that is on the very bottom of the history (i.e., the least recently visited page). The formal Stackinterface does not help, as it gives us no way to directly access or remove the object on the bottom of the stack.
Your Task:
Implement the following MyLeakyStack<E> class
Using Singly Linked List
import net.datastructures.*;
public class MyLeakyStack<E> implements Stack<E> {
@Override
public int size() {
// TODO Auto-generated method stub
return 0;
}
@Override
public boolean isEmpty() {
// TODO Auto-generated method stub
return false;
}
@Override
public void push(E e) {
// TODO Auto-generated method stub
}
@Override
public E top() {
// TODO Auto-generated method stub
return null;
}
@Override
public E pop() {
// TODO Auto-generated method stub
return null;
}
}
Explanation / Answer
Hello, I have already answered a similar question before, so I’m referring it here. Implemented everything as per the requirements. Defined following things in this answer.
? Defined a class Item to represent one Node in the LeakyStack linked list.
? As you have not provided the Stack interface, created one myself.
? Modified the MyLeakyStack class, completed all the required methods. Defined one private method removeBottom() which will remove the bottom most element when the max size has been reached. (will be called by the push() method itself) and one more method to display the stack contents.
? Defined a Test class with a main method, thoroughly tested the MyLeakyStack class.
? Comments are included, If you have any doubts, feel free to ask, Thanks
// MyLeakyStack.java
public class MyLeakyStack<E> implements Stack<E> {
Item<E> top; /* pointer to the top most item */
int MAX_CAPACITY;
/**
* Constructor to initialize the stack
*
* @param max
* - maximum capacity of the stack
*/
public MyLeakyStack(int max) {
MAX_CAPACITY = max;
top = null;
}
/**
* method to return the size of the stack
*/
@Override
public int size() {
int count = 0;
Item<E> itm = top;
while (itm != null) {
itm = itm.next;
count++;
}
return count;
}
/**
* method to check if stack is empty
*/
@Override
public boolean isEmpty() {
if (top == null) {
return true;
}
return false;
}
/**
* method to push an element to the top
*/
@Override
public void push(E e) {
Item<E> item = new Item<E>(e);
if (top == null) {
top = item;
} else {
if (size() == MAX_CAPACITY) {
/**
* Max capacity reached, removing the bottom most item
*/
removeBottom();
}
/**
* Adding to the top and updating the top pointer
*/
item.next = top;
top = item;
}
}
/**
* method to return the data of topmost item without removing it
*/
@Override
public E top() {
if (isEmpty()) {
return null;
} else {
E data = (E) top.data;
return data;
}
}
/**
* method to remove the topmost item and returns the data
*/
@Override
public E pop() {
if (isEmpty()) {
return null;
} else {
E data = (E) top.data;
top = top.next; /* removing the top */
return data;
}
}
/**
* method to remove the element at the bottom, will be called by the method
* push()[when the max capacity is reached ]
*/
private void removeBottom() {
if (!isEmpty()) {
Item<E> itm = top;
Item<E> nextItem = top.next;
if (nextItem == null) {
System.out.println(top.data
+ " has been removed automatically!");
top = null;
} else {
/**
* Loops until the next item is null
*/
while (nextItem != null) {
if (nextItem.next == null) {
/**
* next of next item is null, so removing the next item
* as it is the last node
*/
System.out.println(nextItem.data
+ " has been removed automatically!");
itm.next = null;
}
itm = nextItem;
nextItem = itm.next;
}
}
}
}
/**
* a method to display the current stack contents
*/
public void display() {
System.out.println(" Current LeakyStack:");
Item<E> itm = top;
while (itm != null) {
System.out.print(itm.data);
itm = itm.next;
if (itm != null) {
/**
* printing a separator
*/
System.out.print(" > ");
}
}
System.out.println(" Size: " + size() + " ");
}
}
//Item.java
/**
* A class defined to represent one Node of the linked list
*/
public class Item<E> {
E data;
Item next;
public Item(E data) {
this.data=data;
}
}
//Stack.java
public interface Stack<E> {
public int size();
public boolean isEmpty();
public void push(E e);
public E top();
public E pop();
}
//Test.java
public class Test {
public static void main(String[] args) {
/**
* Defining a leaky stack with maximum size 5
*/
MyLeakyStack<String> leakyStack = new MyLeakyStack<String>(5);
/**
* Demonstrating different operations
*/
leakyStack.push("google.com");
leakyStack.display();
System.out.println("Pushing a few more items");
leakyStack.push("facebook.com");
leakyStack.push("twitter.com");
leakyStack.push("insta.com");
leakyStack.push("reddit.com");
leakyStack.display();
/**
* Now the stack has 5 elements, which is the maximum capacity, pushing
* any more items will remove the bottom most item
*/
System.out
.println("pushing one more item, should remove the bottom most item automatically!");
leakyStack.push("java.com");
leakyStack.display();
System.out.println("Newest item is " + leakyStack.top());
System.out.println(leakyStack.pop()
+ " is now removed, current top item: " + leakyStack.top());
leakyStack.display();
}
}
/*OUTPUT*/
Current LeakyStack:
google.com
Size: 1
Adding a few more items
Current LeakyStack:
reddit.com > insta.com > twitter.com > facebook.com > google.com
Size: 5
pushing one more item, should remove the bottom most item automatically!
google.com has been removed automatically!
Current LeakyStack:
java.com > reddit.com > insta.com > twitter.com > facebook.com
Size: 5
Newest item is java.com
java.com is now removed, current top item: reddit.com
Current LeakyStack:
reddit.com > insta.com > twitter.com > facebook.com
Size: 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.