Learn-dsa..in 30 days!



























CC-6 : Implement 2 Stacks using Array.

Description:

Implement 2 Stacks using single Array.

Test cases and expected outputs:

Input Parameters Expected outputs
StacksUsingArray stack=new StacksUsingArray();
System.out.print("Add to Stack1");
stack.addSt1(9);
System.out.print("Add to Stack1");
stack.addSt1(14);
System.out.print("Add to Stack1");
stack.addSt1(17); 		Stacks Array : 9,14,17,0,0,0,0,0,0,0
System.out.print("Add to Stack2");
stack.addSt2(34);
System.out.print("Add to Stack2");
stack.addSt2(21);
System.out.print("Add to Stack2");
stack.addSt2(28);
System.out.print("Add to Stack2");
stack.addSt2(35);
System.out.print("Add to Stack2");
stack.addSt2(92);
System.out.print("Add to Stack2");
stack.addSt2(10);
System.out.print("Add to Stack2");
stack.addSt2(12);
System.out.print("Add to Stack2");
stack.addSt2(44);
System.out.print("Add to Stack2");
stack.addSt2(44); 		Stacks Array : 9,14,17,12,10,92,35,28,21,34

Pseudocode:

The data structure will use an array for storing data elements. It will maintain two stacks St1 and St2. St1 will start from 0 index and additional elements will be added in rightward indices. St2 will start from last index of array and additional elements will be added in leftward indices.
Maintain int variable lastIdxSt1 to track last index of stack St1.Similarly, maintain int variable lastIdxSt1 to store last index of stack St2.
addSt1() method: if lastIdxSt1 is one less than size of storage array or is one less than lastIdxSt2, then the array is full and no new element can be added, so return false. Else, increment lastIdxSt1 by 1 and store new data at index lastIdxSt1.
addSt2() method: if lastIdxSt2 is equal to -1 or is one more than lastIdxSt1, then the array is full and no new element can be added, so return false. Else, decrement lastIdxSt2 by 1 and store new data at index lastIdxSt2.
removeSt1() method: if lastIdxSt1 is equal to -1, then St1 is empty , so return a value indicating this. Else, return value at index lastIdxSt1, set value of data at index lastIdxSt1 to 0 and decrement lastIdxSt1 by 1.
removeSt2() method: if lastIdxSt1 is equal to length of storage array, then St2 is empty , so return a value indicating this. Else, return value at index lastIdxSt2, set value of data at index lastIdxSt2 to 0 and increment lastIdxSt2 by 1.

Code:

public class StacksUsingArray {
	
private int[] arr=new int[10];	
private int lastIdxSt1=-1;
private int lastIdxSt2=arr.length;
	
public int getSt1() {
	if (lastIdxSt1 != -1) {
		return arr[lastIdxSt1];
	}
	return Integer.MIN_VALUE;
}

public int getSt2() {
	if (lastIdxSt2 != arr.length) {
		return arr[lastIdxSt2];
	}
	return Integer.MIN_VALUE;
}

public boolean addSt1(int data){
	if ((lastIdxSt1 == arr.length-1)||(lastIdxSt1 == lastIdxSt2-1)) {return false;}
	lastIdxSt1++;
	arr[lastIdxSt1]=data;
	return true;
}

public boolean addSt2(int data){
	if ((lastIdxSt2 == -1)||(lastIdxSt2 == lastIdxSt1+1)) {return false;}
	lastIdxSt2--;
	arr[lastIdxSt2]=data;
	return true;
}

public int removeSt1() {
	if (lastIdxSt1 == -1) {return Integer.MIN_VALUE;}
	int removedData=arr[lastIdxSt1];
	arr[lastIdxSt1]=0;
	lastIdxSt1--;
	return removedData;
}

public int removeSt2() {
	if (lastIdxSt2 == arr.length) {return Integer.MIN_VALUE;}
	int removedData=arr[lastIdxSt2];
	arr[lastIdxSt2]=0;
	lastIdxSt2++;
	return removedData;
}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us