!!! NOTE !!! For some reason I was not able to post the photos I took of the white board.
!!! UPDATE !!! Was able to download and place a different photo of the entire whiteboard.
Once again it is Saturday. My wife and one of her girl friends went out shopping. I still do not understand the attraction of shopping. I guess it works the same way when I wish to stay home working with my computers. Of course if my wife is not out and about I would not be able to be in my home office. Seems like a good arrangement after all.
Yesterday morning the computer I ordered for starting to experiment with Kinect and Azure was delivered home. I have all the pieces so after my wife arrives will be making place in my home office to bring down and connect the components. Hopefully all will go well and I will be able to start experimenting tomorrow morning. I can’t wait.
Yesterday afternoon I donated blood to the Red Cross. I do it twice a year in 
spring and fall. Yesterday was my first pint for the third gallon of blood. I am planning to continue giving blood for the next few decades. Will see how that goes.
OK, enough chit chat. Let’s get down to the main subject for this post. The post is based on question 3.1 from the book “Cracking the Coding Interview” by Gayle Laakmann McDowell. The text for the question follows: Describe how you could use a single array to implement three stacks. The question seems pretty vague to me. You would have to get some clarification from the interviewer. The book presents a set of hints to replace the interviewer. I read the first one and went to my whiteboard which is in a different room at home.
I started by drawing on the top left of the whiteboard an array. To implement a single stack you could use an array, a variable to track the top and the size of the array. In this case we have a single stack. If we would like to implement three stacks we would have to share the single array and keep a set of variables to track the top, the index for the min index and the max index for each array.
As you can see I started by splitting the array into three equal parts. In the bottom left section of the image I draw my approach. I then used the right side of the board to come up with constants and variables that we could use to implement such code. I separated two class members to keep track of the array and three instance variables to track the top, min index and max index.
The questions states that one needs to describe how to get three stacks using a single array. To me the key is in the constructor. The rest of the methods would be simpler to implement. Not sure how many methods would the interviewer request based on the allotted time. I just went with the constructor.
I decided to go with a generic class which I named MyStack. It did not take too much to figure out that it was a better idea to have a size argument passed to it. That way the stacks could be of different sizes. I figured it would look better and should not take much from the point of view of calculations.
We first need to make sure that the requested size fits in the array. If it does not, throw an exception.
We then update / set the instance members. We set the min, max and top variables.
Lastly we allocate the actual array if we had not done it yet. The allocation would occur in the first instantiation of a stack. We then update the used variable which keeps track of the contiguous elements in the array that we have used for a stack.
Now let’s look at the actual Java code which I wrote using the Eclipse IDE.
main <<< firstStack.capacity: 7 main <<< firstStack: [ N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, ] main <<< firstStack: [ ] min: 0 max: 6 top: -1 main <<< firstStack.array: [ 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 ] min: 0 max: 6 top: 6 main <<< firstStack: [ 0, 1, 2, 3, 4, 5, 6, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, N, ] main <<< secondStack.capacity: 11 main <<< secondStack: [ ] min: 7 max: 17 top: 6 main <<< thirdStack.capacity: 13 main <<< thirdStack: [ ] min: 18 max: 30 top: 17 main <<< thirdStack: [ 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 ] min: 18 max: 30 top: 30 main <<< thirdStack: [ 0, 1, 2, 3, 4, 5, 6, N, N, N, N, N, N, N, N, N, N, N, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] main <<< secondStack: [ 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 ] min: 7 max: 17 top: 17 main <<< firstStack: [ 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ] main <<< fisrtStack.peek: 6 main <<< firstStack.pop: 6 main <<< fisrtStack.peek: 5 main <<< firstStack.pop: 5 main <<< fisrtStack.peek: 4 main <<< firstStack.pop: 4 main <<< fisrtStack.peek: 3 main <<< firstStack.pop: 3 main <<< fisrtStack.peek: 2 main <<< firstStack.pop: 2 main <<< fisrtStack.peek: 1 main <<< firstStack.pop: 1 main <<< fisrtStack.peek: 0 main <<< firstStack.pop: 0 main <<< secondStack.peek: 10 main <<< secondStack.pop: 10 main <<< secondStack.peek: 9 main <<< secondStack.pop: 9 main <<< secondStack.peek: 8 main <<< secondStack.pop: 8 main <<< secondStack.peek: 7 main <<< secondStack.pop: 7 main <<< secondStack.peek: 6 main <<< secondStack.pop: 6 main <<< secondStack.peek: 5 main <<< secondStack.pop: 5 main <<< secondStack.peek: 4 main <<< secondStack.pop: 4 main <<< secondStack.peek: 3 main <<< secondStack.pop: 3 main <<< secondStack.peek: 2 main <<< secondStack.pop: 2 main <<< secondStack.peek: 1 main <<< secondStack.pop: 1 main <<< secondStack.peek: 0 main <<< secondStack.pop: 0 main <<< thirdStack.peek: 12 main <<< thirdStack.pop: 12 main <<< thirdStack.peek: 11 main <<< thirdStack.pop: 11 main <<< thirdStack.peek: 10 main <<< thirdStack.pop: 10 main <<< thirdStack.peek: 9 main <<< thirdStack.pop: 9 main <<< thirdStack.peek: 8 main <<< thirdStack.pop: 8 main <<< thirdStack.peek: 7 main <<< thirdStack.pop: 7 main <<< thirdStack.peek: 6 main <<< thirdStack.pop: 6 main <<< thirdStack.peek: 5 main <<< thirdStack.pop: 5 main <<< thirdStack.peek: 4 main <<< thirdStack.pop: 4 main <<< thirdStack.peek: 3 main <<< thirdStack.pop: 3 main <<< thirdStack.peek: 2 main <<< thirdStack.pop: 2 main <<< thirdStack.peek: 1 main <<< thirdStack.pop: 1 main <<< thirdStack.peek: 0 main <<< thirdStack.pop: 0 main <<< thirdStack: [ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 ]
The capture from the console of the Eclipse IDE when running a test program start by instantiating three stacks of different sizes. We display their capacity. The first stack is able to hold 7 elements, the second 11 and the third 13. The stacks are empty and we display the contents. We then push some elements until each stack is full. We the loop peeking and then popping elements until the stacks become empty.
/*
* Test scaffolding.
*/
public static void main(String[] args) throws Exception {
// **** instantiate the first stack ****
int size = 7;
MyStack<Integer> firstStack = new MyStack<Integer>(size);
// **** display the capacity of the first stack ****
System.out.println("main <<< firstStack.capacity: " + firstStack.capacity());
// **** display the contents of the array ****
System.out.println("main <<< firstStack: " + firstStack.array() + "\n");
// **** display the contents of the first stack ****
System.out.println("main <<< firstStack: " + firstStack.toString());
// **** push elements into the first stack ****
int i = 0;
while (!firstStack.isFull()) {
firstStack.push(i++);
}
// **** display the contents of the first stack ****
System.out.println("main <<< firstStack.array: " + firstStack.toString() + "\n");
// **** display the contents of the array ****
System.out.println("main <<< firstStack: " + firstStack.array() + "\n");
// **** instantiate the second stack ****
size = 11;
MyStack<Integer> secondStack = new MyStack<Integer>(size);
// **** display the capacity of the second stack ****
System.out.println("main <<< secondStack.capacity: " + secondStack.capacity());
// **** display the contents of this stack ****
System.out.println("main <<< secondStack: " + secondStack.toString() + "\n");
// *** instantiate third stack ****
size = 13;
MyStack<Integer> thirdStack = new MyStack<Integer>(size);
// **** displat the capacity of the third stack ****
System.out.println("main <<< thirdStack.capacity: " + thirdStack.capacity());
// **** display the contents of this stack ****
System.out.println("main <<< thirdStack: " + thirdStack.toString());
// **** push elements into the third stack ****
i = 0;
while (!thirdStack.isFull())
thirdStack.push(i++);
// **** display the contents of this stack ****
System.out.println("main <<< thirdStack: " + thirdStack.toString() + "\n");
// **** display the contents of the array ****
System.out.println("main <<< thirdStack: " + thirdStack.array() + "\n");
// **** push elements into the second stack ****
i = 0;
while (!secondStack.isFull())
secondStack.push(i++);
// **** display the contents of this stack ****
System.out.println("main <<< secondStack: " + secondStack.toString() + "\n");
// **** display the contents of the array ****
System.out.println("main <<< firstStack: " + secondStack.array() + "\n");
// **** pop elements from the first stack ****
while (!firstStack.isEmpty()) {
System.out.println("main <<< fisrtStack.peek: " + firstStack.peek());
System.out.println("main <<< firstStack.pop: " + firstStack.pop());
}
System.out.println();
// **** pop elements from the second stack ****
while (!secondStack.isEmpty()) {
System.out.println("main <<< secondStack.peek: " + secondStack.peek());
System.out.println("main <<< secondStack.pop: " + secondStack.pop());
}
System.out.println();
// **** pop elements from the third stack ****
while (!thirdStack.isEmpty()) {
System.out.println("main <<< thirdStack.peek: " + thirdStack.peek());
System.out.println("main <<< thirdStack.pop: " + thirdStack.pop());
}
System.out.println();
// **** display the contents of the array ****
System.out.println("main <<< thirdStack: " + thirdStack.array());
}
We allocate the first stack with a capacity of 7 elements. The stack is displayed. As we saw in the console capture the stack is empty. We push some elements until the stack is full. Given that the capacity is 7 we should only have 7 elements. We can verify this by the output on the console.
We allocate the second stack using the same array. The capacity we chose is 11. We display the contents of the stack. We verify that we have no elements. Note that following the element brackets we display the min, max and top. You can verify that the proper sections of the array are being used.
The last stack was declared with a capacity of 13 elements.
// **** array size **** private final int ARRAY_SIZE = (7 + 11 + 13); // **** per class members **** private static Object[] arr = null; private static int used = -1; // **** per instance members **** private int min = -1; private int max = -1; private int top = -1;
We have declared the size of our array to be the exact values that sum up to the size of each stack. We could have just allocated an array of 100 elements and let the array be under used. We could also have declared more stacks. There is nothing that prevents us from doing so except the capacities of the individual stacks.
We have declared a constant, some class members and some instance members. The class members are used to allocate and manage the array. The instance variables are used to manage each individual stack.
/*
* Constructor
*/
public MyStack(int stackSize) throws Exception {
// **** check argument ****
if (stackSize + used >= ARRAY_SIZE)
throw new Exception("invalid argument stackSize: " + stackSize);
// **** set instance members ****
this.min = used + 1;
this.max = this.min + stackSize - 1;
this.top = this.min - 1;
// **** update class members ****
if (arr == null) {
arr = new Object[ARRAY_SIZE];
init();
}
used += stackSize;
}
For the constructor we first check the requested capacity. If we do not have enough space left in the array we throw an exception.
We the set the instance variables followed by the class ones.
Note the init method. This is used to initialize all entries in the array to -1. Yes, with additional time we could have initialized differently because this is a generic class. The reason for this initialization is to have some default values. We could have left them null and just print a ‘N’ or something along those lines.
Please note that I have been modifying the code and adding features as I generate this post. If things do not match you can always go to my GitHub repository and get the final version of the code I wrote for this post.
/*
* Push element into the stack
*/
public void push(int item) throws Exception {
// **** check if stack is full ****
if (isFull())
throw new Exception("stack is full");
// **** push element into stack ****
arr[++top] = item;
}
/*
* Pop element from the stack
*/
@SuppressWarnings("unchecked")
public T pop() throws Exception {
T item = null;
// **** check if stack is empty ****
if (isEmpty())
throw new Exception("stack is empty");
// **** pop item ****
item = (T)arr[top];
// **** clear the entry in the array ****
arr[top] = -1;
// **** adjust top ****
top--;
// **** return item ****
return item;
}
/*
* Check if the stack is empty
*/
public boolean isEmpty() {
if (this.top < this.min) return true; else return false; } /* * Check if the stack is full */ public boolean isFull() { if (this.top >= this.max)
return true;
else
return false;
}
/*
* Peek top element in stack
*/
@SuppressWarnings("unchecked")
public T peek() throws Exception {
// **** check if stack is empty ****
if (isEmpty())
throw new Exception("stack is empty");
// **** ****
return (T)arr[this.top];
}
The push, pop, isEmpty, isFull and peek are standard in most stack implementations. Note that on the pop method we are clearing the returned value from the array. Not doing so could cause a potential vector for collecting data from hackers. I will not say more about the rest of the methods in this group.
/*
* Return string with contents of the stack.
*/
public String toString() {
// **** for efficiency ****
StringBuilder sb = new StringBuilder("[ ");
// **** append stack elements ****
for (int i = this.min; i <= this.top; i++) {
if (i < this.top) sb.append(arr[i].toString() + " -> ");
else
sb.append(arr[i].toString() + " ");
}
// **** ****
sb.append("]");
// **** add stack variables ****
sb.append(" min: " + this.min);
sb.append(" max: " + this.max);
sb.append(" top: " + this.top);
// **** return the string ****
return sb.toString();
}
/*
* Return the capacity of the stack.
*/
public int capacity() {
return this.max - this.min + 1;
}
/*
* Initialize the array (for testing purpose only).
*/
private void init() {
// for (int i = 0; i < arr.length; i++) {
// arr[i] = -1;
// }
}
/*
* Build a string with the contents of the array.
* (For testing purpose only).
*/
public String array() {
// **** ****
StringBuilder sb = new StringBuilder("[ ");
// **** display the contents of the array (not the stack) ****
for (int i = 0; i < arr.length; i++) {
if (i < arr.length - 1) {
if (arr[i] == null)
sb.append("N, ");
else
sb.append(arr[i].toString() + ", ");
}
else {
if (arr[i] == null)
sb.append("N, ");
else
sb.append(arr[i].toString() + " ");
}
}
// **** ****
sb.append("]");
// **** ****
return sb.toString();
}
The toString was added to be able to display the contents of the stacks. This is a simple way to check if things are working as expected. The console output shows multiple uses of this method.
The capacity method was added to verify that the returned value matched what was passed to the constructor.
The init method was used to initialize the array used by the stacks. At some point I removed it by commenting out the body. The actual call was left in the constructor.
Finally the array method is used to display the contents of the entire array. This method was also added for testing purposes.
The entire code for this project can be found in my GitHub repository.
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