Data structures and algorithms in Java

I have previously discussed various stack related topics such as operations that can be performed on the stack, the implementations of stack using other data structures such as array and linked list, retrieving the minimum element of the stack in constant time with and without auxiliary stack and few other topics. In this post I will be discussing about the implementation of two stacks using a single array.

Prerequisites:

Knowledge of basic data structures, working of stack data structure, arrays. Knowledge of performance complexity is also required.

Explanation:

The idea behind the implementation is that both the stacks will use the same array. A question that can come to our mind would be, how do we divide the array so that we can have two stacks in it?

An easy solution would be to divide the array into two halves. The first half will be treated as the first stack and the second half as the second stack. Consider if the size of the array arr is N. The first stack will be from arr[0] to arr[N/2] and second stack will be from arr[(N/2) +1] till arr[N-1]. But this approach has a drawback that if elements are pushed to stack1 and if the stack1 gets full, it will show a stack overflow error even when space is left in the array i.e. in stack2.

A more efficient way is to have two pointers top1 and top2 which will point to the start and end index of the array and as we push the elements to the stacks we increment or decrement the pointers. Consider top1 pointing at index 0 of the array and top2 pointing at index N-1 of the array. If an element is pushed to stack1 then pointer top1 is incremented and element is stored at stack[top1] and if an element is pushed to stack2 then pointer top2 is decremented and the element is stored at stac[top2]. The array or the stacks are considered full when top1 and top2 are adjacent to each other.

Algorithm:

1. Create an array of SIZE = N and create two variables top1 and top2 representing the two top pointers of the stacks.
2. Initialize top1 = -1 and top2 = N.
3. To push an element in stack1 i.e. push1(int val), check if the array is full by verifying top2-top1 == 1. If the stack is not full then increment the top1 pointer and store val in stack[top1]. If top2-top1 == 1, then both the pointers will be adjacent to each other, which means the array is full.
4. To push an element in stack2 i.e. push2(int val), check if the array is full by verifying top2-top1 == 1. If the stack is not full then decrement top2 pointer and store val in stack[top2].
5. To pop an element from stack1, check if the stack1 is empty by verifying top1 == -1. If the stack is not empty then pop an element by decrementing top1 by 1.
6. To pop an element from stack2, check if the stack2 is empty by verifying top2 == N. If the stack is not empty then pop an element by incrementing top2 by 1.

Diagrammatic representation:

Code implementation:

public class TwoStacksUsingArray {

	int stack[];
	int top1, top2, N;

	// initialization
	TwoStacksUsingArray(int size) {
		N = size;
		top1 = -1;
		top2 = N;
		stack = new int[N];

	}

	// push an element at top1 end
	private void push1(int val) {
		// check if the array is full or not
		if (isFull()) {
			System.out.println("Array is full, cannot push element");
		} else {
			top1++;
			stack[top1] = val;
			System.out.println("Element pushed at top1 = " + stack[top1]);
		}
	}

	// push an element at top2 end
	private void push2(int val) {
		if (isFull()) {
			System.out.println("Array is full, cannot push element");
		} else {
			top2--;
			stack[top2] = val;
			System.out.println("Element pushed at top2 = " + stack[top2]);
		}
	}

	// pop an element from top1 end
	private void pop1() {
		if (isStack1Empty()) {
			System.out.println("Cannot pop element, array is empty");
		} else {
			System.out.println("Element popped from top1 = " + stack[top1]);
			top1--;
		}
	}

	// pop an element from top2
	private void pop2() {
		if (isStack2Empty()) {
			System.out.println("Cannot pop element, array is empty");
		} else {
			System.out.println("Element popped from top2 = " + stack[top2]);
			top2++;
		}
	}

	// peek an element at top1
	private void peek1() {
		if (isStack1Empty()) {
			System.out.println("Cannot peek element from top1, stack is empty");
		} else {
			System.out.println("Element peeked at top1 = " + stack[top1]);

		}
	}

	// peek an element at top2
	private void peek2() {
		if (isStack2Empty()) {
			System.out.println("Cannot peek element from top2, stack is empty");
		} else {
			System.out.println("Element peeked at top2 = " + stack[top2]);

		}
	}

	// check if the array is full
	private boolean isFull() {
		return (top2 - top1) == 1;
	}

	// check if stack1 is empty
	private boolean isStack1Empty() {
		return top1 == -1;
	}

	// check if stack2 is empty
	private boolean isStack2Empty() {
		return top2 == N;
	}

	public static void main(String[] args) {
		TwoStacksUsingArray s = new TwoStacksUsingArray(5);
		s.push1(5);
		s.push2(10);
		s.push2(15);
		s.push1(11);
		s.push2(7);
		s.push1(10);

		s.pop1();
		s.pop1();
		s.peek1();
		s.peek2();
		s.pop2();
		s.peek2();

	}

}

Code output:

Element pushed at top1 = 5
Element pushed at top2 = 10
Element pushed at top2 = 15
Element pushed at top1 = 11
Element pushed at top2 = 7
Array is full, cannot push element
Element popped from top1 = 11
Element popped from top1 = 5
Cannot peek element from top1, stack is empty
Element peeked at top2 = 7
Element popped from top2 = 7
Element peeked at top2 = 15

Performance complexity:

Time complexity of all four operations push1, push2, pop1, pop2 is O(1) i.e. constant time complexity.

Link to the above code on my github profile, 2 stacks using an array.

Thank you so much for reading. I hope the post helped you to learn something new. Your feedback is highly appreciated.