Question
The introduction of Section 6.1 notes that stacks are often used to provide “undo” support in applications like aWeb browser or text editor. While support for undo can be implemented with an unbounded stack, many applications provide only limited support for such an undo history, with a fixed-capacity stack. When push is invoked with the stack at full capacity, rather than throwing an exception, a more typical semantic is to accept the pushed element at the top while “leaking” the oldest element from the bottom of the stack to make room. Give an implementation of such a LeakyStack abstraction, using a circular array
Answer
package stacks;
public class LeakyStack implements Stack{
private int capacity = 0;
private int size = 0;
private int top = -1;
private int rear = 0;
private Object[] arr;
LeakyStack(int capacity){
this.capacity = capacity;
this.arr = new Object[this.capacity];
}
@Override
public void push(Object obj) {
this.top = (this.top + 1) % this.capacity ;
System.out.println("Adding at top position " + this.top);
this.arr[this.top] = obj;
if (!isFull()) {
this.size++;
}
if (isFull()) {
this.rear = (this.rear + 1) % this.capacity;
System.out.println("Setting rear position now to " + this.rear);
}
}
@Override
public Object pop() {
Object item = this.arr[this.top];
if (this.rear > 0 && this.top != 0) {
this.rear--;
this.top--;
} else if (this.rear == 1) {
this.top = this.capacity - 1;
this.rear--;
} else {
this.top--;
this.size--;
}
return item;
}
@Override
public Object peek() {
return this.arr[this.top];
}
@Override
public int size() {
return this.size;
}
@Override
public boolean isFull() {
return this.size() == this.capacity;
}
@Override
public boolean isEmpty() {
return this.size() == 0;
}
public static void main(String[] args) {
LeakyStack stk = new LeakyStack(2);
stk.push('A'); // push 4 items onto stack
stk.push('B');
stk.push('C');
stk.push('D');
System.out.println("size(): " + stk.size());
Object item = stk.pop(); // delete item
System.out.println(item + " is deleted");
stk.push('D');
stk.push('E');
System.out.println(stk.pop() + " is deleted");
stk.push('G'); // push one item
item = stk.peek(); // get top item from the stack
System.out.println(item + " is on top of stack");
System.out.println("Size of the Stack : " + stk.size());
}
}