Code pop all elements from one stack to another only when the second
one is empty.
All other time deque operation retrieves element from the second stack
in O(1).
On 18 окт, 14:45, bujji jajala <jajalabu...@gmail.com> 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++ <avpostni...@gmail.com> wrote:
> > Please refer to the following link for the explanation:
> >http://stackoverflow.com/questions/69192/using-stack-as-queue
>
> > On 18 окт, 14:06, bujji <jajalabu...@gmail.com> wrote:
> > > Can you please explain your Algorithm to implement queue using stack
> > > in O(1) time?
>
> > > On Oct 18, 1:43 pm, "juver++" <avpostni...@gmail.com> wrote:
>
> > > > 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>
> > <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 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.
