Web browsers commonly allow you to navigate through a \"history\" of web pages t
ID: 3907695 • 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:
1. Implement the following MyLeakyStack<E> class
Using Array
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
Please find the java code below for MyLeakyStack.java
public class MyLeakyStack<T> implements Stack<T> {
private int stackSize;
private T[] stackArr;
private int top;
/**
* constructor to create stack with size
* @param size
*/
@SuppressWarnings("unchecked")
public MyLeakyStack(int size) {
this.stackSize = size;
this.stackArr = (T[]) new Object[stackSize];
this.top = -1;
}
/**
* This method adds new entry to the top
* of the stack
* @param entry
* @throws Exception
*/
public void push(T entry){
if(this.isStackFull()){
System.out.println(("Stack is full. Increasing the capacity."));
this.increaseStackCapacity();
}
System.out.println("Adding: "+entry);
this.stackArr[++top] = entry;
}
/**
* This method removes an entry from the
* top of the stack.
* @return
* @throws Exception
*/
public T pop() throws Exception {
if(this.isStackEmpty()){
throw new Exception("Stack is empty. Can not remove element.");
}
T entry = this.stackArr[top--];
System.out.println("Removed entry: "+entry);
return entry;
}
/**
* This method returns top of the stack
* without removing it.
* @return
*/
public T peek() {
return stackArr[top];
}
private void increaseStackCapacity(){
@SuppressWarnings("unchecked")
T[] newStack = (T[]) new Object[this.stackSize*2];
for(int i=0;i<stackSize;i++){
newStack[i] = this.stackArr[i];
}
this.stackArr = newStack;
this.stackSize = this.stackSize*2;
}
/**
* This method returns true if the stack is
* empty
* @return
*/
public boolean isStackEmpty() {
return (top == -1);
}
/**
* This method returns true if the stack is full
* @return
*/
public boolean isStackFull() {
return (top == stackSize - 1);
}
public static void main(String a[]) throws Exception{
MyLeakyStack<String> stringStack = new MyLeakyStack<String>(2);
stringStack.push("https://www.google.co.in/");
stringStack.push("https://www.youtube.com/");
stringStack.push("https://www.chegg.com/my/expertqa");
System.out.println("Popped URL is: " + stringStack.pop());
System.out.println("URL at the Top of Stack is: " + stringStack.peek());
}
}
Please let me know in case of any clarifications required. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.