Stack Data Structure
In this article, I am going to discuss the major aspects of the Stack data structure. Having the fundamental operations, use cases, time and space complexities, implementations and common problems all in one place can help the reader use this material to quickly brush up everything needed to efficiently use this data structure before diving into problem solving.
This article is part my data structures series. More topics to read:
So what is Stack?
Stack is a linear data structure which follows the LIFO (Last In First Out) order of operations. The insertion and deletion operations need to be at constant O(1) time.
The major operations of stack:
- Push: Inserts an item on top of the stack
- Pop: Removes an item from the top of the stack
- Peek: Views the item from the top without removing it
- isEmpty: Checks if the stack is empty (self explanatory)
Applications of Stack
Below are some of the use cases of stack, in addition to many more out there.
- Infix/Postfix/Prefix notation conversions and expression evaluations. We’ll discuss more on these a bit later.
- Balancing symbols and parenthesis matching
- In implementations of features like redo/undo
- In memory management of modern systems
- Different kinds of reversals
- In backtracking algorithm design techniques
Implementation with Array
I have chosen to implement a integer stack for its simplicity to the reader. A generic stack implementation would be similar to this one with some tweaks. If you’re interested in that, have a look here — https://www.geeksforgeeks.org/how-to-implement-stack-in-java-using-array-and-generics/
public class Stack{
private int top;
private static int max;
private static int [] a;
public Stack(int max){
this.top = -1;
this.max = max;
this.a = new int[max];
}
public boolean isEmpty(){
if(top<0){
return true;
}else{
return false;
}
}
public boolean push(int element){
if(top>=max-1){
System.out.println("Stack overflow");
return false;
}else{
a[++top] = element; //as we initialized top from -1
return true;
}
}
public int pop(){
if(isEmpty()){
System.out.println("Stack underflow");
return -1;
}else{
return a[top--];
}
}
public int peek(){
if(isEmpty()){
System.out.println("Nothing in the stack");
return -1;
}else{
return a[top];
}
}
}Implementation with Linked List
We first create our node class!
public class Node{
private int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}public class Stack{
private Node top; public Stack(){
top= null;
}
public boolean isEmpty(){
if(top==null){
return true;
}else{
return false;
}
}
// Important to note that, in order to keep the LIFO structure, we need to perform push() and pop() from the head of the linked list to ensure O(1) complexity. So, we update the head in each operation. public void push(int element){
Node newNode = new Node(element);
if(isEmpty()){
top = newNode; //making the only node as top(head)
}else{
Node temp = top;
newNode.next = temp; //LIFO
top = newNode; //update the top(head)
}
}
public int pop(){
if(isEmpty()){
System.out.println("Stack Underflow");
return -1;
}else{
Node temp = top;
top = temp.next; //make the next item as top
return temp.data;
}
}
public int peek(){
if(isEmpty()){
return -1;
}else{
return top.data;
}
}
}
Now that we have hopefully understood the internal mechanism of stack and its operations, let us apply this knowledge to approach a common stack problem of Parenthesis Checking!
Parenthesis Checking using Stack
We will use Java’s Stack class which is provided by its Collection Framework. We define the type of data we want to store in the stack using its wrapper class. If you want to know more about the Java stack class, feel free to visit https://www.geeksforgeeks.org/stack-class-in-java/
void checkParenthesis(String expression){
Stack<Character> stack = new Stack<>();
for(int i=0;i<expression.length();i++){
char c = expression.charAt(i);
if(c =='(' || c=='{' || c=='['){
stack.push(c); //we push any opening parentheses
}
else{
if(stack.isEmpty()){
break;
}
else{
if(c==')' && (stack.peek()=='{'
|| stack.peek()=='[') ){
break;
}
else if(c=='}' && (stack.peek()=='('
|| stack.peek()=='[')){
break;
}
else if(c==']' && (stack.peek()=='{'
|| stack.peek()=='(')){
break;
}
else{
stack.pop();
}
}
}
}
if(stack.isEmpty()){
System.out.println("Balanced");
}else{
System.out.println("Not balanced");
}
}The time and space complexity of the above solution is O(n) where n is the length of the expression to be checked.
Infix, Postfix and Prefix Notations
Arithmetic expressions can be written in three different but equivalent ways, without changing the output.
- Infix: Operators are written in between operands. Its easier for us humans to read, write and speak in infix notations but when it comes to machines, processing this notation could be costly in terms of space and time complexity. a+b*c is an infix example.
- Prefix: Operators are written ahead of operands. This notation is also called polish notation. +a*bc is an example prefix notation.
- Postfix: Operators are written after the operands, also known as reverse polish notation. abc*+ is a postfix example.
While I have summarized the concepts here to generate a sense of what we are about to do, you can always dive deeper into these notations. Feel free to visit http://www.cs.man.ac.uk/~pjj/cs212/fix.html
Now, with the help of stack, we will do the conversions of these notations and write some expression evaluation functions. These problems helped me solidify learning the applications of stack, in addition to some cs fundamentals. I highly recommend solving and understanding these problems.
Evaluating a Postfix Expression
void postFixEvaluation(String exp){
Stack<Integer> stack = new Stack<>();
for(int i=0;i<exp.length();i++){
char c = exp.charAt(i);
if(Character.isDigit(c)){
stack.push(c-'0');
}
else{
int value1 = stack.pop();
int value2 = stack.pop();
switch(c){
case '+':
stack.push(value2+value1);
break;
case '-':
stack.push(value2-value1);
break;
case '*':
stack.push(value2*value1);
break;
case '/':
stack.push(value2/value1);
break;
}
}
}
System.out.println("postfix result : "+stack.pop());
}Note that in the above algorithm, the second operand (value2) comes first during any operation. To explain this, lets take a simple postfix expression 86-. The answer of this expression would be 8–6=2. We push the (8) first, then the (6). When we find the ‘-’ operator, we pop the first two values from the stack. Observe that when popping, the top of the stack (6) is popped and then (8) is popped. If we then calculate 6–8=-2, we get the wrong evaluation. So to adjust that, in postfix evaluation using above algorithm, we place the operand popped second(value2) as our primary operand.
Evaluating a Prefix Expression
void preFixEvaluation(String exp){
Stack<Integer> stack = new Stack<>();
for(int i=exp.length()-1;i>=0;i--){
char c = exp.charAt(i);
if(Character.isDigit(c)){
stack.push(c-'0');
}
else{
int value1 = stack.pop();
int value2 = stack.pop();
switch(c){
case '+':
stack.push(value1+value2);
break;
case '-':
stack.push(value1-value2);
break;
case '*':
stack.push(value1*value2);
break;
case '/':
stack.push(value1/value2);
break;
}
}
}
System.out.println("prefix result : "+stack.pop());
}Lets take the same example from above. 86- in prefix form would yield -86. As we traverse from right to left, (6) is pushed in the stack first, then (8). When we find ‘-’, we pop the top of the stack(8) first, then we pop (6). So naturally, the primary operand is popped first. Result would be then, 8–6=2.
The time and space complexity of both the above evaluating algorithms would be O(n) where n is the length of the expression.
Infix to Postfix Conversion
To understand how the algorithm works, please refer to these steps.
- If the character is an operand, append it to the final result.
- If the character is ‘(‘ , push to stack.
- If the character is an operator with higher precedence than stack top, push it to stack.
- If the character is an operator with lower or equal precedence compared to stack top, pop the stack and append to final result , then recheck.
- If the character is ‘)’ , then keep popping and appending to final result until ‘(‘ is found and get rid of the brackets.
- Finally, pop the remaining items and append to find result.
void infixToPostFix(String exp){
Stack<Character> stack = new Stack<>();
String result = "";
for(int i = 0;i<exp.length();i++){
char c = exp.charAt(i);
if(Character.isLetterOrDigit(c)){
result += c;
}
else if(c=='('){
stack.push(c);
}
else if(c==')'){
while(!stack.isEmpty() && stack.peek()!='('){
result += stack.pop();
}
stack.pop();
}
else{
while(!stack.isEmpty() &&
prec(c) <= prec(stack.peek())){
result += stack.pop();
}
stack.push(c);
}
}
while(!stack.isEmpty()){
if(stack.peek()=='('){
System.out.println("Invalid expression");
return;
}
result += stack.pop();
}
System.out.println("Postfix : "+result);
}int prec(char c){
switch(c){
case '+':
return 1;
case '-':
return 1;
case '*':
return 2;
case '/':
return 2;
case '^':
return 3;
}
return -1;
}The prec method helps to identify precedence levels of the operators. Precedence and associativity are key concepts when it comes to these conversions, feel free to dive deeper into these in your free time. For the scope of this context, I will provide a short list to remember.
Precedence from top to bottom :
()
^ -> associativity from right to left
/* -> associativity from left to right
+- -> associativity from left to rightInfix to Prefix Conversion
- Reverse the expression to be converted.
- If the character is an operand, append it to the final result.
- If the character is ‘)‘ , push to stack.
- If the character is an operator with higher or equal precedence compared to stack top, push it to stack.
- If the character is an operator with lower precedence compared to stack top, pop the stack and append to final result , then recheck.
- If the character is ‘(’ , then keep popping and appending to final result until ‘)‘ is found and get rid of the brackets.
- Finally, pop the remaining items and append to find result.
void infixToPreFix(String exp){
Stack<Character> stack = new Stack<>();
String result = "";
StringBuilder input = new StringBuilder(exp);
input.reverse();
for(int i=0;i<input.length();i++){
char c = input.charAt(i);
if(Character.isLetterOrDigit(c)){
result += c;
}
else if(c==')'){
stack.push(c);
}
else if(c=='('){
while(!stack.isEmpty() && stack.peek()!=')'){
result += stack.pop();
}
stack.pop();
}
else{
while(!stack.isEmpty() &&
prec(c) < prec(stack.peek())){
result += stack.pop();
}
stack.push(c);
}
}
while(!stack.isEmpty()){
if(stack.peek()==')'){
System.out.println("Invalid Expression");
return;
}
result += stack.pop();
}
StringBuilder res = new StringBuilder(result);
System.out.println("Prefix : "+res.reverse());
}Postfix to Infix Conversion
- If character is an operand, push to stack.
- If character is an operator, pop the first two values from stack, append them in the form <value2><operator><value1> and push back to stack.
- Finally the result will be the only value in stack.
void postFixToInfix(String exp){
Stack<String> stack = new Stack<>();
for(int i=0;i<exp.length();i++){
char c = exp.charAt(i);
if(c=='+' || c=='-'|| c=='*'|| c=='/' || c=='^'){
String value1 = stack.pop();
String value2 = stack.pop();
stack.push("("+value2+c+value1+")");
}
else{
stack.push(c+""); //to store as string type
}
}
System.out.println(stack.peek());
}Note here that we are again adjusting the order of popped values from the stack to get the correct result. ab- will convert to (a-b) and not (b-a).
Prefix to Infix Conversion
- Traverse the expression from right to left. If read character is an operand, push to stack.
- If the character is an operator, pop the first two values from stack and append in the form <operator><value1><value2> and push back to stack.
- Finally only the result will remain in the stack.
void preFixToInfix(String exp){
Stack<String> stack = new Stack<>();
for(int i=exp.length()-1;i>=0;i--){
char c = exp.charAt(i);
if(c=='+' || c=='-'|| c=='*'|| c=='/' || c=='^'){
String value1 = stack.pop();
String value2 = stack.pop();
stack.push("("+value1+c+value2+")");
}else{
stack.push(c+""); //to store as string type
}
}
System.out.println(stack.peek());
}As the primary operand is popped first naturally, we don’t need to adjust anything here.
Postfix to Prefix Conversion
- If the character is an operand, push to stack.
- If character is an operand, pop the first two values from stack and append in the form <operator><value2><value1> and push back to stack.
- Finally only the result will remain in the stack.
void postFixToPreFix(String exp){
Stack<String> stack = new Stack<>();
for(int i=0;i<exp.length();i++){
char c = exp.charAt(i);
if(Character.isLetterOrDigit(c)){
stack.push(c+""); //to store as string type
}else{
String value1 = stack.pop();
String value2 = stack.pop();
stack.push(c+value2+value1);
}
}
System.out.println(stack.peek());
}Note that we needed to adjust the order of the popped operands to get the correct conversion. ab- will convert to -ab and not -ba.
Prefix to Postfix Conversion
- Traverse from right to left. If read character is an operand, push to stack.
- If character is operator, pop the first two values from stack and append in the form <value1><value2><operator> and push back to stack.
- Finally only the result will remain in the stack.
void preFixToPostFix(String exp){
Stack<String> stack = new Stack<>();
for(int i=exp.length()-1;i>=0;i--){
char c = exp.charAt(i);
if(Character.isLetterOrDigit(c)){
stack.push(c+""); //to store as string type
}else{
String value1 = stack.pop();
String value2 = stack.pop();
stack.push(value1+value2+c);
}
}
System.out.println(stack.peek());
}The six conversion algorithms above all have a time and space complexity of O(n) where n is the size of the expression to be converted.
Conclusion
So there we go. I hope this article will help the reader get up and running with stack as a data structure. I would like to point out some things though:
->While these problems can introduce you to stack, true mastery on the topic can only come by solving more and more problems. Knowing when to efficiently use a data structure and to what capacity is the real achievement, be it for a job interview or in real projects.
->Almost every code is subject to optimization. The code provided above can most definitely be improved, but the underlying concept will remain.
->Some of the code here has been written based on some assumptions. For example, in the conversion algorithms, it has been assumed that the provided input expression will be valid.
Thanks for reading.
