Three stacks in a single array

Question

I have implemented three stacks in a single array in Java. Any advice on object oriented design, coding structure, logical part or any sort of advice would be appreciated.

public class ThreeStack {
 private int[] stack;
 private int first, last, mid;
 private final int midPosition;
 public ThreeStack(int size) {
 stack = new int[size];
 first = -1; last = size; mid = (first + last) >> 1;
 midPosition = mid;
 }
 //push
 public boolean pushFirstStack(final int val) {
 if (first + 1 < midPosition) {
 stack[++first] = val;
 return true;
 } else {
 return false;
 }
 }
 public boolean pushSecondStack(final int val) {
 if (mid + 1 < last) {
 stack[++mid] = val;
 return true;
 } else {
 return false;
 }
 }
 public boolean pushThirdStack(final int val) {
 if (last - 1 > mid) {
 stack[--last] = val;
 return true;
 } else {
 return false;
 }
 }
 //pop
 public int popFirstStack() {
 if (first < 0) {
 return Integer.MIN_VALUE;
 } else {
 int val = stack[first];
 stack[first--] = 0;
 return val;
 }
 }
 public int popSecondStack() {
 if (mid < midPosition) {
 return Integer.MIN_VALUE;
 } else {
 int val = stack[mid];
 stack[mid--] = 0;
 return val;
 }
 }
 public int popThirdStack() {
 if (last >= stack.length) {
 return Integer.MIN_VALUE;
 } else {
 int val = stack[last];
 stack[last++] = 0;
 return val;
 }
 }
 //size
 public int firstStackSize() {
 return mid - midPosition;
 }
 public int secondStackSize() {
 return last - mid;
 }
 public int lastStackSize() {
 return secondStackSize();
 }
 public void printStack() {
 for (int i = 0; i < stack.length; i++) {
 System.out.print(stack[i]);
 System.out.print((i == first || i == mid || i == last) ? "*": "");
 System.out.print(" ");
 }
 System.out.println();
 }
}

Main Method

public class MainClass {
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 ThreeStack stack = new ThreeStack(12);
 while (true) {
 stack.printStack();
 menu();
 int c = in.nextInt();
 switch (c) {
 case 1:
 stack.pushFirstStack(in.nextInt());
 break;
 case 2:
 stack.pushSecondStack(in.nextInt());
 break;
 case 3:
 stack.pushThirdStack(in.nextInt());
 break;
 case 4:
 printPopVal(stack.popFirstStack());
 break;
 case 5:
 printPopVal(stack.popSecondStack());
 break;
 case 6:
 printPopVal(stack.popThirdStack());
 break;
 }
 }
 }
 static void menu() {
 System.out.println("+------------------------------+");
 System.out.println("1 -> push first stack");
 System.out.println("2 -> push second stack");
 System.out.println("3 -> push third stack");
 System.out.println("4 -> pop first stack");
 System.out.println("5 -> pop second stack");
 System.out.println("6 -> pop third stack");
 System.out.println("+------------------------------+");
 }
 static void printPopVal(int val) {
 System.out.println("Pop : " + val);
 }
}

• 200_success: Why would you want to do this?
• Aluan Haddad: I'd be curious as to the purpose of this code. If you simply want three stacks that all consume from a single fixed element count, there are much simpler ways to write this code. If the purpose is optimization via a shared buffer, there are also simpler ways to write it but they would be different. Finally, it's not clear what a ThreeStack is.
• Muztaba Hasanat: @AluanHaddad I was trying to implement ThreeStack in more oo and optimized way. That is way I posted in here to get a better idea in design as well as in performance. If you would provide any better design or optimization that will be appreciated. :)
• Aluan Haddad: @seal Take a look at my answer, it uses delegation and allows the stack sizes to vary independently.

Answer 1

Stack sizing

The 3 stacks have different size limits:

• The 1st stack can have maximum size / 2 elements
• The 2nd and 3rd stacks share their storage, they can have size / 2 elements

When there is a peculiar limitation like this, it's good to document it, and hopefully with an explanation of the reasoning.

An alternative approach could have been giving each stack size / 3 space.

Another alternative would be using an array of StackNode objects, where StackNode would store the payload, and a link to the StackNode above it. This way all stacks would have dynamic size, until their total use reaches the capacity of the StackNode array. However, in addition to the extra storage needed (for the links), the logic would be also more complicated to account for the freed spots in the array.

Make final what you can

This field can be final:

private int[] stack;

One statement per line

It's best when you can read code from top to bottom. When there are multiple statements per line, it's easy to overlook the right end. So instead of putting multiple assignments on the same line like this:

first = -1; last = size; mid = (first + last) >> 1;

It would be better to break it up, to have one statement per line.

Clever code

This code is a bit clever:

mid = (first + last) >> 1;

It's best to keep things simple and natural:

mid = (first + last) / 2;

Sure, bit shifting is faster than division. But it's reasonable to expect the compiler to automatically convert / 2 to use bit shifting instead of division, so that you can write simple, natural, unsurprising code. (I don't know if the compiler actually does that, but in any case, such micro-optimization is likely to be pointless pedantry anyway.)

• Muztaba Hasanat: thanks for the reply. I did not understand what do mean by StackNode and how it would help to make the stack dynamic. Sorry for my bad English understanding. Did you say something like this - int[][] StackNode = new int[3][1]; StackNode[0] = new int[10];

Answer 2

If the desire is simply to provide a type that encapsulates a triple of homogeneous Stacks. There are a few ways to go about it that will be easier to consume and better encapsulated.

interface ThreeStack<T> {
 void pushFirst();
 void pushSecond();
 void pushThird();
 T popFirst();
 T popSecond();
 T popThird();
 int getFirstSize();
 int getSecondSize();
 int getThirdSize();
}
class ThreeStackImplementation<T> implements ThreeStack<T> {
 public ThreeStackImplementation() {
 first = new Stack<T>();
 second = new Stack<T>();
 third = new Stack<T>();
 }
 public void pushFirst(T obj) { first.push(obj); }
 public void pushSecond(T obj) { second.push(obj); }
 public void pushThird(T obj) { third.push(obj); }
 public T popFirst() throws EmptyStackException { return first.pop(); }
 public T popSecond() throws EmptyStackException { return third.pop(); }
 public T popThird() throws EmptyStackException { return third.pop(); }
 public int getFirstSize() { return first.size(); }
 public int getSecondSize() { return second.size(); }
 public int getThirdSize() { return third.size(); }
 private final Stack<T> first;
 private final Stack<T> second;
 private final Stack<T> third;
}

I have removed the size argument because it was not clear what it represented in the original code. It could have meant maximum size of all three stacks combined, as was the case, but this was not obvious from the public interface exposed by the class. Additionally, one does not expect a Stack to have an upper bound beyond what is dictated by the VM.

I would argue that the alternative presented is closer to the notion of a type that is composed of three stacks and that composition is inherent in the name of the type.

If you desire a more performance oriented implementation, with upper bounded stack sizes you could allow a different size to be specified for each by taking 3 constructor arguments. However, the type would no longer meet the commonly understood definition of a stack which generally does not have an upper bound.

With regard to sharing a single array as the underlying store, performance is the only likely reason that would make sense. In this case I would consider following @janos' advice.

• Mathieu Guindon: Can you expand on how this very simple example is easier to consume and better at OOP than the OP's code? Reviewing code should be about the OP; if you present an alternative solution, you should relate it to the OP and explain in what ways it's better than the OP and what problems with the original code the alternative approach is solving.
• Aluan Haddad: For one thing, it simply represents 3 stacks in a single data structure, without exposing unnecessary details about them. Each stack may grow independently
• Aluan Haddad: The op said in a comment that he was trying to implement ThreeStack in more oo and optimized way. I feel this code is more oo in the sense that it does not have a shared size argument which exists as an implementation detail. Furthermore, I say it is simple because it delegates it behavior to 3 internal stack objects which maintain their state independently, freeing TheeStacks from their management. See my edited reply
• Mathieu Guindon: Well done, have an upvote! :-)