Implement two stacks using single array in java (example)

• 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).

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

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.

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.

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