stack, pop, push and min in o(1)  Unix
This is a discussion on stack, pop, push and min in o(1)  Unix ; Hi Everyone,
I have a stack implementation having integers. The complexity of push
and pop is o(1). And i need to provide another functionality of
printing the minimum value in the stack. I don't have any restriction
in the space. ...

stack, pop, push and min in o(1)
Hi Everyone,
I have a stack implementation having integers. The complexity of push
and pop is o(1). And i need to provide another functionality of
printing the minimum value in the stack. I don't have any restriction
in the space. Is there any way to provide min functionality in 0(1)?
Thanks in advance ! ! !

Re: stack, pop, push and min in o(1)
Rahul writes:
>Hi Everyone,
> I have a stack implementation having integers. The complexity of push
>and pop is o(1). And i need to provide another functionality of
>printing the minimum value in the stack. I don't have any restriction
>in the space. Is there any way to provide min functionality in 0(1)?
Homework?

Chris.

Re: stack, pop, push and min in o(1)
On Apr 22, 2:05 pm, Rahul wrote:
> Hi Everyone,
>
> I have a stack implementation having integers. The complexity of push
> and pop is o(1). And i need to provide another functionality of
> printing the minimum value in the stack. I don't have any restriction
> in the space. Is there any way to provide min functionality in 0(1)?
>
> Thanks in advance ! ! !
Not really, it came up in one of the discussions, and the best that i
could do is o(log n) by creating a binary search tree as and when
elements are pushed into and removed from the stack. However, the
complexity of push, pop and min becomes o(log n) [worst case]. I was
wondering that there isn't any other better way of implementation...

Re: stack, pop, push and min in o(1)
On Apr 22, 2:05 pm, Rahul wrote:
> Hi Everyone,
>
> I have a stack implementation having integers. The complexity of push
> and pop is o(1). And i need to provide another functionality of
> printing the minimum value in the stack. I don't have any restriction
> in the space. Is there any way to provide min functionality in 0(1)?
>
> Thanks in advance ! ! !
Ok , i have found a solution and it is working fine.
#include
#include
struct stack
{
int data;
struct stack *ptr;
struct stack *next_minimum_value;
};
struct stack *minimum_node = NULL;
struct stack* push(int data,struct stack *head)
{
struct stack *new_node = (struct stack*)malloc(sizeof(struct stack));
new_node>data = data;
new_node>ptr = NULL;
new_node>next_minimum_value = NULL;
if(head != NULL)
{
new_node>ptr = head;
if(new_node>data < minimum_node>data)
{
new_node>next_minimum_value = minimum_node;
minimum_node = new_node;
}
}
else
{
minimum_node = new_node;
}
printf("%d PUSHED\n",data);
return new_node;
}
struct stack* pop(struct stack *head)
{
if(head != NULL)
{
struct stack *temp;
printf("POPED %d\n",head>data);
if(head>data == minimum_node>data)
{
minimum_node = head>next_minimum_value;
}
temp = head;
head = head>ptr;
free(temp);
}
else
{
printf("no more values in stack\n");
}
return head;
}
void min_value()
{
if(minimum_node != NULL)
{
printf("minimum value is %d\n",minimum_node>data);
}
else
{
printf("There aren't any nodes present in the stack\n");
}
}
int main()
{
struct stack *head = NULL;
min_value();
head = push(4,NULL);
min_value();
head = push(3,head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = push(1,head);
min_value();
head = push(2,head);
min_value();
head = push(1,head);
min_value();
head = push(0,head);
min_value();
head = push(10,head);
min_value();
return 0;
}

Re: stack, pop, push and min in o(1)
On Apr 22, 2:41 pm, Rahul wrote:
> On Apr 22, 2:05 pm, Rahul wrote:
>
> > Hi Everyone,
>
> > I have a stack implementation having integers. The complexity of push
> > and pop is o(1). And i need to provide another functionality of
> > printing the minimum value in the stack. I don't have any restriction
> > in the space. Is there any way to provide min functionality in 0(1)?
>
> > Thanks in advance ! ! !
>
> Ok , i have found a solution and it is working fine.
When I read your problem that solution seemed so obvious to me I
thought you were already aware of it and you seeked something else.
I suggest you modify struct stack and push() as:
struct stack
{
int data;
int (*compar)(struct stack *, struct stack *);
struct stack *ptr;
struct stack *nextval;
};
Somewhere, have
stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
/* ... */
s>compar = compar;
/* ... */
}
And in push()
if(s>compar(new_node, ...))
HTH.

Re: stack, pop, push and min in o(1)
On Apr 22, 8:34*pm, vipps...@gmail.com wrote:
> On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul wrote:
>
> > > Hi Everyone,
>
> > > *I have a stack implementation having integers. The complexity of push
> > > and pop is o(1). And i need to provide another functionality of
> > > printing the minimum value in the stack. I don't have any restriction
> > > in the space. Is there any way to provide min functionality in 0(1)?
>
> > > Thanks in advance ! ! !
>
> > Ok , i have found a solution and it is working fine.
>
>
> When I read your problem that solution seemed so obvious to me I
> thought you were already aware of it and you seeked something else.
> I suggest you modify struct stack and push() as:
>
> struct stack
> {
> *int data;
> *int (*compar)(struct stack *, struct stack *);
> *struct stack *ptr;
> *struct stack *nextval;
>
> };
>
> Somewhere, have
> stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> /* ... */
> s>compar = compar;
> /* ... */
>
> }
>
> And in push()
> if(s>compar(new_node, ...))
>
> HTH.
I don't see the advantage of your method.

Re: stack, pop, push and min in o(1)
On Apr 23, 7:03 am, Kmart Cashier wrote:
> On Apr 22, 8:34 pm, vipps...@gmail.com wrote:
>
>
>
> > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul wrote:
>
> > > > Hi Everyone,
>
> > > > I have a stack implementation having integers. The complexity of push
> > > > and pop is o(1). And i need to provide another functionality of
> > > > printing the minimum value in the stack. I don't have any restriction
> > > > in the space. Is there any way to provide min functionality in 0(1)?
>
> > > > Thanks in advance ! ! !
>
> > > Ok , i have found a solution and it is working fine.
>
> >
> > When I read your problem that solution seemed so obvious to me I
> > thought you were already aware of it and you seeked something else.
> > I suggest you modify struct stack and push() as:
>
> > struct stack
> > {
> > int data;
> > int (*compar)(struct stack *, struct stack *);
> > struct stack *ptr;
> > struct stack *nextval;
>
> > };
>
> > Somewhere, have
> > stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> > /* ... */
> > s>compar = compar;
> > /* ... */
>
> > }
>
> > And in push()
> > if(s>compar(new_node, ...))
>
> > HTH.
>
> I don't see the advantage of your method.
Can you see the advantage of qsort being a higher order function then?
It's a similar situation, what if I want the next max value? Or the
next prime?
The problem of finding the next min value is very specific and there's
a more general solution to it, which I provided.
Of course there are solutions more general than mine.

Re: stack, pop, push and min in o(1)
On Apr 22, 9:31*pm, vipps...@gmail.com wrote:
> On Apr 23, 7:03 am, Kmart Cashier wrote:
>
>
>
> > On Apr 22, 8:34 pm, vipps...@gmail.com wrote:
>
> > > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul wrote:
>
> > > > > Hi Everyone,
>
> > > > > *I have a stack implementation having integers. The complexity of push
> > > > > and pop is o(1). And i need to provide another functionality of
> > > > > printing the minimum value in the stack. I don't have any restriction
> > > > > in the space. Is there any way to provide min functionality in 0(1)?
>
> > > > > Thanks in advance ! ! !
>
> > > > Ok , i have found a solution and it is working fine.
>
> > >
> > > When I read your problem that solution seemed so obvious to me I
> > > thought you were already aware of it and you seeked something else.
> > > I suggest you modify struct stack and push() as:
>
> > > struct stack
> > > {
> > > *int data;
> > > *int (*compar)(struct stack *, struct stack *);
> > > *struct stack *ptr;
> > > *struct stack *nextval;
>
> > > };
>
> > > Somewhere, have
> > > stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> > > /* ... */
> > > s>compar = compar;
> > > /* ... */
>
> > > }
>
> > > And in push()
> > > if(s>compar(new_node, ...))
>
> > > HTH.
>
> > I don't see the advantage of your method.
>
> Can you see the advantage of qsort being a higher order function then?
> It's a similar situation, what if I want the next max value? Or the
> next prime?
> The problem of finding the next min value is very specific and there's
> a more general solution to it, which I provided.
> Of course there are solutions more general than mine. Hide quoted text 
>
>  Show quoted text 
Okay. I see the advantage of qsort beig a higher order function.

Re: stack, pop, push and min in o(1)
On Apr 23, 8:34 am, vipps...@gmail.com wrote:
> On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul wrote:
>
> > > Hi Everyone,
>
> > > I have a stack implementation having integers. The complexity of push
> > > and pop is o(1). And i need to provide another functionality of
> > > printing the minimum value in the stack. I don't have any restriction
> > > in the space. Is there any way to provide min functionality in 0(1)?
>
> > > Thanks in advance ! ! !
>
> > Ok , i have found a solution and it is working fine.
>
>
> When I read your problem that solution seemed so obvious to me I
> thought you were already aware of it and you seeked something else.
> I suggest you modify struct stack and push() as:
>
> struct stack
> {
> int data;
> int (*compar)(struct stack *, struct stack *);
> struct stack *ptr;
> struct stack *nextval;
>
> };
>
> Somewhere, have
> stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> /* ... */
> s>compar = compar;
> /* ... */
>
> }
>
> And in push()
> if(s>compar(new_node, ...))
>
> HTH.
I didn't get the logic of your suggestion, what is nextval? could you
explain with an example?

Re: stack, pop, push and min in o(1)
ARRRGL. Stop the fullquotes. Everyone! Now!
Please....

Re: stack, pop, push and min in o(1)
On Tue, 22 Apr 2008 20:34:37 0700, vippstar wrote:
> On Apr 22, 2:41 pm, Rahul wrote:
>> On Apr 22, 2:05 pm, Rahul wrote:
>>
>> > Hi Everyone,
>>
>> > I have a stack implementation having integers. The complexity of
>> > push
>> > and pop is o(1). And i need to provide another functionality of
>> > printing the minimum value in the stack. I don't have any restriction
>> > in the space. Is there any way to provide min functionality in 0(1)?
>>
>>
>> Ok , i have found a solution and it is working fine.
Alas. no. Try:
push(3); push(4); pop(); min();
>
> When I read your problem that solution seemed so obvious to me I thought
> you were already aware of it and you seeked something else. I suggest
> you modify struct stack and push() as:
[...]
> And in push()
> if(s>compar(new_node, ...))
>
> HTH.
Doing a full sorted insert means that push() is not O(1) anymore.
Although the initial solution from Rahul stops working (and
crashes) if you push/pop in a certain order.
I don't think there is a solution where push/pop/min are all O(1)
for arbitrary input/calls, although you can probably get close most
of the time.

James Antill  james@and.org
C String APIs use too much memory? ustr: length, ref count, size and
readonly/fixed. Ave. 44% overhead over strdup(), for 020B strings
http://www.and.org/ustr/

Re: stack, pop, push and min in o(1)
"James Antill" wrote in message
newsan.2008.04.23.18.35.19@and.org...
> On Tue, 22 Apr 2008 20:34:37 0700, vippstar wrote:
>
>> On Apr 22, 2:41 pm, Rahul wrote:
>>> On Apr 22, 2:05 pm, Rahul wrote:
>>>
>>> > Hi Everyone,
>>>
>>> > I have a stack implementation having integers. The complexity of
>>> > push
>>> > and pop is o(1). And i need to provide another functionality of
>>> > printing the minimum value in the stack. I don't have any restriction
>>> > in the space. Is there any way to provide min functionality in 0(1)?
>>>
>>>
>>> Ok , i have found a solution and it is working fine.
>
> Alas. no. Try:
>
> push(3); push(4); pop(); min();
>
>>
>> When I read your problem that solution seemed so obvious to me I thought
>> you were already aware of it and you seeked something else. I suggest
>> you modify struct stack and push() as:
> [...]
>> And in push()
>> if(s>compar(new_node, ...))
>>
>> HTH.
>
> Doing a full sorted insert means that push() is not O(1) anymore.
> Although the initial solution from Rahul stops working (and
> crashes) if you push/pop in a certain order.
> I don't think there is a solution where push/pop/min are all O(1)
> for arbitrary input/calls, although you can probably get close most
> of the time.
Regular priority queues will not hit that sort of performance.
A simple stack will have push() and pop() that are O(1), but you would have
to navigate the stack to find the smallest item O(n).
A priority queue will find min() in O(1), but either push() or pop() or both
will be O(log2(n))
This thing:
http://www.pmg.lcs.mit.edu/~chandra/...ions/btech.pdf
says: "Our data structure supports the operations find minimum, insert,
decrease key and meld, each in O(1) worst case time and delete and delete
min
in O(log n) worst case time."
Which is pretty darn good.
** Posted from http://www.teranews.com **

Re: stack, pop, push and min in o(1)
In article <536fa$480fa1c9$3473@news.teranews.com>,
Dann Corbit wrote:
> This thing:
> http://www.pmg.lcs.mit.edu/~chandra/...ions/btech.pdf
> says: "Our data structure supports the operations find minimum,
> insert, decrease key and meld, each in O(1) worst case time and
> delete and delete min in O(log n) worst case time."
Did you skip the 'errata' section? It will direct you to
"Worstcase efficiency priority queues" by Gerth Stolling
Brodal (which I have not yet read).

Re: stack, pop, push and min in o(1)
On Apr 23, 11:35 pm, James Antill wrote:
> On Tue, 22 Apr 2008 20:34:37 0700, vippstar wrote:
> > On Apr 22, 2:41 pm, Rahul wrote:
> >> On Apr 22, 2:05 pm, Rahul wrote:
>
> >> > Hi Everyone,
>
> >> > I have a stack implementation having integers. The complexity of
> >> > push
> >> > and pop is o(1). And i need to provide another functionality of
> >> > printing the minimum value in the stack. I don't have any restriction
> >> > in the space. Is there any way to provide min functionality in 0(1)?
>
> >> Ok , i have found a solution and it is working fine.
>
> Alas. no. Try:
>
> push(3); push(4); pop(); min();
>
struct stack *head = NULL;
head = push(3,head);
head = push(4,head);
head = pop(head);
min_value(head);
3 PUSHED
4 PUSHED
POPED 4
minimum value is 3
>
>
> >
> > When I read your problem that solution seemed so obvious to me I thought
> > you were already aware of it and you seeked something else. I suggest
> > you modify struct stack and push() as:
> [...]
> > And in push()
> > if(s>compar(new_node, ...))
>
> > HTH.
>
> Doing a full sorted insert means that push() is not O(1) anymore.
> Although the initial solution from Rahul stops working (and
> crashes) if you push/pop in a certain order.
Could you specify the order which causes the crash?

Re: stack, pop, push and min in o(1)
James Antill wrote:
[snip]
> I don't think there is a solution where push/pop/min are all O(1)
> for arbitrary input/calls, although you can probably get close most
> of the time.
Really? Rahul's implementation may have "issues" but the underlying idea
seems sound to me. Am I missing something?
Alex

Re: stack, pop, push and min in o(1)
"Alex Fraser" wrote in message
news:MeydnbEHZOQ9uI3VRVnyvAA@eclipse.net.uk...
> James Antill wrote:
> [snip]
>> I don't think there is a solution where push/pop/min are all O(1)
>> for arbitrary input/calls, although you can probably get close most
>> of the time.
>
> Really? Rahul's implementation may have "issues" but the underlying idea
> seems sound to me. Am I missing something?
Yes, it can't possibly work properly.
#include
#include
#include
struct stack {
int data;
struct stack *ptr;
struct stack *next_minimum_value;
};
struct stack *minimum_node = NULL;
struct stack *push(int data, struct stack * head)
{
struct stack *new_node = (struct stack *) malloc(sizeof(struct
stack));
assert(new_node);
if (new_node) {
new_node>data = data;
new_node>ptr = NULL;
new_node>next_minimum_value = NULL;
if (head != NULL) {
new_node>ptr = head;
if (new_node>data < minimum_node>data) {
new_node>next_minimum_value = minimum_node;
minimum_node = new_node;
}
} else {
minimum_node = new_node;
}
printf("%d PUSHED\n", data);
}
return new_node;
}
struct stack *pop(struct stack * head)
{
if (head != NULL) {
struct stack *temp;
printf("POPED %d\n", head>data);
if (head>data == minimum_node>data) {
minimum_node = head>next_minimum_value;
}
temp = head;
head = head>ptr;
free(temp);
} else {
printf("no more values in stack\n");
}
return head;
}
void min_value()
{
if (minimum_node != NULL) {
printf("minimum value is %d\n", minimum_node>data);
} else {
printf("There aren't any nodes present in the stack\n");
}
}
void clear_stack(struct stack * head)
{
while (head != NULL) {
head = pop(head);
}
}
int main()
{
struct stack *head = NULL;
min_value();
head = push(4, NULL);
min_value();
head = push(3, head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = push(1, head);
min_value();
head = push(2, head);
min_value();
head = push(1, head);
min_value();
head = push(0, head);
min_value();
head = push(10, head);
min_value();
head = push(5, head);
min_value();
head = push(7, head);
min_value();
head = push(3, head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
head = pop(head);
min_value();
clear_stack(head);
return 0;
}
** Posted from http://www.teranews.com **

Re: stack, pop, push and min in o(1)
On Wed, 23 Apr 2008 22:27:29 0700, Rahul wrote:
> On Apr 23, 11:35 pm, James Antill wrote:
>> On Tue, 22 Apr 2008 20:34:37 0700, vippstar wrote:
>> > On Apr 22, 2:41 pm, Rahul wrote:
>> >> On Apr 22, 2:05 pm, Rahul wrote:
>> >> Ok , i have found a solution and it is working fine.
>>
>> Alas. no. Try:
>>
>> push(3); push(4); pop(); min();
>>
> struct stack *head = NULL;
> head = push(3,head);
> head = push(4,head);
> head = pop(head);
> min_value(head);
>
> 3 PUSHED
> 4 PUSHED
> POPED 4
> minimum value is 3
Hmm, you're right. I can't create a case using where this happens.
I guess I was thinking of also being able to "pop" from the nonend
(most implementations of "stacks" I've used allow this), so that
when you pop the minimum might not be the same as when you pushed.
For nonunique numbers you have to deal with:
head = push(3,head);
head = push(3,head);
min_value();
head = pop(head);
min_value();
....but that's a fairly trivial fix to compare ptrs instead of data in
pop().
So, yeh, for a strict RO stack your solution basically solves the
problem.

James Antill  james@and.org
C String APIs use too much memory? ustr: length, ref count, size and
readonly/fixed. Ave. 44% overhead over strdup(), for 020B strings
http://www.and.org/ustr/