DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Stack and Queue

Valid parenthesis
TC: O(N)

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char ch [] = s.toCharArray();
        for(char i : ch){
            if(stack.size()==0) {

                System.out.println("push happened "+stack.peek());
            else if(stack.peek()=='(' && i==')' || stack.peek()=='{' && 
              i=='}' || stack.peek()=='[' && i ==']') {
            else stack.push(i);
        if(stack.size()==0) return true;
        else return false;
Enter fullscreen mode Exit fullscreen mode

Next greater element than stack top
TC: in worst case O(n^2), as we will iterate over nums2, and if all the elements are in descending order except the last element in nums2 (example: 7,6,5,4,3,8), then at last index we will go to else part and while loop that will run for n-1 times hence TC will be n*(n-1)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        //we will get next greater element of all the element in the nums2,
        // by that we will easily be able to get the next greater element of all the 
        //elements in nums1;
        for(int i = 0;i<nums2.length;i++){
            if(stack.isEmpty() || stack.peek() > nums2[i]){
                // below while condition means that we have found
                // greater value than stack top, now we will have to keep on removing 
                //stack top to make sure that we have got next greater value of stack top
                while(!stack.isEmpty() && nums2[i] > stack.peek()){
        //now we have got the next greater value of all the elements in the nums2
        //we can easily get the next greater value of nums1
        int result[] = new int[nums1.length];
        for(int i =0;i<result.length;i++){
            result[i]= map.getOrDefault(nums1[i],-1);// if next greater does not return then default value will be -1

        return result;
Enter fullscreen mode Exit fullscreen mode

Implement stack using single queue (design quetion)
You can easily guess the TC:

// we can easily do it with two queue,
// we will do it with one queue
class MyStack {
    Queue<Integer> q ;
    public MyStack() {
        q  = new LinkedList<>();

    public void push(int x) {
            int size = q.size();
            int index =0;
            while(index!=size-1){//just re-push size-1 value again it will insure that the value 
                // that needs to be poped is at head;

    public int pop() {
        return q.remove();

    public int top() {
        return q.peek();

    public boolean empty() {
        return q.isEmpty();

 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 =;
 * boolean param_4 = obj.empty();

Enter fullscreen mode Exit fullscreen mode

Sort stack in descending order

TC: o(N)

import java.util.*;
public class Solution {

    public static void sortStack(Stack<Integer> stack) {
        // Write your code here. 
        Stack<Integer> stack2 = new Stack<>();
        while(!stack.isEmpty()) {
            int top = stack.pop();
            while(!stack2.isEmpty() && stack2.peek() < top){
       while(!stack2.isEmpty()) stack.push(stack2.pop());
Enter fullscreen mode Exit fullscreen mode

Top comments (0)