Prev: comp.unix.programmer charter
Next: Seiko Men's Chronograph Stainless Steel Watch SNA635 - Replica Watch Fake
From: Rahul on 22 Apr 2008 05:05
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 ! ! !
From: Chris McDonald on 22 Apr 2008 05:17
Rahul <sam_cit(a)yahoo.co.in> 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.
From: Rahul on 22 Apr 2008 05:40
On Apr 22, 2:05 pm, Rahul <sam_...(a)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)?
>
> 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...
From: Rahul on 22 Apr 2008 07:41
On Apr 22, 2:05 pm, Rahul <sam_...(a)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)?
>
> Thanks in advance ! ! !

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(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;
}
From: vippstar on 22 Apr 2008 23:34
On Apr 22, 2:41 pm, Rahul <sam_...(a)yahoo.co.in> wrote:
> On Apr 22, 2:05 pm, Rahul <sam_...(a)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)?
>
> > Thanks in advance ! ! !
>
> Ok , i have found a solution and it is working fine.
<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.
 |  Next  |  Last
Pages: 1 2 3
Prev: comp.unix.programmer charter
Next: Seiko Men's Chronograph Stainless Steel Watch SNA635 - Replica Watch Fake