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.
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.
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.
References
