As I said before, O(1) time is a amortized complexity (average) for doing some long series of operations.
On 18 окт, 14:45, bujji jajala <[email protected]> wrote: > public class Queue<E> > { > > private Stack<E> inbox = new Stack<E>(); > private Stack<E> outbox = new Stack<E>(); > > public void queue(E item) { > inbox.push(item); > } > > public E dequeue() { > if (outbox.isEmpty()) { > while (!inbox.isEmpty()) { > outbox.push(inbox.pop()); > } > } > return outbox.pop(); > } > > } > > In the above code queue() function takes O(1) time and dequeue operation > takes O(n) time as it pops all the elements in one stack. > Please correct me if I am wrong. > > > > > > > > On Mon, Oct 18, 2010 at 3:59 PM, juver++ <[email protected]> wrote: > > 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> > > <algogeeks%2bunsubscr...@googlegroups .com> > > > > > > . > > > > > > For more options, visit this group at > > > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequoted 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]<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 [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.
