Being Code Expert: Stack

Showing posts with label Stack. Show all posts

Validate Stack Sequences

Given two integer arrays pushed and popped each with distinct values, return true if this could have been the result of a sequence of push and pop operations on an initially empty stack, or false otherwise.

Example 1:

Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
Output: true
Explanation: We might do the following sequence:
push(1), push(2), push(3), push(4),
pop() -> 4,
push(5),
pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

Example 2:

Input: pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
Output: false
Explanation: 1 cannot be popped before 2.

Approach

Java


import java.util.Stack;

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

        int pushed[] = { 1, 2, 3, 4, 5 }, popped[] = { 4, 5, 3, 2, 1 };

        System.out.println(validateStackSequences(pushed, popped));
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {

        Stack<Integer> st = new Stack<Integer>();

        int j = 0;

        // iterate through the whole array
        for (int i = 0; i < pushed.length; i++) {

            // insert the current element into stack
            st.push(pushed[i]);

            // iterate till the size of stack is greater than 0 and
            // current element is the stack top element
            while (st.size() > 0) {
                if (popped[j] == st.peek()) {
                    st.pop();
                    j++;
                } else
                    break;
            }

        }

        // iterate through the remaining elements of the popped
        // array
        for (int i = j; i < popped.length; i++) {

            // if at any point top element is not
            // equal to the current element then
            // return false
            if (st.peek() != popped[i]) {
                return false;
            }
        }

        // at the end return true
        return true;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
                int j=0;
        // iterate through the whole array
        for (int i = 0; i < pushed.size(); i++) {

            // insert the current element into stack
            st.push(pushed[i]);

            // iterate till the size of stack is greater than 0 and
            // current element is the stack top element
            while (st.size() > 0) {
                if (popped[j] == st.top()) {
                    st.pop();
                    j++;
                } else
                    break;
            }

        }

        // iterate through the remaining elements of the popped
        // array
        for (int i = j; i < popped.size(); i++) {

            // if at any point top element is not
            // equal to the current element then
            // return false
            if (st.top() != popped[i]) {
                return false;
            }
        }

        // at the end return true
        return true;
    }
int main()
{
    vector<int> pushed = { 1, 2, 3, 4, 5 }, 
             popped = { 4, 5, 3, 2, 1 };
    cout << validateStackSequences(pushed,popped);
    return 0;
}

Stack class methods in Java

java.util.Stack

The Stack class represents a last-in-first-out(LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack.

Some methods of Stack class

empty(): This method tests if this stack is empty.

peek(): This method looks at the object at the top of this stack without removing it from the stack.

pop(): This method removes the object at the top of this stack and returns that object as the value of this function.

push(K): This method pushes an item onto the top of this stack.

search(Object): This method returns the 1-based position where an object is on this stack.

Stack search(Object) in Java

search(Object): This method is available in java.util.Stack class of Java.

Syntax:

int java.util.Stack.search(Object o)

This method takes one argument. This method returns the 1-based position where an object is on this stack.

Note: If the object o occurs as an item in this stack, this method returns the distance from the top of the stack of the occurrence nearest the top of the stack.

Parameters: One parameter is required for this method.

o: the desired object.

Returns: the 1-based position from the top of the stack where the object is located; the return value -1indicates that the object is not on the stack.

Exceptions: NA

Approach

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        st.push(1);
        st.push(18);
        st.push(29);
        st.push(8);

        System.out.println(st.search(1));

    }
}

Output:

Stack push(K) in Java

push(K): This method is available in java.util.Stack class of Java.

Syntax:

K java.util.Stack.push(K item)

This method takes one argument. This method pushes an item onto the top of this stack.

Parameters: One parameter is required for this method.

item: the item to be pushed onto this stack.

Returns: the item argument.

Exceptions: NA

Approach

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        st.push(1);
        st.push(18);
        st.push(29);
        st.push(8);

        System.out.println(st);

    }
}

Output:

[1, 18, 29, 8]

Stack pop() in Java

pop(): This method is available in java.util.Stack class of Java.

Syntax:

K java.util.Stack.pop()

This method removes the object at the top of this stack and returns that object as the value of this function.

Parameters: NA

Returns: The object at the top of this stack.

Throws:

EmptyStackException - if this stack is empty.

Approach 1: When no exception

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        st.push(1);
        st.push(18);
        st.push(29);
        st.push(8);

        System.out.println(st.pop());

    }
}

Output:

Approach 2: EmptyStackException

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        System.out.println(st.pop());

    }
}

Output:

Exception in thread "main" java.util.EmptyStackException
	at java.base/java.util.Stack.peek(Stack.java:101)
	at java.base/java.util.Stack.pop(Stack.java:83)

Stack peek() in Java

peek(): This method is available in java.util.Stack class of Java.

Syntax:

K java.util.Stack.peek()

This method looks at the object at the top of this stack without removing it from the stack.

Parameters: NA

Returns: the object at the top of this stack.

Throws:

EmptyStackException - if this stack is empty.

Approach 1: When no exception

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        st.push(1);
        st.push(18);
        st.push(29);
        st.push(8);

        System.out.println(st.peek());

    }
}

Output:

Approach 2: EmptyStackException

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        System.out.println(st.peek());

    }
}

Output:

Exception in thread "main" java.util.EmptyStackException
	at java.base/java.util.Stack.peek(Stack.java:101)

Stack empty() in Java

empty(): This method is available in java.util.Stack class of Java.

Syntax:

boolean java.util.Stack.empty()

This method tests if this stack is empty.

Parameters: NA

Returns: true if and only if this stack contains no items; false otherwise.

Exceptions: NA

Approach

Java

import java.util.Stack;

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

        Stack<Integer> st = new Stack<>();

        st.push(1);
        st.push(18);
        st.push(29);
        st.push(8);
        System.out.println(st.empty());

    }
}

Output:

false

Minimum Number of Swaps to Make the String Balanced

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

It is the empty string, or
It can be written as AB, where both A and B are balanced strings, or
It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

Example 1:

Input: s = "][]["
Output: 1
Explanation: You can make the string balanced by swapping index 0 with index 3.
The resulting string is "[[]]".

Example 2:

Input: s = "]]][[["
Output: 2
Explanation: You can do the following to make the string balanced:
- Swap index 0 with index 4. s = "[]][][".
- Swap index 1 with index 5. s = "[[][]]".
The resulting string is "[[][]]".

Example 3:

Input: s = "[]"
Output: 0
Explanation: The string is already balanced.

Approach

Java

import java.util.Stack;

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

        String s = "][][";

        System.out.println(minSwaps(s));

    }

    static int minSwaps(String s) {
        Stack<Character> st = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[')
                st.push(s.charAt(i));
            else if (!st.empty())
                st.pop();
        }
        return (st.size() + 1) / 2;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int minSwaps(string s)
{
    stack<char> st;

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '[')
            st.push(s[i]);
        else if (!st.empty())
            st.pop();
    }
    return (st.size() + 1) / 2;
}

int main()
{
    string s = "][][";

    cout << minSwaps(s) << "\n";

    return 0;
}

How to solve reverse polish notation

Given an arithmetic expression in Reverse Polish Notation, write a program to evaluate it.

The expression is given as a list of numbers and operands. For example: [5, 3, '+'] should return 5 + 3 = 8.

For example, [15, 7, 1, 1, '+', '-', '/', 3, '*', 2, 1, 1, '+', '+', '-'] should return 5, since it is equivalent to ((15 / (7 - (1 + 1))) * 3) - (2 + (1 + 1)) = 5.

Example:

Input:  {"15", "7", "1", "1", "+", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"}
Output: 5

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int reversePolishNotation(vector<string> &tokens)
{
    int res = 0;
    stack<int> st;
    int n = tokens.size();
    if (n == 0)
        return res;
    for (int i = 0; i < n; i++)
    {
        if (tokens[i] == "+" || tokens[i] == "-" || 
                    tokens[i] == "*" || 
                  tokens[i] == "/")
        {
            int rem;
            int x = st.top();
            st.pop();
            int y = st.top();
            st.pop();
            if (tokens[i] == "+")
                rem = y + x;
            else if (tokens[i] == "-")
                rem = y - x;
            else if (tokens[i] == "*")
                rem = y * x;
            else if (tokens[i] == "/")
                rem = y / x;
            st.push(rem);
        }
        else
        {
            int x = stoi(tokens[i]);
            st.push(x);
        }
    }
    return st.top();
}
int main()
{
    vector<string> tokens = {"15", "7", "1", "1",
                             "+", "-", "/", "3", "*",
                             "2", "1", "1", "+", "+", "-"};

    cout << reversePolishNotation(tokens) << "\n";

    return 0;
}

Home