recursion internally uses one stack for maintaining the return
addresses.which all we need... :-)
On Friday, June 22, 2012 11:38:39 AM UTC+5:30, joker wrote:
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
@ALL this shud work :-)
#includeiostream
#includequeue
using namespace std;
queueint Q;
void rev()
{ if(!Q.empty())
{ int x=Q.front(); Q.pop();
rev();
Q.push(x);
}
}
main()
{ for(int i=1;i12;i++) Q.push(i);
rev();
while(!Q.empty())
{ int x=Q.front();
it seems @hassan sol is correctcan nybody knw d flaw in it???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
How to reverse a Queue .
Constraints: Time complexity O(n). space complexity: O(1)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/kepls-8qRwgJ.
To post to
count the size of queue : O(n)
loop for n and do remove and add in queue : O(n)
Total : O(n)
On Wed, Jun 20, 2012 at 6:34 PM, Navin Kumar algorithm.i...@gmail.comwrote:
How to reverse a Queue .
Constraints: Time complexity O(n). space complexity: O(1)
--
You received this message because
@Saurabh: queue will be remain unchanged according to your algorithm.
Because if you will delete an element from front and add at rear no change
will be there. After n iteration front will be pointing to same element and
rear will also point to same element.
Correct me if i am wrong. :)
On Wed,
For ex: let only two element are in queue: 1 2 (1 at front and rear is at
2).
looping two times:
first time: delete from front and adding to rear: queue will be: 2 1(front
at 2 , rear at 1)
second iteration: deleting 2 and adding to queue :result will be: 1 2
(front 1, rear 2)
On Wed, Jun 20,
I meant do it for n-1 times (my focus was on time complexity).Try with more
examples and you will know :)
On Wed, Jun 20, 2012 at 6:50 PM, Navin Kumar algorithm.i...@gmail.comwrote:
For ex: let only two element are in queue: 1 2 (1 at front and rear is at
2).
looping two times:
first time:
can we create other methods or we have to use only enqueue and dequeue...?
if yes then simply
for(i=0;i=n/2;i++)
swap(i,n-i);
On Wed, Jun 20, 2012 at 6:46 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Saurabh: queue will be remain unchanged according to your algorithm.
Because if you will
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue
etc
On Wed, Jun 20, 2012 at 6:50 PM, amrit harry dabbcomput...@gmail.comwrote:
can we create other methods or we have to use only enqueue and dequeue...?
if yes then simply
for(i=0;i=n/2;i++)
swap(i,n-i);
On Wed,
You could use recursion.
def reverse_Q q
if !q.isEmpty?
el = q.dequeue
nQ = reverse_Q(q)
nQ.enqueue el
return nQ
end
return q
end
On Wednesday, June 20, 2012 6:57:23 PM UTC+5:30, Navin Kumar wrote:
Use only standard operation of Queue like: EnQueue, DeQueue, IsEmptyQueue
etc
On
@Kirubakaran : still space complexity is O(n) due to stack.Can it be solved
in space complexity O(1).
On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D kirubakara...@gmail.comwrote:
You could use recursion.
def reverse_Q q
if !q.isEmpty?
el = q.dequeue
nQ = reverse_Q(q)
nQ.enqueue el
Why will my proposed solution not work for you ???
On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Kirubakaran : still space complexity is O(n) due to stack.Can it be
solved in space complexity O(1).
On Wed, Jun 20, 2012 at 8:00 PM, Kirubakaran D
@saurabh : i want solution with space complexity of O(1) . your solution is
right but it takes O(n) space.
On Wed, Jun 20, 2012 at 8:28 PM, saurabh singh saurabh.n...@gmail.comwrote:
Why will my proposed solution not work for you ???
On Wed, Jun 20, 2012 at 8:19 PM, Navin Kumar
How ??
I am asking to manipulate the same queue.
Dequeue n-1 elements and enqueue them in order to you take out to the same
queue..Where is extra space involved ?
On Wed, Jun 20, 2012 at 8:36 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@saurabh : i want solution with space complexity of O(1)
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will take
O(1) time but you have to enqueue elements in reverse order.Not in the
order you fetched. Think about it :). Then you have to take stack or some
other data structure.
On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh
My bad...Sorry :(..Yes it certainly was not right
On Wed, Jun 20, 2012 at 8:56 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Saurabh:i was wrong in deciding space complexity. Yes, your algo will
take O(1) time but you have to enqueue elements in reverse order.Not in the
order you fetched.
@Navin: as you say you have to take stack or some other data structure
then it will definately not be donw in O(1) space complexity i think the
recursive solution is best because we are not explicitly using any extra
space its internal stack is using this space.
--
You received this message
@Rishabh: i know using stack or recursion it can be done easily with O(n)
space. I want to know whether there exist more space efficient algo for
this problem or not?
On Wed, Jun 20, 2012 at 9:20 PM, Rishabh Agarwal rishabh...@gmail.comwrote:
@Navin: as you say you have to take stack or some
i doesn't seem possible without using stack...
On Wed, Jun 20, 2012 at 10:13 PM, Navin Kumar algorithm.i...@gmail.comwrote:
@Rishabh: i know using stack or recursion it can be done easily with O(n)
space. I want to know whether there exist more space efficient algo for
this problem or not?
@saurabh : your solution require O(n) space.
On Wed, Jun 20, 2012 at 8:40 PM, saurabh singh saurabh.n...@gmail.comwrote:
How ??
I am asking to manipulate the same queue.
Dequeue n-1 elements and enqueue them in order to you take out to the same
queue..Where is extra space involved ?
On
21 matches
Mail list logo
