Implement two stacks using single array in java (example)

Leave a Comment / By /
  • Given an array of integers in java.
    • Create two stacks using single array.
  • We shall able to perform push & pop operations on both stacks.
  • We will create two stacks i.e. stack1 and stack2.
    • stack1 will have following methods.
      • push1 method: push1 method will insert the element to stack1
      • pop1 method: pop1 method will remove the top element from stack1.
    • stack2 will have following methods.
      • push2 method: push2 method will insert the element to stack2.
      • pop2 method: pop2 method will remove the top element from stack2.

Example – Implement two stacks using single array in java

1.) Initial state of array (Fig 1)

  • We will take couple of indexes i.e.top1 & top2 representing top of stack1 and stack2 respectively.
  • top1 = -1 and top2 = size of array. (initial state of indexes).
implement two stack array
Fig 1: Stack’s top i.e. top1 and top2

2.) Push elements to stack1 (Fig 2)

  • Push element 5 to stack1.
    • top1 index will be increment and top1 will start pointing to zeroth index of array.
    • At zero index, the element 5 will be set i.e. arr[0] = 5
  • Push element 4 to stack1.
    • top1 index will be increment and top1 will start pointing to first index of array.
    • At first index, the element 4 will be set i.e. arr[1] = 4
push element stack
Fig 2: Push elements to stack1 (increment top1)

3.) Push elements to stack2 (Fig 3)

  • Push element 3 to stack2.
    • top2 index will be decremented and top2 will start pointing to seventh index of array.
    • At seventh index, the element 3 will be set i.e. arr[7] = 3.
  • Push element 2 to stack2.
    • top2 index will be decremented and top2 will start pointing to sixth index of array.
    • At sixth index, the element 2 will be set i.e. arr[6] = 2.
Fig 3: Push elements to stack2 (decrements top2)
Fig 3: Push elements to stack2 (decrements top2)

4.) Pop elements to stack1 (Fig 4)

  • Pop element 3 to stack1.
    • top1 is currently pointing to index 1 (refer Fig 3).
      • Take the backup of current element i.e. 3
    • top1 will be decremented and top1 will start pointing to zeroth index of array.
    • Element 3 will be returned from pop method.
  • Similarly, we can pop the elements from stack2.
Fig 4: Pop element from Stack1
Fig 4: Pop element from Stack1

Program – create two stacks using single array in java

1.) TwoStacks Class:

  • TwoStacks class primarily has following methods:
    • push1 & push2 method will insert element to stack1 & stack2 respectively.
    • pop1 & pop2 method will remove the top element from stack1 & stack2 respectively.
    • isEmpty1 & isEmpty2 method will check, whether stack1 & stack2 is empty respectively.
    • isFull method will whether stack is full and stack1 & stack2 does not have enough space to accept any entity.
package org.learn;
 
import java.util.EmptyStackException;
 
public class TwoStacks {
    private int arr[];
    private int size;
    private int index1;
    private int index2;
 
    public TwoStacks(int size) {
        this.size = size;
        arr = new int[size];
        index1 = -1;
        index2 = size;
    }
 
    public void push1(int element) {
        if (isFull()) {
            throw new StackOverflowError("TwoStacks is full");
        }
 
        arr[++index1] = element;
    }
 
    public void push2(int element) {
        if (isFull()) {
            throw new StackOverflowError("TwoStacks is full");
        }
 
        arr[--index2] = element;
    }
 
    public int pop1() {
        if (isEmpty1()) {
            throw new EmptyStackException();
        }
        int element = arr[index1];
        index1--;
        return element;
    }
 
    public int pop2() {
        if (isEmpty2()) {
            throw new EmptyStackException();
        }
        int element = arr[index2];
        index2++;
        return element;
    }
 
    public boolean isEmpty1() {
        if (index1 == -1) {
            return true;
        }
        return false;
    }
 
    public boolean isFull() {
        if (index1 == index2) {
            return true;
        }
        return false;
    }
 
    public boolean isEmpty2() {
        if (index2 == size) {
            return true;
        }
        return false;
    }
}

2.) StackClient:

  • StackClient class contains the main method and we are creating the instance of TwoStacks class.
  • We are pushing and popping the elements to/from stack1 & stack2.
package org.learn;
 
public class StackClient {
 
    public static void main(String[] args) {
        TwoStacks twoStacks = new TwoStacks(5);
        twoStacks.push1(5);
        twoStacks.push1(4);
        twoStacks.push2(3);
        twoStacks.push2(2);
        twoStacks.push2(1);
 
        System.out.printf("1. Pop elements from stack1 : ");
        while (!twoStacks.isEmpty1()) {
            System.out.printf(" %d", twoStacks.pop1());
        }
 
        System.out.printf("\n2. Pop elements from stack2 : ");
        while (!twoStacks.isEmpty2()) {
            System.out.printf(" %d", twoStacks.pop2());
        }
    }
}

Output – create two stacks using single array in java

1. Pop elements from stack1 :  4 5
2. Pop elements from stack2 :  1 2 3

You may also like:

Create or implement stack using array in java (with example)

Sort an integer array containing 0 & 1 in java (example)

Classify or segregate array containing even & odd numbers in java (example)

Find a missing number in an array of distinct integers in java (example)

Find union of two sorted integer or number arrays in java (example)

Reverse an integer array in java using iterative & recursive algorithm

Find maximum sum subarray in java using Kadane’s algorithm