The amortized time is O(1) for extracting and pushing elements from/in the queue.
On 18 окт, 12:01, Mallesh Kavuluri <mallesh...@gmail.com> wrote: > @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.
