# stack, pop, push and min in o(1)

• 04-22-2008, 09:05 AM
unix
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 ! ! !
• 04-22-2008, 09:17 AM
unix
Re: stack, pop, push and min in o(1)
Rahul <sam_cit@yahoo.co.in> writes:
[color=blue]
>Hi Everyone,[/color]
[color=blue]
> 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)?[/color]

Homework?

--
Chris.
• 04-22-2008, 09:40 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=blue]
> 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 ! ! ![/color]

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...
• 04-22-2008, 11:41 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=blue]
> 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 ! ! ![/color]

Ok , i have found a solution and it is working fine.

#include <stdio.h>
#include <stdlib.h>

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(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 *temp;
{
}
free(temp);
}
else
{
printf("no more values in stack\n");
}
}

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()
{
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();

min_value();
min_value();
min_value();
min_value();
min_value();
return 0;
}
• 04-23-2008, 03:34 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=blue]
> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:
>[color=green]
> > Hi Everyone,[/color]
>[color=green]
> > 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)?[/color]
>[color=green]
> > Thanks in advance ! ! ![/color]
>
> Ok , i have found a solution and it is working fine.[/color]
<snip C solution>
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.
• 04-23-2008, 04:03 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 22, 8:34*pm, vipps...@gmail.com wrote:[color=blue]
> On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:
>[color=green][color=darkred]
> > > Hi Everyone,[/color][/color]
>[color=green][color=darkred]
> > > *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)?[/color][/color]
>[color=green][color=darkred]
> > > Thanks in advance ! ! ![/color][/color]
>[color=green]
> > Ok , i have found a solution and it is working fine.[/color]
>
> <snip C solution>
> 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.[/color]

• 04-23-2008, 04:31 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 23, 7:03 am, K-mart Cashier <cdal...@gmail.com> wrote:[color=blue]
> On Apr 22, 8:34 pm, vipps...@gmail.com wrote:
>
>
>[color=green]
> > On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:[/color]
>[color=green][color=darkred]
> > > > Hi Everyone,[/color][/color]
>[color=green][color=darkred]
> > > > 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)?[/color][/color]
>[color=green][color=darkred]
> > > > Thanks in advance ! ! ![/color][/color]
>[color=green][color=darkred]
> > > Ok , i have found a solution and it is working fine.[/color][/color]
>[color=green]
> > <snip C solution>
> > 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:[/color]
>[color=green]
> > struct stack
> > {
> > int data;
> > int (*compar)(struct stack *, struct stack *);
> > struct stack *ptr;
> > struct stack *nextval;[/color]
>[color=green]
> > };[/color]
>[color=green]
> > Somewhere, have
> > stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> > /* ... */
> > s->compar = compar;
> > /* ... */[/color]
>[color=green]
> > }[/color]
>[color=green]
> > And in push()
> > if(s->compar(new_node, ...))[/color]
>[color=green]
> > HTH.[/color]
>
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.
• 04-23-2008, 04:42 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 22, 9:31*pm, vipps...@gmail.com wrote:[color=blue]
> On Apr 23, 7:03 am, K-mart Cashier <cdal...@gmail.com> wrote:
>
>
>[color=green]
> > On Apr 22, 8:34 pm, vipps...@gmail.com wrote:[/color]
>[color=green][color=darkred]
> > > On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:[/color][/color]
>[color=green][color=darkred]
> > > > > Hi Everyone,[/color][/color]
>[color=green][color=darkred]
> > > > > *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)?[/color][/color]
>[color=green][color=darkred]
> > > > > Thanks in advance ! ! ![/color][/color]
>[color=green][color=darkred]
> > > > Ok , i have found a solution and it is working fine.[/color][/color]
>[color=green][color=darkred]
> > > <snip C solution>
> > > 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:[/color][/color]
>[color=green][color=darkred]
> > > struct stack
> > > {
> > > *int data;
> > > *int (*compar)(struct stack *, struct stack *);
> > > *struct stack *ptr;
> > > *struct stack *nextval;[/color][/color]
>[color=green][color=darkred]
> > > };[/color][/color]
>[color=green][color=darkred]
> > > Somewhere, have
> > > stack_init(/* ... */, int (*compar)(struct stack *, struct stack *)) {
> > > /* ... */
> > > s->compar = compar;
> > > /* ... */[/color][/color]
>[color=green][color=darkred]
> > > }[/color][/color]
>[color=green][color=darkred]
> > > And in push()
> > > if(s->compar(new_node, ...))[/color][/color]
>[color=green][color=darkred]
> > > HTH.[/color][/color]
>[color=green]
>
> 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 -[/color]

Okay. I see the advantage of qsort beig a higher order function.
• 04-23-2008, 05:31 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 23, 8:34 am, vipps...@gmail.com wrote:[color=blue]
> On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:
>[color=green][color=darkred]
> > > Hi Everyone,[/color][/color]
>[color=green][color=darkred]
> > > 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)?[/color][/color]
>[color=green][color=darkred]
> > > Thanks in advance ! ! ![/color][/color]
>[color=green]
> > Ok , i have found a solution and it is working fine.[/color]
>
> <snip C solution>
> 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.[/color]

I didn't get the logic of your suggestion, what is nextval? could you
explain with an example?
• 04-23-2008, 08:56 AM
unix
Re: stack, pop, push and min in o(1)
ARRRGL. Stop the fullquotes. Everyone! Now!

• 04-23-2008, 06:35 PM
unix
Re: stack, pop, push and min in o(1)
On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
[color=blue]
> On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=green]
>> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:
>>[color=darkred]
>> > Hi Everyone,[/color]
>>[color=darkred]
>> > 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)?[/color]
>>
>>
>> Ok , i have found a solution and it is working fine.[/color][/color]

Alas. no. Try:

push(3); push(4); pop(); min();
[color=blue]
> <snip C solution>
> 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:[/color]
[...][color=blue]
> And in push()
> if(s->compar(new_node, ...))
>
> HTH.[/color]

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 -- [email]james@and.org[/email]
C String APIs use too much memory? ustr: length, ref count, size and
[url]http://www.and.org/ustr/[/url]
• 04-23-2008, 08:53 PM
unix
Re: stack, pop, push and min in o(1)
"James Antill" <james-netnews@and.org> wrote in message
news:pan.2008.04.23.18.35.19@and.org...[color=blue]
> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
>[color=green]
>> On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=darkred]
>>> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> 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.[/color][/color]
>
> Alas. no. Try:
>
> push(3); push(4); pop(); min();
>[color=green]
>> <snip C solution>
>> 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:[/color]
> [...][color=green]
>> And in push()
>> if(s->compar(new_node, ...))
>>
>> HTH.[/color]
>
> 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.[/color]

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:
[url]http://www.pmg.lcs.mit.edu/~chandra/publications/btech.pdf[/url]
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 [url]http://www.teranews.com[/url] **
• 04-24-2008, 04:59 AM
unix
Re: stack, pop, push and min in o(1)
In article <536fa\$480fa1c9\$3473@news.teranews.com>,
Dann Corbit wrote:
[color=blue]
> This thing:
> [url]http://www.pmg.lcs.mit.edu/~chandra/publications/btech.pdf[/url]
> 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."[/color]

Did you skip the 'errata' section? It will direct you to
"Worst-case efficiency priority queues" by Gerth Stolling
Brodal (which I have not yet read).

• 04-24-2008, 05:27 AM
unix
Re: stack, pop, push and min in o(1)
On Apr 23, 11:35 pm, James Antill <james-netn...@and.org> wrote:[color=blue]
> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:[color=green]
> > On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:[color=darkred]
> >> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:[/color][/color]
>[color=green][color=darkred]
> >> > Hi Everyone,[/color][/color]
>[color=green][color=darkred]
> >> > 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)?[/color][/color]
>[color=green][color=darkred]
> >> Ok , i have found a solution and it is working fine.[/color][/color]
>
> Alas. no. Try:
>
> push(3); push(4); pop(); min();
>[/color]

3 PUSHED
4 PUSHED
POPED 4
minimum value is 3

[color=blue]
>
>[color=green]
> > <snip C solution>
> > 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:[/color]
> [...][color=green]
> > And in push()
> > if(s->compar(new_node, ...))[/color]
>[color=green]
> > HTH.[/color]
>
> 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.[/color]

Could you specify the order which causes the crash?
• 04-24-2008, 06:16 AM
unix
Re: stack, pop, push and min in o(1)
James Antill wrote:
[snip][color=blue]
> 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.[/color]

Really? Rahul's implementation may have "issues" but the underlying idea
seems sound to me. Am I missing something?

Alex
• 04-24-2008, 07:36 PM
unix
Re: stack, pop, push and min in o(1)
"Alex Fraser" <me@privacy.net> wrote in message
news:MeydnbEHZOQ9uI3VRVnyvAA@eclipse.net.uk...[color=blue]
> James Antill wrote:
> [snip][color=green]
>> 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.[/color]
>
> Really? Rahul's implementation may have "issues" but the underlying idea
> seems sound to me. Am I missing something?[/color]

Yes, it can't possibly work properly.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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 (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)
{
struct stack *temp;
}
free(temp);
} else {
printf("no more values in stack\n");
}
}

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()
{
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();
min_value();

return 0;
}

** Posted from [url]http://www.teranews.com[/url] **
• 05-01-2008, 05:50 PM
unix
Re: stack, pop, push and min in o(1)
On Wed, 23 Apr 2008 22:27:29 -0700, Rahul wrote:
[color=blue]
> On Apr 23, 11:35 pm, James Antill <james-netn...@and.org> wrote:[color=green]
>> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:[color=darkred]
>> > On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:
>> >> On Apr 22, 2:05 pm, Rahul <sam_...@yahoo.co.in> wrote:
>> >> Ok , i have found a solution and it is working fine.[/color]
>>
>> Alas. no. Try:
>>
>> push(3); push(4); pop(); min();
>>[/color]
> struct stack *head = NULL;
>
> 3 PUSHED
> 4 PUSHED
> POPED 4
> minimum value is 3[/color]

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 non-end
(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 non-unique numbers you have to deal with:

min_value();