How to implement 3 stacks in an array [Practical Examples]

Implement three stacks in an array

A Stack is a Last in First out(LIFO) data structure. Push and pop operations are used for insertion and deletion of a value from the stack respectively. In order to implement three stacks in an array, there are two different approaches that can be used. In the first approach, we will need to divide the array into three equal parts and use the starting position of the part as a base of the stack. The limitation of this approach is, if the middle stack becomes full, either we need to stop further push operation or shift the whole middle stack to left by some position if the first stack is empty enough. The other approach is to start first stack from 0, middle stack from mid position and last stack from the last position in the array.

 

Approach 1 : Divide an array into three equal parts

In this approach to implement three stacks in an array, our array is divided as shown in the figure below. Here, we will have all the three stacks of fix size that is equal to total size of an array divided by 3. It will fill up the values from left to right. The disadvantage of this approach is if one of the stack gets full, it will not allow any further push operation on that stack. Although there is empty space in the other stack, it will not utilize the empty slots due to fixed size.
Approach 1 - three stacks in an array

Advertisement

 

Implementation

// Program to implement three stacks in an array
public class Main {
    // Creating stack, top, starting and ending array as class variables
    static int stack[];
    static int top[];
    static int starting[];
    static int ending[];

    // Defining the size of an array
    static int max = 30;

    public static void main(String[] args) {
        stack = new int[max];
        top = new int[3];
        starting = new int[3];
        ending = new int[3];

        Main m = new Main();
        int k = 0;

        // Loop to initialize starting, ending and top of each array
        for (int i = 0; i < 3; i++) {
            starting[i] = k;
            top[i] = k;
            k = k + max / 3;
            ending[i] = k - 1;
        }

        // Pushing values on different stacks
        m.push(10, 1);
        m.push(1, 0);
        m.push(100, 2);
        m.push(200, 2);
        m.push(2, 0);
        m.push(20, 1);

        // Displaying the content
        m.display();

        // Popping the values
        m.pop(1);
        m.pop(2);

        // Display the content after pop
        m.display();
    }

    // Function to return the top of a given stack
    int gettop(int stno) {
        return top[stno];
    }

    // Push function to push value on the specified stack
    void push(int val, int stno) {

        if (gettop(stno) <= ending[stno]) {
            stack[top[stno]] = val;
            top[stno] = top[stno] + 1;
        } else {
            System.out.println("Stack is full");
        }
    }
    // Function to pop the value out from the specified stack 
    void pop(int stno) {
        if (gettop(stno) >= starting[stno]) {
            top[stno] = top[stno] - 1;
            System.out.println("\nValue popped out is " + stack[top[stno]]);
            stack[top[stno]] = 0;
        } else {
            System.out.println("Stack is empty");
        }
    }

    // Function to display the content of all stacks
    void display() {
        int j = 0;
        for (int i = 0; i < max; i++) {
            if (j < 3 && i == starting[j]) {
                System.out.println("\n\nPrinting stack " + j);
                j++;
            }
            System.out.print(stack[i] + " ");
        }
    }
}

Output

Printing stack 0
1 2 0 0 0 0 0 0 0 0 
Printing stack 1
10 20 0 0 0 0 0 0 0 0 
Printing stack 2
100 200 0 0 0 0 0 0 0 0 
Value popped out is 20
Value popped out is 200
Printing stack 0
1 2 0 0 0 0 0 0 0 0 
Printing stack 1
10 0 0 0 0 0 0 0 0 0 
Printing stack 2
100 0 0 0 0 0 0 0 0 0 

 

Approach 2 : Divide an array such that last two stacks share the array space

In this approach to implement three stacks in an array, our array is divided as shown in the figure below. Here, we will have the first stack of fix size while the other two stacks share the empty space. That means, last stack will start filling in from the highest position. The advantage of this approach over the first is, as they share the empty slots, resource utilization is better than the first approach. However, for stack 0 the size will be fixed. Hence, it will allow stack 1 and stack 2 to share the common space to perform push and pop operations.
Approach 2 - Three stacks in an array

 

Implementation

// Program to implement three stacks in an array
public class Main {
    // Creating stack and top array as class variables
    static int stack[];
    static int top[];

    // Defining the size of an array
    static int max = 30;

    public static void main(String[] args) {
        stack = new int[max];
        top = new int[3];

        Main m = new Main();
        int k = 0;

        // Initialize top of each array
        top[0] = 0;
        top[1] = max / 3 + 1;
        top[2] = max - 1;

        // Pushing values on different stacks
        m.push(10, 1);
        m.push(1, 0);
        m.push(100, 2);
        m.push(200, 2);
        m.push(2, 0);
        m.push(20, 1);

        // Displaying the content
        m.display();

        // Popping the values
        m.pop(1);
        m.pop(2);

        // Display the content after pop
        m.display();
    }

    // Function to return the top of a given stack
    int gettop(int stno) {
        return top[stno];
    }

    // Push function to push value on the specified stack
    void push(int val, int stno) {
        stack[top[stno]] = val;
        // if it is stack 2 then decrement the value of top otherwise increment the value of top
        if (stno == 2)
            top[stno] = top[stno] - 1;
        else
            top[stno] = top[stno] + 1;
    }

    // Function to pop the value out from the specified stack
    void pop(int stno) {
        // if it is stack 2 increment the value of top otherwise decrement the value of top
        if (stno == 2)
            top[stno] = top[stno] + 1;
        else
            top[stno] = top[stno] - 1;
        System.out.println("\nValue popped out is " + stack[top[stno]]);
        stack[top[stno]] = 0;

    }

    // Function to display the content of all stacks
    void display() {
        int i, j = 0;
        System.out.println("\n\nPrinting stack 0");
        for (i = 0; i < top[j]; i++) {
            System.out.print(stack[i] + " ");
        }
        j++;
        System.out.println("\n\nPrinting stack 1");
        i = max / 3 + 1;
        for (; i < top[j]; i++) {
            System.out.print(stack[i] + " ");
        }
        System.out.println("\n\nPrinting stack 2");
        j++;
        i = max - 1;
        for (; i > top[j]; i--) {
            System.out.print(stack[i] + " ");
        }
    }
}

Output

Printing stack 0
1 2 
Printing stack 1
10 20 
Printing stack 2
100 200 
Value popped out is 20
Value popped out is 200
Printing stack 0
1 2 
Printing stack 1
10 
Printing stack 2
100

 

Summary

The Implementation of three stacks in an array is very useful while working on real time applications. In many situations, we will need to implement multiple stacks in an array. In this tutorial, we covered two different approaches to implement three stacks in an array. We learned in detail about this with a executed code. All in all, this tutorial, covers everything that you need to know in order to have a clear view on how to implement three stacks in an array using Java.

Advertisement

 

References

Classes in Java

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment

X