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%[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]<algogeeks%[email protected]>
> .
> 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.
