It is the Sunday of Labor Week 2019. Woke up as usual, fixed breakfast and then woke up my wife. After having breakfast got ready and went down to my office for my first work block of the day.
Yesterday afternoon we stopped by my son’s place and cooked paella in the wood pit. It was pretty good. This time we did not use red peppers. It seems to taste better with them.
Let’s get to the main subject of this post. Yesterday morning I watched the first few minutes of a video by Java Brains “Implement a Stack – Java Interview Coding Challenge #4”. I decided that today I would generate my own implementation and would add some of the methods not covered in the 
YouTube video. I did use an array for the stack. I typically implement stacks using doubly linked queues. As a matter of fact, years ago I implemented a queue and stack libraries which have been and still are used by a few commercial products.
A stack is a FILO (First In – Last Out) type of data structure. The name derives from the fact that their operation resembles the stacks you find in cafeterias / buffets and schools holding trays / dishes. The first dish pushed into a stack is the last one to come out. You can read more about them here.
The first thing to do is to declare a class for the stack. In our case we will call it MyStack. The stack needs a place to hold the values, the size of the stack and an index pointing to the top of the stack. As I mentioned before, I typically use doubly linked lists in order to eliminate size constraints. Of course each application has its own constraints so it is up to the software designer to determine what would work best for the specific case. That said; the assumptions should always be tested with real world cases. You know what happens when you assume.
Once we have a class we need to add some basic functionality. In our case we will implement the following methods:
| Method | Description |
| constructor | Instantiate a stack. |
| push | Push (insert) a value into the top of a stack. |
| pop | Pop (remove) the value from the top of a stack. |
| peek | Peek (get a copy) of the value at the top of a stack. |
| isEmpty | Check if a stack is empty. |
| isFull | Check if a stack is full. |
| grow | Grow the stack to allow for more values. |
| shrink | Shrink a stack to save memory. |
Following is a screen capture of the console of the Eclipse IDE showing output from the test code:
main <<< peek: 0 main <<< peek: 2 main <<< peek: 4 main <<< peek: 6 grow <<< growing the stack... main <<< peek: 8 main <<< peek: 10 main <<< peek: 12 main <<< stack: [ 12 -> 10 -> 8 -> 6 -> 4 -> 2 -> 0 ] size: 8 top: 6 main <<< peek: 12 main <<< val: 12 main <<< peek: 10 main <<< val: 10 main <<< peek: 8 shrink <<< shrinking the stack... main <<< val: 8 main <<< peek: 6 main <<< val: 6 main <<< peek: 4 main <<< val: 4 main <<< peek: 2 main <<< val: 2 main <<< peek: 0 main <<< val: 0 main <<< stack: [ ] size: 4 top: -1
The test scaffolding shows how we instantiated a stack and pushed 8 values into it. Keep in mind that the initial size of the stack was set to only 4 elements. After we push a value, we peek into the stack to verify that what we pushed was saved at the top of the stack. When done we display the complete stack.
We note that after pushing (inserting) 4 elements into the stack, we had to grow its capacity to continue accepting more values.
When done we display the values in the stack, the size and the index to the top element. The stack is now capable of holding 8 entries and we have pushed 7. All seems to be working as expected.
We now start popping off values from the stack. We first peek at the value on the top of the stack and then we pop it. Note that both values match. When the stack got do 4 entries, a message is displayed indicating that the size of the stack was cut in half. This was done to save memory. Note that in practice we could have used a smaller value in an attempt to eliminate shrinking and growing the stack if we start popping and pushing elements when the size is a multiple of 4.
When all is set and done we display the empty stack.
The Java code for this implementation was generated using the Eclipse IDE on a Windows 10 computer.
public class Solution {
/*
*
*/
static class MyStack<T> {
// **** constants ****
private static final int MIN_STACK_SIZE = 4;
private static final int GROW_SHRINK_FACTOR = 2;
// **** members ****
public int size = MIN_STACK_SIZE;
public T arr[] = null;
public int top = -1;
/*
* Constructor.
*/
@SuppressWarnings("unchecked")
public MyStack() {
this.arr = (T[])new Object[size];
}
/*
* Push value to the top of the stack.
*/
public void push(T val) {
// **** check if stack is full ****
if (isFull()) {
// **** grow the stack ****
// return;
grow();
}
// **** push element into stack ****
this.arr[++top] = val;
}
/*
* Pop top value from the stack.
*/
public T pop() {
// **** check if stack is empty ****
if (isEmpty()) {
System.out.println("pop <<< stack is empty");
return null;
}
// **** ****
T val = arr[top--];
// **** check and if needed shring the stack ****
shrink();
// **** ****
return (T)val;
}
/*
* Peek the next value in the stack
*/
public T peek() {
// **** check is stack is empty ****
if (isEmpty())
return null;
// **** ****
return (T)arr[top];
}
/*
* Check if the stack is empty.
*/
public Boolean isEmpty() {
if (this.top < 0) return true; else return false; } /* * Check if the stack is full. */ public Boolean isFull() { if (top >= (size - 1))
return true;
else
return false;
}
/*
* Grow the stack by doubling the capacity.
* The stack should be full at this time.
*/
private void grow() {
// ???? ????
System.out.println("grow <<< growing the stack...");
// **** compute the new array size ****
int prevSize = size;
int newSize = size * GROW_SHRINK_FACTOR;
// **** allocate the new array ****
@SuppressWarnings("unchecked")
T newArr[] = (T[])new Object[newSize];
// **** copy the values from the previous to the new array ****
for (int i = 0; i < prevSize; i++) newArr[i] = arr[i]; // **** update the members of the stack **** this.arr = newArr; this.size = newSize; } /* * Shrink the stack in half (if needed). */ private void shrink() { // **** check if we do NOT need to shrink the stack **** if ((size == MIN_STACK_SIZE) || (top >= (size / GROW_SHRINK_FACTOR)))
return;
// ???? ????
System.out.println("shrink <<< shrinking the stack...");
// **** compute the new array size ****
int newSize = size / GROW_SHRINK_FACTOR;
// **** allocate the new array ****
@SuppressWarnings("unchecked")
T newArr[] = (T[])new Object[newSize];
// **** copy the values from the previous to the new array ****
for (int i = 0; i < newSize; i++) newArr[i] = arr[i]; // **** update the members of the stack **** this.arr = newArr; this.size = newSize; } /* * (non-Javadoc) * @see java.lang.Object#toString() */ public String toString() { // **** check if the stack is empty **** if (isEmpty()) return "[ ] size: " + size + " top: " + top; // **** **** StringBuilder sb = new StringBuilder(); // **** to enclose elements **** sb.append("[ "); // **** build the string with elements in the stack **** for (int i = top; i >= 0; i--) {
// **** ****
sb.append(arr[i].toString());
// **** ****
if (i > 0)
sb.append(" -> ");
else
sb.append(" ] size: " + size + " top: " + top);
}
// **** return a string with the values in the stack ****
return sb.toString();
}
}
/*
* Test scaffolding.
*/
public static void main(String[] args) {
// **** instantiate our stack ****
MyStack<Integer> stack = new MyStack<Integer>();
// **** loop pushing some values into our stack ****
for (int i = 0; i < 7; i++) {
// **** push this value ****
stack.push(i * 2);
// **** peek the top element ****
System.out.println("main <<< peek: " + stack.peek());
}
// **** display the stack ****
System.out.println("main <<< stack: " + stack.toString());
System.out.println();
// **** loop poping values from the stack ****
while (!stack.isEmpty()) {
// **** peek the top element ****
System.out.println("main <<< peek: " + stack.peek());
// **** pop the top element ****
Integer val = stack.pop();
System.out.println("main <<< val: " + val);
}
// **** display the stack ****
System.out.println("main <<< stack: " + stack.toString());
System.out.println();
}
}
One of the constants MIN_STACK_SIZE is used to maintain the minimum size for the stack. In most implementations one is able to provide such value to the constructor. The stack will use that as a minimum and if needed to grow the stack it would double it per step. If that is not convenient, one may add a second parameter to the constructor to specify the size to grow per step. The use of the additional arguments would be a good exercise if you are interested.
In the grow method I commented out the return statement before the call to the grow method. If we do not wish to grow the stack we could just throw an exception indicating the maximum capacity has been reached. Note that the calculation indicating that the stack is full is performed by the isFull method. The grow method just grows the stack.
The shrink method performs similar set of steps in a similar order when we need to shrink the size of the stack. By doing this it is easier to see what is going on simplifying the work if changes need to be made during maintenance.
The toString method not only displays the elements in the stack but also the size and the top index.
The entire code for this project can be found in my GitHub repository.
At this point I have exceeded the time for a block of work. Will get up, prepare some tea and will get back to generate the post on WordPress. That should take another 30 minutes or so.
If you have comments or questions regarding this or any other post in this blog, or if you would like me to help with any phase in the SDLC (Software Development Life Cycle) of a product or service, please do not hesitate and leave me a note below. Requests for help will remain private.
Keep on reading and experimenting. It is the best way to learn and refresh your knowledge!
John
Follow me on Twitter: @john_canessa