Stack in Java

A Stack is a data structure known in many programming languages. It is based on last in first out (LIFO) principle. In a stack, the element that is inserted last or most recent will be accessed first.

The stack can be imagined as a Stack of plates placed on top of one another. The plate that is placed last in the stack will always be on the top of the stack and will be picked up first. Elements in a stack can be inserted or accessed only from one end called as top of the stack. Any new element in a stack can be added only to the top of the stack. If an element has to be removed from the stack it gets removed from the top.

Functions available in Stack :

1. push(element) – to add an element to the top of a stack
2. pop() – to remove an element from top of a stack
3. peek() – to see the top element in the stack
4. isEmpty() to check if the stack is empty

Create and add elements to a stack

 
import java.util.Stack;

public class StackMain {
	
	public static void main(String[] args) {

		// Create Stack
		Stack<String> stack =new Stack<>();
		
		// Push elements to stack
		stack.push("A");
		stack.push("B");
		stack.push("C");
		stack.push("D");
		
		// Print elements in a stack
		System.out.println("stack : " + stack);

    }
} 
  

OUTPUT

Stack : [A,B,C,D]
    

Check the top element in a stack

 
// check the top most element in a stack
String top = stack.peek();
System.out.println("stack.peek() : " + top);
        

OUTPUT

stack.peek() : D
    

Remove elements from a stack

 
// Pop out elements in a stack
String firstFromTop = stack.pop();
System.out.println("stack.pop() : " + firstFromTop);
System.out.println("stack after stack.pop() : " + stack);
System.out.println();


String secondFromTop = stack.pop();
System.out.println("stack.pop() : " + secondFromTop);
System.out.println("stack after stack.pop() : " + stack);

OUTPUT

stack.pop() : D
Stack after stack.pop() : [A, B, C]
  
stack.pop() : C
Stack after stack.pop() : [A, B]
  

Iterate over a Stack :

for(String element : stack){
  System.out.println("element : " + element);
}
System.out.println("Stack after iteration : " + stack);

OUTPUT

element : A
element : B
Stack after iteration : [A, B]
  

Uses of Stack

Stack is used in function calls as well as in recursive function calls.

Compilers use stacks to check for balanced parentheses.

Stack interview questions

Balanced Parentheses : check if each opening parentheses has a matching closing parentheses or not

Parentheses or brackets means any of [ , ] ,{ , } , ( , ) . 
The matching pairs of opening and closing brackets are
( and )
[ and ]
{ and }
  

Given a string, each opening bracket should have a matching closing bracket to its right-hand side. Also, any pair of matching brackets can enclose another pair of matching brackets of same or different type.

Examples of balanced parentheses

[ ]
{ [ ] }
{ { { } } }

Examples of imbalanced parantheses

[ )
{ [ } ]
{ { { } } 

Write a function to return YES if the string has balanced Parentheses and return NO if the Parentheses are not balanced.

APPROACH : to the above example

In a balanced Parentheses scenario, the first closing bracket at an index will have a matching opening bracket at index-1. Once the matching pair is found, if u remove this pair the next closing bracket at an index will have an opening matching bracket at index-1 and so on. So, based on this scenario we decided to use Stack as it’s a LIFO based data structure so that when we find a closing bracket we can look back at the last inserted bracket and remove it if it’s a matching bracket.

1. Use stack data structure.
2. Traverse the input string. If any opening bracket is found push it in the stack.
3. If a closing bracket is found, pop from the top of the stack to see the last inserted bracket is matching or not.
4. If step 3 returns a non-matching bracket , return NO. else continue string traversal and keep following steps 2 and 3.
5. After complete traversal of the input string, check if Stack is empty. If yes Return YES else return NO.

Solution

import java.util.Stack;

public class BalancedBrackets {
  
    public static String isBalanced(String s) {
        Stack<Character> stack = new Stack<>();
        char input[] = s.toCharArray();

        for (int i = 0; i < input.length; i++) {
          char bracket = input[i];
          if (bracket == '{' || bracket == '[' || bracket == '(') {
                stack.push(bracket);
          }

          switch (bracket) {
          case '}':
                if (stack.isEmpty() || stack.peek() != '{') {
                      return "NO";
                }
                stack.pop();
                break;
          case ']':
                if (stack.isEmpty() || stack.peek() != '[') {
                      return "NO";
                }
                stack.pop();
                break;
          case ')':
              if (stack.isEmpty() || stack.peek() != '(') {
                      return "NO";
                }
                stack.pop();
                break;
          }
        }
          return (stack.empty()) ? "YES" : "NO";
    }
  
public static void main(String[] args) {

      String s = "{{()}[]}";
      String output = isBalanced(s);
      System.out.println(output);
}
          

Summary

In this article we learnt about the Stack Data Structure using Java. For better understanding we looked into some code snippets of stack push, peek & pop operations
Hope you liked the article !

---