Stack in DSA

What is a Stack?

A stack is an abstract data type that adheres to the Last-In-First-Out (LIFO) principle in the context of data structures and algorithms (DSA). It’s a linear data structure with operations like push (adding an element to the top) and pop (removing the topmost element).

Note: A stack can be visualized as a stack of plates where you can only access the topmost plate. The last plate you put on the stack is the first one to be removed.

Standard Stack Operations:

The following are some common operations implemented on the stack:

• push(): When we insert an element in a stack then the operation is known as a push. If the stack is full then the overflow condition occurs.
• pop(): When we delete an element from the stack, the operation is known as a pop. If the stack is empty means that no element exists in the stack, this state is known as an underflow state.
• isEmpty(): It determines whether the stack is empty or not.
• isFull(): It determines whether the stack is full or not.’
• peek(): It returns the element at the given position.
• count(): It returns the total number of elements available in a stack.
• change(): It changes the element at the given position.
• display(): It prints all the elements available in the stack.

Operation	Time Complexity (N- no. o elements in the stack)	Space Complexity
push()	O(1)	O(1)
pop()	O(1)	O(1)
isEmpty()	O(1)	O(1)
isFull()	O(1)	O(1)
peek()	O(1)	O(1)
count()	O(1)	O(1)
change()	O(1)	O(1)
display()	O(N)	O(N)

Application of Stack:

Stacks are commonly used in various algorithms and programming tasks due to their simple and efficient structure. Some applications of stacks include:

1. Expression evaluation: Stacks can be used to evaluate arithmetic expressions, such as infix, postfix, or prefix notations.
2. Function call management: Stacks are used to manage function calls and recursion in programming languages.
3. Undo operations: Stacks can be used to implement undo functionality in applications.
4. Backtracking: Stacks are useful for backtracking algorithms, such as depth-first search (DFS).
5. Browser history: Stacks can be used to maintain the history of visited web pages in a browser.

Implementation of stack in DSA:

A stack can be implemented in two ways:

• Array implementation
• Linked list implementation

Array Implementation:

1. push(int element): This function adds an element to the top of the stack. It has a time complexity of O(1) since adding an element to an array at a specific index takes constant time.
2. pop(): This function removes and returns the topmost element from the stack. It also has a time complexity of O(1) since accessing and removing an element from a specific index in an array takes constant time.
3. isEmpty(): This function checks if the stack is empty. It has a time complexity of O(1) since it only requires checking the value of the top variable, which is constant time.
4. isFull(): This function checks if the stack is full. It has a time complexity of O(1) since it only requires comparing the top variable with the capacity, which is constant time.
5. peek(): This function returns the topmost element of the stack without removing it. It has a time complexity of O(1) as it directly accesses the element at the top index of the array.
6. size(): This function returns the number of elements in the stack. It has a time complexity of O(1) as it simply returns the value of the top variable, which represents the number of elements in the stack.
7. display(): This function displays all the elements in the stack. It has a time complexity of O(N) where N is the number of elements in the stack since it requires iterating over each element in the array and printing it.
8. The space complexity for all the functions is O(1) as they use a fixed amount of additional space regardless of the input size.

public class Stack {
    private int capacity;
    private int top;
    private int[] stackArray;

    public Stack(int capacity) {
        this.capacity = capacity;
        this.top = -1;
        this.stackArray = new int[capacity];
    }

    public void push(int element) {
        if (top < capacity - 1) {
            stackArray[++top] = element;
        } else {
            System.out.println("Stack Overflow");
        }
    }

    public int pop() {
        if (top >= 0) {
            return stackArray[top--];
        } else {
            System.out.println("Stack Underflow");
            return -1; // Or throw an exception
        }
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == capacity - 1);
    }

    public int peek() {
        if (top >= 0) {
            return stackArray[top];
        } else {
            System.out.println("Stack is empty");
            return -1; // Or throw an exception
        }
    }

    public int size() {
        return top + 1;
    }

    public void display() {
        System.out.print("Stack: ");
        for (int i = 0; i <= top; i++) {
            System.out.print(stackArray[i] + " ");
        }
        System.out.println();
    }
}

Linked List Implementation:

• push(int element): This function adds an element to the top of the stack by creating a new node and updating the top reference. It has a time complexity of O(1) since it involves creating a new node and updating a reference.
• pop(): This function removes and returns the topmost element from the stack by updating the top reference. It also has a time complexity of O(1) as it only involves updating a reference.
• isEmpty(): This function checks if the stack is empty. It has a time complexity of O(1) as it only requires checking the value of the top reference, which is constant time.
• peek(): This function returns the topmost element of the stack without removing it. It has a time complexity of O(1) as it directly accesses the element referenced by the top reference.
• display(): This function displays all the elements in the stack by iterating over the linked list. It has a time complexity of O(N) where N is the number of elements in the stack since it requires visiting each node in the linked list.
• The space complexity for all the functions is O(1) as they use a fixed amount of additional space regardless of the input size.

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class Stack {
    private Node top;

    public Stack() {
        this.top = null;
    }

    public void push(int element) {
        Node newNode = new Node(element);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (top != null) {
            int poppedValue = top.data;
            top = top.next;
            return poppedValue;
        } else {
            System.out.println("Stack Underflow");
            return -1; // Or throw an exception
        }
    }

    public boolean isEmpty() {
        return (top == null);
    }

    public int peek() {
        if (top != null) {
            return top.data;
        } else {
            System.out.println("Stack is empty");
            return -1; // Or throw an exception
        }
    }

    public void display() {
        System.out.print("Stack: ");
        Node current = top;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

Array vs Linked list implementation of stack:

	Array Implementation	Linked List Implementation
Memory Allocation	Requires a fixed-size array	Dynamic allocation of nodes
Insertion (Push)	Direct access at top index (O(1))	Creation of new node and reference update (O(1))
Deletion (Pop)	Direct access at top index (O(1))	Reference update and node deallocation (O(1))
Memory Efficiency	More memory efficient (no overhead)	Slightly less memory efficient (overhead of nodes and references)
Resizing	Resizing the array can be expensive	No resizing required
Advantages	– Constant-time access and updates – More memory efficient	– Dynamic size handling
Disadvantages	– Limited capacity – Costly resizing if capacity is exceeded	– No predefined maximum capacity – Slightly less memory efficient

Problems based on Stack:

You are given N elements and your task is to Implement a Stack in which you can get a minimum element in O(1) time.

Example:

Input:
push(2)
push(3)
pop()
getMin()
push(1)
getMin()
Output: 2 1
Explanation: In the first test case for
query 
push(2)  Insert 2 into the stack.
         The stack will be {2}
push(3)  Insert 3 into the stack.
         The stack will be {2 3}
pop()    Remove top element from stack 
         Poped element will be 3 the
         stack will be {2}
getMin() Return the minimum element
         min element will be 2 
push(1)  Insert 1 into the stack.
         The stack will be {2 1}
getMin() Return the minimum element
         min element will be 1

Your Task:
You are required to complete the three methods push() which takes one argument an integer ‘x’ to be pushed into the stack, pop() which returns an integer popped out from the stack, and getMin() which returns the min element from the stack. (-1 will be returned if for pop() and getMin() the stack is empty.)

Expected Time Complexity: O(1) for all the 3 methods.
Expected Auxiliary Space: O(1) for all the 3 methods.

Solution:

import java.util.Stack;

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public int pop() {
        if (stack.isEmpty()) {
            return -1;
        }
        int popped = stack.pop();
        if (popped == minStack.peek()) {
            minStack.pop();
        }
        return popped;
    }

    public int getMin() {
        if (minStack.isEmpty()) {
            return -1;
        }
        return minStack.peek();
    }
}

Explanation:

• The MinStack class has two stacks:
  • stack to store the actual elements
  • minStack to store the minimum values.
• When pushing an element, we first push it onto the stack. Then, if the minStack is empty or the new element is less than or equal to the top element of minStack, we push the new element onto minStack as well.
• When popping an element, we first check if the stack is empty. If it is, we return -1 indicating an empty stack. Otherwise, we pop the element from the stack and check if it is the same as the top element of minStack. If it is, we also pop the top element from minStack.
• When getting the minimum element, we simply return the top element of minStack. If minStack is empty, we return -1 indicating an empty stack.

Given an expression string x. Examine whether the pairs and the orders of {,},(,),[,] are correct in exp.
For example, the function should return ‘true’ for exp = [()]{}{[()()]()} and ‘false’ for exp = [(]).

Note: The drive code prints “balanced” if function return true, otherwise it prints “not balanced”.

Example:

Input:
{([])}
Output: 
true
Explanation: 
{ ( [ ] ) }. Same colored brackets can form 
balanced pairs, with 0 number of 
unbalanced bracket.

Expected Time Complexity: O(|x|)
Expected Auixilliary Space: O(|x|)

Solution:

 Stack<Character> stack = new Stack<>();

        for (char c : exp.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
                    return false;
                }
            }
        }

        return stack.isEmpty();

Explanation:

• The ispar function takes a string exp as input and returns a boolean value indicating whether the brackets are balanced or not.
• We iterate through each character in the input string using a for-each loop.
• If we encounter an opening bracket ((, [, or {), we push it onto the stack.
• If we encounter a closing bracket (), ], or }), we check if the stack is empty. If it is, there is no corresponding opening bracket, so the brackets are not balanced, and we return false.
• If the stack is not empty, we pop the top element from the stack and compare it with the current closing bracket. If they do not form a matching pair (e.g., ( ), [ ], { }), we return false.
• If the stack is empty after iterating through all the letters, it signifies that all the brackets have been matched and balanced, and we return true. If there are still unmatched opening brackets in the stack, we return false.

Given a binary tree, find its preorder traversal.

Example 1:

Input:
        1      
      /          
    4    
  /    \   
4       2
Output: 1 4 4 2 

Example 2:

Input:
       6
     /   \
    3     2
     \   / 
      1 2
Output: 6 3 1 2 2 

Your Task:
You just have to complete the function preorder() which takes the root node of the tree as input and returns an array containing the preorder traversal of the tree.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).

Solution:

// class Node{
//     int data;
//     Node left,right;
//     Node(int d){
//         data=d;
//         left=right=null;
//     }
// }

class BinaryTree
{
    //Function to return a list containing the preorder traversal of the tree.
    static ArrayList<Integer> preorder(Node root)
    { ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        
        Stack<Node> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node node = stack.pop();
            result.add(node.data);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return result;
    
        // Code here
    }

}

Explanation:

• The BinaryTree class represents a binary tree.
• The preorder function takes the root node of the binary tree as input and returns an ArrayList<Integer> containing the preorder traversal of the tree.
• We start by creating an empty ArrayList<Integer> called result to store the preorder traversal elements.
• If the root node is null, we simply return the empty result list.
• We use a stack to keep track of the nodes during the traversal. We initialize the stack with the root node.
• While the stack is not empty, we perform the following steps:
  • Pop a node from the stack and add its data value to the result list.
  • Push the right child of the node onto the stack (if it exists) before the left child (to ensure preorder traversal).
• After traversing all the nodes, we return the result list containing the preorder traversal elements.

Given a stack, the task is to sort it such that the top of the stack has the greatest element.

Example:

Input:
Stack: 11 2 32 3 41
Output: 41 32 11 3 2

Your Task: 
You don’t have to read input or print anything. Your task is to complete the function sort() which sorts the elements present in the given stack. (The sorted stack is printed by the driver’s code by popping the elements of the stack.)

Expected Time Complexity: O(N*N)
Expected Auxilliary Space: O(N) recursive.

Solution:

import java.util.Stack;

class SortStack {
    public static void sort(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        
        int temp = stack.pop();
        sort(stack);
        insertSorted(stack, temp);
    }
    
    private static void insertSorted(Stack<Integer> stack, int element) {
        if (stack.isEmpty() || element > stack.peek()) {
            stack.push(element);
        } else {
            int temp = stack.pop();
            insertSorted(stack, element);
            stack.push(temp);
        }
    }
}

Explanation:

• The sort function takes a stack of integers as input and sorts its elements in descending order.
• If the stack is empty, we simply return as there are no elements to sort.
• We recursively sort the stack by performing the following steps:
  • Pop an element from the stack and store it in the variable temp.
  • Recursively sort the remaining elements of the stack.
  • Insert the temp element back into the stack in the correct position using the insertSorted helper function.
• The insertSorted function is a recursive helper function that inserts an element into the stack at the correct position.
• If the stack is empty or the element is greater than the top element of the stack, we push the element onto the stack.
• Otherwise, we recursively call insertSorted with the remaining stack elements until we find the correct position to insert the element.
• The time complexity of this approach is O(N^2), where N is the number of elements in the stack. This is because, in the worst case, each element needs to be inserted at its correct position by comparing it with the elements already in the stack.
• The auxiliary space complexity is O(N) as the recursive calls consume space on the function call stack.

Note: also read about Pointers in DSA

Follow Me

If you like my post please follow me to read my latest post on programming and technology.

https://www.instagram.com/coderz.py/

https://www.facebook.com/coderz.py