Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations

by

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)].

Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.

E.g for a pop request, moving all the elements from first stack [(4,4), (2,2), (5,2), (1,1)], the second stack would be [(1,1), (5,1), (2,1), (4,1)]. and now return top element from second stack.

To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values. (Of course, there’s some extra logic here is case one of the stacks is empty, but that’s not too hard to work around).

It will have O(1) get_min() and push() and amortized O(1) pop().

More Related Contents:

  1. How to implement a queue using two stacks?
  2. Computing set intersection in linear time?
  3. The intersection of all combinations of n sets
  4. Deciding a Big-O notation for an algorithm
  5. What is a plain English explanation of “Big O” notation?
  6. What does O(log n) mean exactly?
  7. How to create the most compact mapping n → isprime(n) up to a limit N?
  8. Reverse the ordering of words in a string
  9. Can hash tables really be O(1)?
  10. Difference between Big-O and Little-O Notation
  11. Time complexity of Euclid’s Algorithm
  12. What is pseudopolynomial time? How does it differ from polynomial time?
  13. Quick sort Worst case
  14. What is Constant Amortized Time?
  15. How to delete in a heap data structure?
  16. What is the difference between tree depth and height?
  17. What would cause an algorithm to have O(log n) complexity?
  18. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  19. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  20. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  21. Skip List vs. Binary Search Tree
  22. Why do we ignore co-efficients in Big O notation?
  23. Print the biggest K elements in a given heap in O(K*log(K))?
  24. Calculating phi(k) for 1
  25. How can I return an array of struct in solidity?
  26. Prove that binary heap build max comparsion is (2N-2)
  27. Difference between Big-Theta and Big O notation in simple language
  28. Why use binary search if there’s ternary search?
  29. Why are hash table expansions usually done by doubling the size?
  30. Why is bubble sort O(n^2)?

Leave a Comment