@Juver Simulating queue with Stack takes O(n) time. If it takes O(1) time, then your solution is correct.
If simulating Queue with stack takes O(n) time, then your solution complexity will be O(n) and not O(1). 2010/10/16 juver++ <avpostni...@gmail.com> > Suppose you have a stack data structure which has additional > operation findMin() - returns smallest element on the stack. > This can be easily updated in O(1) while pushing new element onto the > stack. > > It is known that queue DS can be simulated by using two stacks (here > we use stacks which have findMin routine). > From this point we are able to retrieve smallest element from the > queue in O(1). > > On 13 окт, 22:22, malli <mallesh...@gmail.com> wrote: > > A queue data structure has functions enqueue(int x) ( inserts element > > in right end), dequeue() ( deletes element from left end) functions. > > These operations take O(1) time. Modify this queue data structure, so > > that it supports findmin() which returns minimum element of stack in > > O(1) time. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
