Please refer to the following link for the explanation: http://stackoverflow.com/questions/69192/using-stack-as-queue
On 18 окт, 14:06, bujji <[email protected]> wrote: > Can you please explain your Algorithm to implement queue using stack > in O(1) time? > > On Oct 18, 1:43 pm, "juver++" <[email protected]> wrote: > > > > > > > > > The amortized time is O(1) for extracting and pushing elements from/in > > the queue. > > > On 18 ÏËÔ, 12:01, Mallesh Kavuluri <[email protected]> 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++ <[email protected]> > > > > > 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 <[email protected]> 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 [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]<algogeeks%2bunsubscr...@googlegroups > > > > .com> > > > > . > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - > > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
