Java Program to Implement Two Stacks in an Array

In this section, we will create a Java program that implemnts two stacks in an array.

The meaning of two stack means both the stacks should use the same array for keeping the elements. The following are a few methods that must be implemented by those two stacks.

push1(int i) -> pushes i into the first stack

push2(int j) -> pushes j into the second stack

pop1() -> removes the top element from the first stack and then returns the element that is popped.

pop2() -> removes the top element from the second stack and then returns the element that is popped.

Note: Implementation of the two stacks should be space-efficient.

Naive Approach

The simple approach is to divide the given array into two halves and then use those halves as the stack. However, it may lead to non-efficient use of the memory. For example, let's assume the size of the given array is 6. Thus, each stack will have a size of 3. Also, assume that we have to push 4 elements in the first stack and 1 element in the second stack. We can easily put 1 element in the second stack.

However, we can only push 3 elements in the first stack. Pushing the 4^th element will cause overflow. Ideally, it should not happen as there are some vacant regions (space for 2 elements is still empty) in the second stack, which can be utilized. However, we can not use it for the first stack as it is already assigned to the second. Therefore, we can say that the simple approach implementation of the two stacks will not be space-efficient.

To make the implementation space efficient, it is required to allocate the space of the two stacks as per the need. The concept is to begin the two stacks from the two extreme sides of the input arr[]. Stack 1 begins from the leftmost side, which means the first element in stack 1 is pushed at the index 0. Stack 2 begins from the rightmost side. The first element in stack 2 is pushed at the index size - 1.

Both the stacks shrink or grow in the opposite direction. For checking the overflow, one needs to look after the space between elements that are residing at the top of both the stacks. The following program shows the same.

FileName: TwoStacksArray.java

Output:

The popped element from the stack 1 is: 191 The popped element from the stack 2 is: 40 

Complexity Analysis: For the push and pop operation, constant time is taken. Hence, for the operations, the time complexity is O(1).