Hi Guys, a warm welcome to tech-maze, todays article is quite light but yet powerful to give an insight, how and in which scenario stack data structure can be used efficiently to solve the problem, to back this statement, lets have a look into following two programs which are also asked during the interviews to check the knowledge of data structure.
Program 1 :---------------------------
System A sends a number to System B in sequence but when number is not in sequence, System B doesn't accept it and respond as not in sequence.
solution :
This question can be solved by using for/while loop or keep track of last sent number so whenever a new number comes then compare that, but in this way we have to rely on global variable and that variable may decide at some point of time to cache its value (this happens when more request comes for computation), to overcome from this issue we declare this global variable as volatile and it works as expected, but it comes with a burden to manage and barred to cache its value, it also increases the complexity of the program. There is more to it, going in above route which not only decrease the performance, it also become tedious to manage multiple variables and its state
We can think of any data structure which can provide this type of functionality and take care of managing the complexity internally, and in this case Stack is one of the best choice, Stack not only provide Last In Fist Out approach, it also hides the complexity of storing and managing the items.
Now lets see how Stack can be used to resolve this problem.
public String checkTheSequence(int item) {
if(item<0)
return null;
if(stk.isEmpty()) {
stk.push(item);
return "number "+item+" successfully added ";
}
int val = stk.peek();
if(item == (val+1)) {
stk.push(item);
}else {
return "number "+item+ " not in sequence";
}
return "number "+item+" successfully added ";
}
Logic follows as below :-
Step 1- null check to avoid null pointer exception
Step 2 - if control pass step 1 then check the stack size, if its empty that means the item which has come to this method is the first item, hence add this item to stack and return.
Step 3 - pick last item from stack and increment by 1 and then compare with the incoming number,
if both are same, that means the number which method checkTheSequence received is in sequence with the last item in the stack, hence add that item to the stack and return success.
if both are not same, that means, the number which method checkTheSequence has received is not in sequence with the last item in the stack, hence return "number not in sequence".
Program 2 :---------------------------------
Compute the result from a given Polish Notation which is in String, for example the result for the polish notation "234+*" should be 14
solution :
Solution for this problem can also be determined by using multiple loops with multiple arrays, but we have to go through many data conversion logic which eventually makes the code unreadable and hard to understand.
Here too we can use Stack and avoid having multiple conversion to/from Array and multiple loops.
Lets see how stack can be used for this problem
public static int findResultFromGivenExppression(String polishnotation) {
String notation = "+-*/";
Stack<String> stk = new Stack<>();
if(polishnotation.isEmpty()) {
return 0;
}
for (int i = 0; i < polishnotation.length(); i++) {
String cstr = String.valueOf(polishnotation.charAt(i));
if(!notation.contains(cstr)) {
stk.push(cstr);
}else {
int val1 = Integer.parseInt(stk.pop());
int val2 = Integer.parseInt(stk.pop());
switch(cstr) {
case "+" :
stk.push(String.valueOf(val1+val2));
break;
case "-" :
stk.push(String.valueOf(val1-val2));
break;
case "*" :
stk.push(String.valueOf(val1*val2));
break;
case "/" :
stk.push(String.valueOf(val2/val1));
break;
default :
System.out.println("invalid operator:::");
break;
}
}
}
return Integer.parseInt(stk.pop());
}
Logic follows as below :-
Step 1- null check to avoid null pointer exception
Step 2 - if control pass step 1 then we can start iterating through the given polishNotation and then put all the numbers in the stack one by one hence the last number in the polishNotation will be the first to pick from the stack, this makes our task very easy, which we can see in further steps.
Step 3 - When all numbers get added to Stack, we receive the first mathematical notation, which is nearest to those items which are saved in stack at the top, now we have to pop first two numbers from the stack and compute the result and then push the computed result in the stack for the next computation.
To achieve this we have used Switch statement, so that based on mathematical notation we can choose the operation to be performed.
This process will continue until all the computation is done.
After finishing all the computation, we will end up having one number which is the result in the stack, hence pop that number and return.
Note : In java 8 or higher version, we can use String in the Switch statement, but if someone using java version older than 8 then please check following logic, everything will be same except the Switch statement, instead of using String , we have to use integer as lower version of Java doesn't support String in Switch statement.
public static int findResultFromGivenExppressionLowerVersionThanJAVA8
(String polishnotation) {
String notation = "+-*/";
Stack<String> stk = new Stack<>();
if(polishnotation.isEmpty()) {
return 0;
}
for (int i = 0; i < polishnotation.length(); i++) {
String cstr = String.valueOf(polishnotation.charAt(i));
if(!notation.contains(cstr)) {
stk.push(cstr);
}else {
int val1 = Integer.parseInt(stk.pop());
int val2 = Integer.parseInt(stk.pop());
int indx = notation.indexOf(cstr);
switch(indx) {
case 0 :
stk.push(String.valueOf(val1+val2));
break;
case 1 :
stk.push(String.valueOf(val1-val2));
break;
case 2 :
stk.push(String.valueOf(val1*val2));
break;
case 3 :
stk.push(String.valueOf(val2/val1));
break;
default :
System.out.println("invalid operator:::");
break;
}
}
}
return Integer.parseInt(stk.pop());
}
That's all folks in this article, please let me know if there are better solutions for these problems in comment section, feel free to share this article and your suggestion/thoughts.
hope this will help at some extent to understand the significance and how powerful Stack can be when it comes to mathematical calculation and arranging the numbers in particular sequence.
for more details and complete code please have a look in the below GitHub project
Git location for the demo : https://github.com/rohitmodi07/Programs
A Big thank you for checking out my article, this really encourage me to come up with more topics.
Comments