Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Then it is O(n) worst case. While juver's algo is amortized constant time in
worst case.
On Jan 9, 2011 10:26 PM, SVIX saivivekh.swaminat...@gmail.com wrote:
The only operation for which this solution doesn't have constant time
(variable based on number of items in the list) is for 'delete' and
that too when the minimum item is deleted. For all other cases, delete
is constant as well... For delete in those special cases, time is
O(n)...
On Jan 9, 10:19 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
I think you misunderstood my solution...
There's no min value for each node here... The queue class i propose
will look like this...
public class MyQ
{
private int? currentMin; //nullable current minimum val in the
queue
private LinkedListint itemsList;
//constructor and init stuff...
//all insert/delete methods, front, rear etc,...
//one example set of insert and delete pseudocode
public void Insert(int i)
{
if( currentMin == null || currentMin i )
currentMin = i;
itemsList.Add(i);
}
public int Delete()
{
var itemToReturn = itemsList.First.Value;
itemsList.RemoveFirst();
if(itemToReturn == currentMin)
RecomputeAndStoreMin(); //A private method that'll
find and store min in O(n) time
return itemToReturn;
}
public int GetMinValue()
{
If(currentMin == null)
throw new InvalidOperationException();
return currentMin;
}
}
On Jan 9, 11:42 am, juver++ avpostni...@gmail.com wrote:
When you remove element from the front of queue, you should update min
value
for all remaining nodes.
So it's linear.
--
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.comalgogeeks%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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
When you push into stack2, you have to recompute the min value. So after you
push into stack2, it will be:
(6,6),(3,3),(4,3),(2,2)
On Thu, Jan 6, 2011 at 6:34 PM, sourav souravs...@gmail.com wrote:
@Juvier, @yq Zhang
In your approach, when you are asked pop_front() you keep popping from
one stack and pushing them to another and then from the other pop the
top element. What happens is this top element happens to have been the
Min element?Example
stack1 {(2,2),(4,2),(3,2),(6,2)} (a,b) = ( element, min)
then you are asked pop_front(), you push to another stach like below
stck2: {(6,2),(3,2),(4,2),(2,2)}.
Then you remove (2,2)! Ok. But all elements in your stack2 still say
2 is the min element. But 2 is no more in the queue (or for that
matter in the stacks we are using).
On Jan 4, 9:07 am, yq Zhang zhangyunq...@gmail.com wrote:
@sourav,
As Juvier++ pointed out, it's an **amortized** O(n) algorithm. That's
because each element can be at most popped twice.
Thanks
Yq
On Mon, Jan 3, 2011 at 11:20 AM, sourav souravs...@gmail.com wrote:
@yq Zhang,
To pop if you are going to pop all from first stack and push into the
second stack, then does your operation remain constant time? Please
note that we need constant time implementation for the 3 functions
pop_front, push_rear and get_min(). Goint by your approach, not all of
them are constant time.
Thanks,
Sourav
On Jan 3, 9:44 pm, yq Zhang zhangyunq...@gmail.com wrote:
Push into one stack. When pop first pop all from the first stack and
push
into the second stack. Then pop from the second stack
On Jan 3, 2011 7:42 AM, MOHIT mohit...@gmail.com wrote:
if only two stack are used but how pop_front is get?
suppose if element comes in order
12 15 4 3 7 20
then in min queue
1. 12 (12)
2. 12 12 (12,15)
3. 12 12 4 (12,15,4)
4.12 12 4 3 (12,15,4,3)
5.12 12 4 3 3 (12,15,4,3,7)
6.12 12 4 3 3 3 (12,15,4,3,20)
we can get min in constant by pop of stack but how pop front will
work
using
two stack only in constant 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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
only 2 stacks, one of them (or both...) should provide functionality for retrieving minimum. -- 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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- 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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
That's a big save of space! On Jan 5, 2011 9:03 AM, juver++ avpostni...@gmail.com wrote: Good point. Right. But we can avoid first stack of such structure, having separate variable (Minimum) for this. -- 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.comalgogeeks%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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
Yes, you are right. Stack contains the following pair of elements - (Min, Element), where Min - minimum element among all elements in the stack below the current, Element - current element. When you add new element onto the stack, then you should push pair(min(stack.top().Min, Element), Element). To retrieve min element from the stack, simply access its top min. -- 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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
@juver++ how will implwment find_min() function? On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Simulate queue using two stacks. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- 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.
Re: [algogeeks] Re: Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.
keep min for stack is easy. just use another stack to keep the min for each top. Sent from Nexus one On Jan 2, 2011 11:43 AM, Anuj Kumar anuj.bhambh...@gmail.com wrote: @juver++ how will implwment find_min() function? On Sun, Jan 2, 2011 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Simulate queue using two stacks. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anuj Kumar Third Year Undergraduate, Dept. of Computer Science and Engineering NIT Durgapur -- 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.comalgogeeks%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.
