Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Stacks & Queues

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

Queue via Stacks

Implement a MyQueue class which implements a queue using two stacks.

👉 Link here to the repo to solve the problem

imagen

👌 Tips

The major difference between a queue and a stack is the order of elements. A queue removes the oldest item and a stack removes the newest item. How could you remove the oldest item from a stack if you only had access to the newest item?

We can remove the oldest item from a stack by repeatedly removing the newest item (inserting those into the temporary stack) until we get down to one element. Then, after we've retrieved the newest item, putting all the elements back. The issue with this is that doing several pops in a row will require 0 (N) work each time. Can we optimize for scenarios where we might do several pops in a row?

👊 Solution 1

This solution uses a reference to an Active and passive stack. For the inserting side of things is fairly straight forward, we just want to push onto the active stack.

For the popping it becomes a bit more difficult, for this we have to shift all the values to the passive stack pop the value and then return all of them to the passive stack.

image

public class MyQueue <T> {
    Stack<T> activeStack = new Stack<>();
    Stack<T> passiveStack = new Stack<>();
    
    public void insert(T item) {
        activeStack.push(item);
    }

    public T peek() {
        while (!activeStack.isEmpty()) {
            T current = activeStack.pop();
            passiveStack.push(current);
        }
        return passiveStack.peek();
    }

    public T pop() {
        if (activeStack.isEmpty()) throw new EmptyStackException();
        while (!activeStack.isEmpty()) {
            T current = activeStack.pop();
            passiveStack.push(current);
        }
        T value = passiveStack.pop();

        while (!passiveStack.isEmpty()) {
            T current = passiveStack.pop();
            activeStack.push(current);
        }
        
        return value;
    }
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/10/2020
← Stack Of PlatesSort Stack →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr