By bits


2011-01-26 06:54:32 8 Comments

I came across this question: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

I initially thought of using a min-heap data structure which has O(1) complexity for a get_min(). But push_rear() and pop_front() would be O(log(n)).

Does anyone know what would be the best way to implement such a queue which has O(1) push(), pop() and min()?

I googled about this, and wanted to point out this Algorithm Geeks thread. But it seems that none of the solutions follow constant time rule for all 3 methods: push(), pop() and min().

Thanks for all the suggestions.

12 comments

@Scott Rudiger 2018-02-21 11:49:54

JavaScript implementation

(Credit to adamax's solution for the idea; I loosely based an implementation on it. Jump to the bottom to see fully commented code or read through the general steps below. Note that this finds the maximum value in O(1) constant time rather than the minimum value--easy to change up):

The general idea is to create two Stacks upon construction of the MaxQueue (I used a linked list as the underlying Stack data structure--not included in the code; but any Stack will do as long as it's implemented with O(1) insertion/deletion). One we'll mostly pop from (dqStack) and one we'll mostly push to (eqStack).


Insertion: O(1) worst case

For enqueue, if the MaxQueue is empty, we'll push the value to dqStack along with the current max value in a tuple (the same value since it's the only value in the MaxQueue); e.g.:

const m = new MaxQueue();

m.enqueue(6);

/*
the dqStack now looks like:
[6, 6] - [value, max]
*/

If the MaxQueue is not empty, we push just the value to eqStack;

m.enqueue(7);
m.enqueue(8);

/*
dqStack:         eqStack: 8
         [6, 6]           7 - just the value
*/

then, update the maximum value in the tuple.

/*
dqStack:         eqStack: 8
         [6, 8]           7
*/


Deletion: O(1) amortized

For dequeue we'll pop from dqStack and return the value from the tuple.

m.dequeue();
> 6

// equivalent to:
/*
const tuple = m.dqStack.pop() // [6, 8]
tuple[0];
> 6
*/

Then, if dqStack is empty, move all values in eqStack to dqStack, e.g.:

// if we build a MaxQueue
const maxQ = new MaxQueue(3, 5, 2, 4, 1);

/*
the stacks will look like:

dqStack:         eqStack: 1
                          4
                          2
         [3, 5]           5
*/

As each value is moved over, we'll check if it's greater than the max so far and store it in each tuple:

maxQ.dequeue(); // pops from dqStack (now empty), so move all from eqStack to dqStack
> 3

// as dequeue moves one value over, it checks if it's greater than the ***previous max*** and stores the max at tuple[1], i.e., [data, max]:
/*
dqStack: [5, 5] => 5 > 4 - update                          eqStack:
         [2, 4] => 2 < 4 - no update                         
         [4, 4] => 4 > 1 - update                            
         [1, 1] => 1st value moved over so max is itself            empty
*/

Because each value is moved to dqStack at most once, we can say that dequeue has O(1) amortized time complexity.


Finding the maximum value: O(1) worst case

Then, at any point in time, we can call getMax to retrieve the current maximum value in O(1) constant time. As long as the MaxQueue is not empty, the maximum value is easily pulled out of the next tuple in dqStack.

maxQ.getMax();
> 5

// equivalent to calling peek on the dqStack and pulling out the maximum value:
/*
const peekedTuple = maxQ.dqStack.peek(); // [5, 5]
peekedTuple[1];
> 5
*/


Code

class MaxQueue {
  constructor(...data) {
    // create a dequeue Stack from which we'll pop
    this.dqStack = new Stack();
    // create an enqueue Stack to which we'll push
    this.eqStack = new Stack();
    // if enqueueing data at construction, iterate through data and enqueue each
    if (data.length) for (const datum of data) this.enqueue(datum);
  }
  enqueue(data) { // O(1) constant insertion time
    // if the MaxQueue is empty,
    if (!this.peek()) {
      // push data to the dequeue Stack and indicate it's the max;
      this.dqStack.push([data, data]); // e.g., enqueue(8) ==> [data: 8, max: 8]
    } else {
      // otherwise, the MaxQueue is not empty; push data to enqueue Stack
      this.eqStack.push(data);
      // save a reference to the tuple that's next in line to be dequeued
      const next = this.dqStack.peek();
      // if the enqueueing data is > the max in that tuple, update it
      if (data > next[1]) next[1] = data;
    }
  }
  moveAllFromEqToDq() { // O(1) amortized as each value will move at most once
    // start max at -Infinity for comparison with the first value
    let max = -Infinity;
    // until enqueue Stack is empty,
    while (this.eqStack.peek()) {
      // pop from enqueue Stack and save its data
      const data = this.eqStack.pop();
      // if data is > max, set max to data
      if (data > max) max = data;
      // push to dequeue Stack and indicate the current max; e.g., [data: 7: max: 8]
      this.dqStack.push([data, max]);
    }
  }
  dequeue() { // O(1) amortized deletion due to calling moveAllFromEqToDq from time-to-time
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // pop from the dequeue Stack and save it's data
    const [data] = this.dqStack.pop();
    // if there's no data left in dequeue Stack, move all data from enqueue Stack
    if (!this.dqStack.peek()) this.moveAllFromEqToDq();
    // return the data
    return data;
  }
  peek() { // O(1) constant peek time
    // if the MaxQueue is empty, return undefined
    if (!this.dqStack.peek()) return;
    // peek at dequeue Stack and return its data
    return this.dqStack.peek()[0];
  }
  getMax() { // O(1) constant time to find maximum value
    // if the MaxQueue is empty, return undefined
    if (!this.peek()) return;
    // peek at dequeue Stack and return the current max
    return this.dqStack.peek()[1];
  }
}

@Sachin 2011-08-07 08:55:58

We know that push and pop are constant time operations [O(1) to be precise].

But when we think of get_min()[i.e to find the current minimum number in the queue] generally the first thing that comes to mind is searching the whole queue every time the request for the minimum element is made. But this will never give the constant time operation, which is the main aim of the problem.

This is generally asked very frequently in the interviews, so you must know the trick

To do this we have to use two more queues which will keep the track of minimum element and we have to go on modifying these 2 queues as we do push and pop operations on the queue so that minimum element is obtained in O(1) time.

Here is the self-descriptive sudo code based on the above approach mentioned.

    Queue q, minq1, minq2;
    isMinq1Current=true;   
    void push(int a)
    {
      q.push(a);
      if(isMinq1Current)
      {
        if(minq1.empty) minq1.push(a);
        else
        {
          while(!minq1.empty && minq1.top < =a) minq2.push(minq1.pop());
          minq2.push(a);
          while(!minq1.empty) minq1.pop();
          isMinq1Current=false;
        }
      }
      else
      {
        //mirror if(isMinq1Current) branch. 
      }
    }

    int pop()
    { 
      int a = q.pop();
      if(isMinq1Current)
      {
        if(a==minq1.top) minq1.pop();
      }
      else
      {
        //mirror if(isMinq1Current) branch.    
      }
    return a;
    }

@Nitish Bhagat 2017-04-02 08:12:47

Java Implementation

import java.io.*;
import java.util.*;

public class queueMin {
    static class stack {

        private Node<Integer> head;

        public void push(int data) {
            Node<Integer> newNode = new Node<Integer>(data);
            if(null == head) {
                head = newNode;
            } else {
                Node<Integer> prev = head;
                head = newNode;
                head.setNext(prev);
            }
        }

        public int pop() {
            int data = -1;
            if(null == head){
                System.out.println("Error Nothing to pop");
            } else {
                data = head.getData();
                head = head.getNext();
            }

            return data;
        }

        public int peek(){
            if(null == head){
                System.out.println("Error Nothing to pop");
                return -1;
            } else {
                return head.getData();
            }
        }

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

    static class stackMin extends stack {
        private stack s2;

        public stackMin(){
            s2 = new stack();
        }

        public void push(int data){
            if(data <= getMin()){
                s2.push(data);
            }

            super.push(data);
        }

        public int pop(){
            int value = super.pop();
            if(value == getMin()) {
                s2.pop();
            }
            return value;
        }

        public int getMin(){
            if(s2.isEmpty()) {
                return Integer.MAX_VALUE;
            }
            return s2.peek();
        }
    }

     static class Queue {

        private stackMin s1, s2;

        public Queue(){
            s1 = new stackMin();
            s2 = new stackMin();
        }

        public  void enQueue(int data) {
            s1.push(data);
        }

        public  int deQueue() {
            if(s2.isEmpty()) {
                while(!s1.isEmpty()) {
                    s2.push(s1.pop());
                }
            }

            return s2.pop();
        }

        public int getMin(){
            return Math.min(s1.isEmpty() ? Integer.MAX_VALUE : s1.getMin(), s2.isEmpty() ? Integer.MAX_VALUE : s2.getMin());
        }

    }



   static class Node<T> {
        private T data;
        private T min;
        private Node<T> next;

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


        public void setNext(Node<T> next){
            this.next = next;
        }

        public T getData(){
            return this.data;
        }

        public Node<T> getNext(){
            return this.next;
        }

        public void setMin(T min){
            this.min = min;
        }

        public T getMin(){
            return this.min;
        }
    }

    public static void main(String args[]){
       try {
           FastScanner in = newInput();
           PrintWriter out = newOutput();
          // System.out.println(out);
           Queue q = new Queue();
           int t = in.nextInt();
           while(t-- > 0) {
               String[] inp = in.nextLine().split(" ");
               switch (inp[0]) {
                   case "+":
                       q.enQueue(Integer.parseInt(inp[1]));
                       break;
                   case "-":
                       q.deQueue();
                       break;
                   case "?":
                       out.println(q.getMin());
                   default:
                       break;
               }
           }
           out.flush();
           out.close();

       } catch(IOException e){
          e.printStackTrace();
       }
    }

    static class FastScanner {
        static BufferedReader br;
        static StringTokenizer st;

        FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }
        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDoulbe() {
            return Double.parseDouble(next());
        }
    }

    static FastScanner newInput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new FastScanner(new File("input.txt"));
        } else {
            return new FastScanner(System.in);
        }
    }
    static PrintWriter newOutput() throws IOException {
        if (System.getProperty("JUDGE") != null) {
            return new PrintWriter("output.txt");
        } else {
            return new PrintWriter(System.out);
        }
    }
}

@user3139774 2016-03-24 17:19:55

This solution contains 2 queues:
1. main_q - stores the input numbers.
2. min_q - stores the min numbers by certain rules that we'll described (appear in functions MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min()).

Here's the code in Python. Queue is implemented using a List.
The main idea lies in the MainQ.enqueue(x), MainQ.dequeue(), MainQ.get_min() functions.
One key assumption is that emptying a queue takes o(0).
A test is provided at the end.

import numbers

class EmptyQueueException(Exception):
    pass

class BaseQ():
    def __init__(self):
        self.l = list()

    def enqueue(self, x):
        assert isinstance(x, numbers.Number)
        self.l.append(x)

    def dequeue(self):
        return self.l.pop(0)

    def peek_first(self):
        return self.l[0]

    def peek_last(self):
        return self.l[len(self.l)-1]

    def empty(self):
        return self.l==None or len(self.l)==0

    def clear(self):
        self.l=[]

class MainQ(BaseQ):
    def __init__(self, min_q):
        super().__init__()
        self.min_q = min_q

    def enqueue(self, x):
        super().enqueue(x)
        if self.min_q.empty():
            self.min_q.enqueue(x)
        elif x > self.min_q.peek_last():
            self.min_q.enqueue(x)
        else: # x <= self.min_q.peek_last():
            self.min_q.clear()
            self.min_q.enqueue(x)

    def dequeue(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty")
        x = super().dequeue()
        if x == self.min_q.peek_first():
            self.min_q.dequeue()
        return x

    def get_min(self):
        if self.empty():
            raise EmptyQueueException("Queue is empty, NO minimum")
        return self.min_q.peek_first()

INPUT_NUMS = (("+", 5), ("+", 10), ("+", 3), ("+", 6), ("+", 1), ("+", 2), ("+", 4), ("+", -4), ("+", 100), ("+", -40),
              ("-",None), ("-",None), ("-",None), ("+",-400), ("+",90), ("-",None),
              ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None), ("-",None))

if __name__ == '__main__':
    min_q = BaseQ()
    main_q = MainQ(min_q)

    try:
        for operator, i in INPUT_NUMS:
            if operator=="+":
                main_q.enqueue(i)
                print("Added {} ; Min is: {}".format(i,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
            else:
                x = main_q.dequeue()
                print("Removed {} ; Min is: {}".format(x,main_q.get_min()))
                print("main_q = {}".format(main_q.l))
                print("min_q = {}".format(main_q.min_q.l))
                print("==========")
    except Exception as e:
        print("exception: {}".format(e))

The output of the above test is:

"C:\Program Files\Python35\python.exe" C:/dev/python/py3_pocs/proj1/priority_queue.py
Added 5 ; Min is: 5
main_q = [5]
min_q = [5]
==========
Added 10 ; Min is: 5
main_q = [5, 10]
min_q = [5, 10]
==========
Added 3 ; Min is: 3
main_q = [5, 10, 3]
min_q = [3]
==========
Added 6 ; Min is: 3
main_q = [5, 10, 3, 6]
min_q = [3, 6]
==========
Added 1 ; Min is: 1
main_q = [5, 10, 3, 6, 1]
min_q = [1]
==========
Added 2 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2]
min_q = [1, 2]
==========
Added 4 ; Min is: 1
main_q = [5, 10, 3, 6, 1, 2, 4]
min_q = [1, 2, 4]
==========
Added -4 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4]
min_q = [-4]
==========
Added 100 ; Min is: -4
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100]
min_q = [-4, 100]
==========
Added -40 ; Min is: -40
main_q = [5, 10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 5 ; Min is: -40
main_q = [10, 3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 10 ; Min is: -40
main_q = [3, 6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Removed 3 ; Min is: -40
main_q = [6, 1, 2, 4, -4, 100, -40]
min_q = [-40]
==========
Added -400 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400]
min_q = [-400]
==========
Added 90 ; Min is: -400
main_q = [6, 1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 6 ; Min is: -400
main_q = [1, 2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 1 ; Min is: -400
main_q = [2, 4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 2 ; Min is: -400
main_q = [4, -4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 4 ; Min is: -400
main_q = [-4, 100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed -4 ; Min is: -400
main_q = [100, -40, -400, 90]
min_q = [-400, 90]
==========
Removed 100 ; Min is: -400
main_q = [-40, -400, 90]
min_q = [-400, 90]
==========
Removed -40 ; Min is: -400
main_q = [-400, 90]
min_q = [-400, 90]
==========
Removed -400 ; Min is: 90
main_q = [90]
min_q = [90]
==========
exception: Queue is empty, NO minimum

Process finished with exit code 0

@jianglai 2013-08-16 00:25:17

Use one deque (A) to store the elements and another deque (B) to store the minimums.

When x is enqueued, push_back it to A and keep pop_backing B until the back of B is smaller than x, then push_back x to B.

when dequeuing A, pop_front A as return value, and if it is equal to the front of B, pop_front B as well.

when getting the minimum of A, use the front of B as return value.

dequeue and getmin are obviously O(1). For the enqueue operation, consider the push_back of n elements. There are n push_back to A, n push_back to B and at most n pop_back of B because each element will either stay in B or being popped out once from B. Over all there are O(3n) operations and therefore the amortized cost is O(1) as well for enqueue.

Lastly the reason this algorithm works is that when you enqueue x to A, if there are elements in B that are larger than x, they will never be minimums now because x will stay in the queue A longer than any elements in B (a queue is FIFO). Therefore we need to pop out elements in B (from the back) that are larger than x before we push x into B.

from collections import deque


class MinQueue(deque):
    def __init__(self):
        deque.__init__(self)
        self.minq = deque()

    def push_rear(self, x):
        self.append(x)
        while len(self.minq) > 0 and self.minq[-1] > x:
            self.minq.pop()
        self.minq.append(x)

    def pop_front(self):
        x = self.popleft()
        if self.minq[0] == x:
            self.minq.popleft()
        return(x)

    def get_min(self):
        return(self.minq[0])

@TheMan 2013-09-30 01:20:49

#include <iostream>
#include <queue>
#include <deque>
using namespace std;

queue<int> main_queue;
deque<int> min_queue;

void clearQueue(deque<int> &q)
{
  while(q.empty() == false) q.pop_front();
}

void PushRear(int elem)
{
  main_queue.push(elem);

  if(min_queue.empty() == false && elem < min_queue.front())
  {
      clearQueue(min_queue);
  }

  while(min_queue.empty() == false && elem < min_queue.back())
  {
      min_queue.pop_back();
  }

  min_queue.push_back(elem);
}

void PopFront() 
{
  int elem = main_queue.front();
  main_queue.pop();

  if (elem == min_queue.front())
  {
       min_queue.pop_front();
  }
}

int GetMin() 
{ 
  return min_queue.front(); 
}

int main()
{
  PushRear(1);
  PushRear(-1);
  PushRear(2);

  cout<<GetMin()<<endl;
  PopFront();
  PopFront();
  cout<<GetMin()<<endl;

  return 0;
}

@Richard 2014-02-19 15:49:29

It's not good to post code without an accompanying, clearly-stated explanation of why the code is right.

@TheMan 2014-04-30 02:58:07

That code is very self explanatory. If you want explanation, you could ask instead of down voting, please?

@Richard 2014-04-30 06:53:51

One of the qualities I like best about StackOverflow is the high quality of the answers here. When I visit other sites it seems like everyone who posts is just throwing up wads of "self-explanatory code", like yours. Inevitably, some of these are wrong and each one takes time to understand and verify. A good answer carries you through the verification process and preemptively answers questions you might have. It's hard to remember to come back and check on these things, so I prefer to down vote and then neutralize or up-vote.

@j_random_hacker 2017-05-08 11:12:16

AFAICT, this is the same algorithm as that already given as source code and described by jianglai more than a month earlier.

@adamax 2011-01-26 07:36:19

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().

@templatetypedef 2011-01-26 07:37:42

How does using two stacks to implement the queue give you amortized O(1) pop?

@adamax 2011-01-26 07:39:27

@template Each element can be moved from one stack to another only once.

@templatetypedef 2011-01-26 07:41:45

@adamax- What if I alternate between pushing and popping on every step? Doesn't that move the nodes back and forth repeatedly?

@adamax 2011-01-26 07:45:23

@template Seems that the implementation in that answer is incorrect. I fixed the link. We always push to one stack and pop from another one.

@Olhovsky 2011-01-26 07:53:18

If you store the "current minimum together with the elements", and you pop the minimum from the queue, how would you know what the new minimum is, in O(1) time?

@adamax 2011-01-26 07:55:55

@Kdoto We don't pop the minimum, it's a usual FIFO queue

@Olhovsky 2011-01-26 07:57:02

I know, I'm asking: If you pop an item, and that item happens to be the minimum, how do you know what the new minimum is?

@adamax 2011-01-26 07:58:07

@Kdoto: the minimum for the queue is the minimum of minimums for each stack. The minimum for the stack is the minimum stored at the top of the stack.

@adamax 2011-01-26 08:01:15

@Kdoto: Sorry, my answer wasn't clear. I added a clarification.

@Olhovsky 2011-01-26 08:27:04

After thinking about this answer for a while, I think that this works. Nice. +1

@Chris Hopman 2011-01-26 08:51:21

push() is O(1) (not amortized).

@Matthieu M. 2011-01-26 10:16:51

@adamax: Brilliant! I corrected the push complexity following @Chris' remark and reformatted the answer a bit, for clarity.

@bits 2011-01-26 17:55:34

@Matthieu: I see you stored current minimum as pairs. You explained very well about queue() and dequeue(). Can you explain how are we going to implement get_min()? Because I can't understand how your own example [(4,4), (2,2), (5,2), (1,1)] is going to work.

@Matthieu M. 2011-01-26 18:07:47

@bits: actually I only edited the answer, @adamax has got all the credit for publishing it :) To answer your question though, it's easy. If you look at the stack, you'll see that the minimum is contained as the second member of the top pair (1,1) here. If you pop (1,1), then the minimum is 2 as indicated by (5,2). You have two stack, so it's a matter of taking the minimum of the stacks minimum (a simple comparison).

@bits 2011-01-26 18:38:15

Yup, (sorry for giving off the wrong credit). But to continue one the issue: Why would you pop from from rear? Its a queue, which means that we are going to pop from front (4,4) and then (2,2)... but after we pop (2,2), we are left with [(5,2),(1,1)]. So in other words, I still can't get how get_min() is implemented.

@adamax 2011-01-26 19:27:27

@bits In stack pop and push are done from the same side.

@UmmaGumma 2011-01-26 20:29:46

@adamax please provide us with example. It is too difficult to understand what are you doing.

@adamax 2011-01-26 20:44:47

@Ashot 1. Implement stack with O(1) push, pop and get_min. 2. Implement the queue on the basis of 2 stacks (with get_min) as described on the link. (You don't need to read the whole page, just the relevant section.) 3. get_min for the queue = min(get_min for the stacks). Which part is unclear?

@UmmaGumma 2011-01-26 21:01:39

@adamax I can't understand 3rd part. How your minimum is working. As you see there are too many comments here. Why just not provide a little example, with your algorithms steps. It will help understand your algorithm.

@adamax 2011-01-26 21:10:28

@Ashot The third part is trivial: all elements are stored in two stacks. The minimum element is the minimum of two numbers: the minimum of numbers from the first stack and from the second stack.

@UmmaGumma 2011-01-26 21:28:33

@adamax OK, lets I pushed elements [1,5,2] to first stack and got [ (1,1), (5,1), (2,1)]. Now I want to pop element. I need to move all elements from first stack to second empty stack. After it I will have empty first stack and second stack with first stack old values but reversed in order( [(2,1),(5,1),(1,1)]). Now I'm poping second stack. After it I will have [(2,1),(5,1)] in second stack and empty first stack. Now, what is minimal element and how should I get it? So what I'm doing wrong?

@adamax 2011-01-26 21:34:16

@Ashot No, you pop the element 2 from the first stack, push it to the second stack, it becomes [(2,2)]. Then you pop element 5, push it to the second stack, it becomes [(2,2), (5,2)]. Etc.

@bits 2011-01-26 21:35:49

@adamax: I still think we are not on the same page. Because I can't figure out from your solution how get_min() will work properly in constant time. As Ashot requested, can you please post an example of how get_min() will work? If you think its difficult to explain in comments, can you write your solution in pastebin.com and post the link here.

@adamax 2011-01-26 21:48:55

@bits I've already given an example of how it works. I'm not going to write the code. Stop thinking about underlying structure of the stack for a bit. Think of it as an interface: pop(), push() and get_min(). Do you understand that if we have this interface, then we have the queue with get_min?

@bits 2011-01-26 21:54:08

@adamax: I am not requesting you to write code. I was just hoping that you would post some step by step example to support your solution. Showing the contents of your 2 stacks in each step and how get_min() would work after each step would be sufficient. Its not too much to ask. You think you have a solution, I just want to validate it and put it out clearly for StackOverflow visitors. Thanks for the help.

@adamax 2011-01-26 21:57:44

@bits Ashot's example: [(1,1), (5,1), (2,1)] [] When we extract the element, we first pop elements one by one from the first stack and push to another one. It becomes: [] [(2,2), (5,2), (1,1)]. Then we pop: [] [(2,2), (5,2)]. The minimum is 2 at the top of the stack.

@UmmaGumma 2011-01-26 22:28:47

@adamax I finally understand your solution. You should add to your explanation, that we should recalculate values of second elements, when we moving elements from first structure to second. By the way as I show in my answer It's possible to do all this operations in o(1) and not in amortized O(1). :)

@bits 2011-01-26 22:36:26

@adamax: ok, now everything is clear to me. I was missing the point that the 2nd stack modifies the pairs according to the current minimum. Very elegant solution. Thanks for being patient with me. This discussion will definitely help Stack Overflow community. Accepting your solution.

@bits 2011-01-26 22:37:22

@Ashot: I agree its worst-case O(1). Really nice one Adamax.

@Yves Daoust 2014-04-04 08:05:03

A very interesting generalization of the sliding window minimum algorithm !

@Alan Wang 2017-03-16 01:49:48

I am still trying to understand, but it seems the main incentive for the two-stack trick is that the get_min() for a stack is much easier than get_min() for a queue, right?

@avl_sweden 2018-04-06 20:25:00

Does this datastructure have a name?

@Alex Li 2018-11-26 06:36:31

Implemented in java (albeit getting max rather than min) pastebin.com/NT5JcjNP

@templatetypedef 2011-01-26 07:49:46

Okay - I think I have an answer that gives you all of these operations in amortized O(1), meaning that any one operation could take up to O(n), but any sequence of n operations takes O(1) time per operation.

The idea is to store your data as a Cartesian tree. This is a binary tree obeying the min-heap property (each node is no bigger than its children) and is ordered in a way such that an inorder traversal of the nodes gives you back the nodes in the same order in which they were added. For example, here's a Cartesian tree for the sequence 2 1 4 3 5:

       1
     /   \
    2      3
          / \
         4   5

It is possible to insert an element into a Cartesian tree in O(1) amortized time using the following procedure. Look at the right spine of the tree (the path from the root to the rightmost leaf formed by always walking to the right). Starting at rightmost node, scan upward along this path until you find the first node smaller than the node you're inserting.
Change that node so that its right child is this new node, then make that node's former right child the left child of the node you just added. For example, suppose that we want to insert another copy of 2 into the above tree. We walk up the right spine past the 5 and the 3, but stop below the 1 because 1 < 2. We then change the tree to look like this:

       1
     /   \
    2      2
          /
         3
        / \
       4   5

Notice that an inorder traversal gives 2 1 4 3 5 2, which is the sequence in which we added the values.

This runs in amortized O(1) because we can create a potential function equal to the number of nodes in the right spine of the tree. The real time required to insert a node is 1 plus the number of nodes in the spine we consider (call this k). Once we find the place to insert the node, the size of the spine shrinks by length k - 1, since each of the k nodes we visited are no longer on the right spine, and the new node is in its place. This gives an amortized cost of 1 + k + (1 - k) = 2 = O(1), for the amortized O(1) insert. As another way of thinking about this, once a node has been moved off the right spine, it's never part of the right spine again, and so we will never have to move it again. Since each of the n nodes can be moved at most once, this means that n insertions can do at most n moves, so the total runtime is at most O(n) for an amortized O(1) per element.

To do a dequeue step, we simply remove the leftmost node from the Cartesian tree. If this node is a leaf, we're done. Otherwise, the node can only have one child (the right child), and so we replace the node with its right child. Provided that we keep track of where the leftmost node is, this step takes O(1) time. However, after removing the leftmost node and replacing it with its right child, we might not know where the new leftmost node is. To fix this, we simply walk down the left spine of the tree starting at the new node we just moved to the leftmost child. I claim that this still runs in O(1) amortized time. To see this, I claim that a node is visited at most once during any one of these passes to find the leftmost node. To see this, note that once a node has been visited this way, the only way that we could ever need to look at it again would be if it were moved from a child of the leftmost node to the leftmost node. But all the nodes visited are parents of the leftmost node, so this can't happen. Consequently, each node is visited at most once during this process, and the pop runs in O(1).

We can do find-min in O(1) because the Cartesian tree gives us access to the smallest element of the tree for free; it's the root of the tree.

Finally, to see that the nodes come back in the same order in which they were inserted, note that a Cartesian tree always stores its elements so that an inorder traversal visits them in sorted order. Since we always remove the leftmost node at each step, and this is the first element of the inorder traversal, we always get the nodes back in the order in which they were inserted.

In short, we get O(1) amortized push and pop, and O(1) worst-case find-min.

If I can come up with a worst-case O(1) implementation, I'll definitely post it. This was a great problem; thanks for posting it!

@Olhovsky 2011-01-26 08:14:33

I'm still considering whether your pop is really amortized O(1). I'll be sure to upvote this answer when I confirm this. It would be nice if someone else helped to verify this answer also.

@templatetypedef 2011-01-26 08:15:53

@Kdoto- Come to think of it, you need each node to store a parent pointer if you want to get the O(1) amortized dequeue, since that way when you remove a leaf you can update the pointer to the leftmost node in the tree in worst-case O(1).

@Sandeep 2012-03-08 05:20:49

You Can actually use a LinkedList to maintain the Queue.

Each element in LinkedList will be of Type

class LinkedListElement
{
   LinkedListElement next;
   int currentMin;
}

You can have two pointers One points to the Start and the other points to the End.

If you add an element to the start of the Queue. Examine the Start pointer and the node to insert. If node to insert currentmin is less than start currentmin node to insert currentmin is the minimum. Else update the currentmin with start currentmin.

Repeat the same for enque.

@UmmaGumma 2011-01-26 22:11:05

Ok, here is one solution.

First we need some stuff which provide push_back(),push_front(),pop_back() and pop_front() in 0(1). It's easy to implement with array and 2 iterators. First iterator will point to front, second to back. Let's call such stuff deque.

Here is pseudo-code:

class MyQueue//Our data structure
{
    deque D;//We need 2 deque objects
    deque Min;

    push(element)//pushing element to MyQueue
    {
        D.push_back(element);
        while(Min.is_not_empty() and Min.back()>element)
             Min.pop_back();
        Min.push_back(element);
    }
    pop()//poping MyQueue
    {
         if(Min.front()==D.front() )
            Min.pop_front();
         D.pop_front();
    }

    min()
    {
         return Min.front();
    }
}

Explanation:

Example let's push numbers [12,5,10,7,11,19] and to our MyQueue

1)pushing 12

D [12]
Min[12]

2)pushing 5

D[12,5]
Min[5] //5>12 so 12 removed

3)pushing 10

D[12,5,10]
Min[5,10]

4)pushing 7

D[12,5,10,7]
Min[5,7]

6)pushing 11

D[12,5,10,7,11]
Min[5,7,11]

7)pushing 19

D[12,5,10,7,11,19]
Min[5,7,11,19]

Now let's call pop_front()

we got

 D[5,10,7,11,19]
 Min[5,7,11,19]

The minimum is 5

Let's call pop_front() again

Explanation: pop_front will remove 5 from D, but it will pop front element of Min too, because it equals to D's front element (5).

 D[10,7,11,19]
 Min[7,11,19]

And minimum is 7. :)

@adamax 2011-01-26 22:55:22

It seems that if you push 2, 3, 1 then get_min returns 2 instead of 1.

@UmmaGumma 2011-01-26 23:09:36

@adamax Oops :). You got me. I corrected push(). Now it's working correct, but not in 0(1). It is working in amortized O(1) like yours :).

@seeker 2014-10-20 05:18:51

@UmmaGumma,good job! Minor correction though, its 5<12 when 12 is popped off the stack.

@Olhovsky 2011-01-26 08:28:15

Solutions to this question, including code, can be found here: http://discuss.joelonsoftware.com/default.asp?interview.11.742223.32

@Richard 2014-02-19 15:51:52

Links to outside pages are unhelpful. What if the link breaks? Also: the page you link too is just a long discussion. A good answer would capture the important elements of that discussion and leave out the fluff.

@Andy Mikula 2011-01-26 07:12:24

If you don't mind storing a bit of extra data, it should be trivial to store the minimum value. Push and pop can update the value if the new or removed element is the minimum, and returning the minimum value is as simple as getting the value of the variable.

This is assuming that get_min() does not change the data; if you would rather have something like pop_min() (i.e. remove the minimum element), you can simply store a pointer to the actual element and the element preceding it (if any), and update those accordingly with push_rear() and pop_front() as well.

Edit after comments:

Obviously this leads to O(n) push and pop in the case that the minimum changes on those operations, and so does not strictly satisfy the requirements.

@templatetypedef 2011-01-26 07:13:10

Doesn't this give you an O(n) pop, since you have to scan all the elements to find the new min?

@bits 2011-01-26 07:15:36

I think get_min() doesn't actually pop the data. But pop_front() does pop the data. Lets say the front node is also the min node, so its popped. Now how can we maintain the min property in constant time?

@Andy Mikula 2011-01-26 07:27:20

Ah, good call...though you're right, @bits, it's only O(n) in the case that you push a new minimum or pop your current minimum. If it has to be worst-case O(1), I don't know that it's possible, but I would love to see otherwise.

Related Questions

Sponsored Content

9 Answered Questions

[SOLVED] Best implementation of Java Queue?

  • 2012-06-22 03:12:01
  • Georges Oates Larsen
  • 78192 View
  • 47 Score
  • 9 Answer
  • Tags:   java queue

23 Answered Questions

[SOLVED] How do you implement a Stack and a Queue in JavaScript?

6 Answered Questions

[SOLVED] Constant Amortized Time

44 Answered Questions

2 Answered Questions

[SOLVED] built-in max heap API in Python

1 Answered Questions

[SOLVED] implementing priority queues and heaps

4 Answered Questions

2 Answered Questions

Sponsored Content