stack, pop, push and min in o(1)
Rahul
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 ! ! !
Chris McDonald
Rahul
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...
Rahul
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;
}
vipp...@gmail.com
> 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)?
>
> > 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.
K-mart Cashier
I don't see the advantage of your method.
vipp...@gmail.com
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.
K-mart Cashier
>
> - Show quoted text -
Okay. I see the advantage of qsort beig a higher order function.
Rahul
I didn't get the logic of your suggestion, what is nextval? could you
explain with an example?
Lars Uffmann
Please....
James Antill
> On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:
>> 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.
Alas. no. Try:
push(3); push(4); pop(); min();
> <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:
[...]
> 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 -- ja...@and.org
C String APIs use too much memory? ustr: length, ref count, size and
read-only/fixed. Ave. 44% overhead over strdup(), for 0-20B strings
http://www.and.org/ustr/
Dann Corbit
news:pan.2008.04...@and.org...
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/publications/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 **
Marcel Bruinsma
Dann Corbit wrote:
> This thing:
> http://www.pmg.lcs.mit.edu/~chandra/publications/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
"Worst-case efficiency priority queues" by Gerth Stolling
Brodal (which I have not yet read).
Rahul
> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
> > On Apr 22, 2:41 pm, Rahul <sam_...@yahoo.co.in> wrote:
> >> 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.
>
> 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
>
>
> > <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:
> [...]
> > 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?
Alex Fraser
[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
Dann Corbit
> "Alex Fraser" <m...@privacy.net> wrote in message
> news:MeydnbEHZOQ...@eclipse.net.uk...
>
> #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));
> if (new_node) {
> new_node->data = data;
> new_node->ptr = NULL;
> new_node->next_minimum_value = 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)
> {
> struct stack *temp;
> printf("POPED %d\n", head->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()
> {
> printf("minimum value is %d\n", minimum_node->data);
> } else {
> printf("There aren't any nodes present in the stack\n");
> }
> }
>
> {
> while (head != NULL) {
> head = pop(head);
> }
> }
>
> int main()
> {
> struct stack *head = NULL;
> 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();
> 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();
> min_value();
>
> clear_stack(head);
>
> return 0;
> }
Actually, I am wrong. The basic idea works, and this is a marvelous idea.
In fact, someone should write a paper on it. This is an important
discovery.
Dann Corbit
I retract my retraction. In order for the idea to work, it will require an
ordered list of minimum value pointers for the entire data set, which are
not produced by the algorithm.
void dump_stack(struct stack * head)
{
int index = 0;
while (head != NULL) {
struct stack *temp;
printf("data[%d] %d\n", index++, head->data);
temp = head;
head = head->ptr;
}
}
int main()
{
struct stack *head = NULL;
dump_stack(head);
min_value();
head = push(4, NULL);
dump_stack(head);
min_value();
head = push(3, head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = push(1, head);
dump_stack(head);
min_value();
head = push(2, head);
dump_stack(head);
min_value();
head = push(-1, head);
dump_stack(head);
min_value();
head = push(0, head);
dump_stack(head);
min_value();
head = push(-10, head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = push(-2, head);
dump_stack(head);
min_value();
head = push(-3, head);
dump_stack(head);
min_value();
head = push(-1, head);
dump_stack(head);
min_value();
head = push(5, head);
dump_stack(head);
min_value();
head = push(7, head);
dump_stack(head);
min_value();
head = push(-5, head);
dump_stack(head);
min_value();
head = push(-5, head);
dump_stack(head);
min_value();
head = push(-7, head);
dump_stack(head);
min_value();
head = push(-3, head);
dump_stack(head);
min_value();
head = push(-5, head);
dump_stack(head);
min_value();
head = push(-7, head);
dump_stack(head);
min_value();
head = push(-3, head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
head = pop(head);
dump_stack(head);
min_value();
clear_stack(head);
return 0;
Dann Corbit
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 (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;
}
Alex Fraser
> "Dann Corbit" <dco...@connx.com> wrote in message news:...
>> "Dann Corbit" <dco...@connx.com> wrote in message news:...
>>> "Alex Fraser" <m...@privacy.net> wrote in message
>>> news:MeydnbEHZOQ...@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.
>> In fact, someone should write a paper on it. This is an important
>> discovery.
>
> I retract my retraction. In order for the idea to work, it will require an
> ordered list of minimum value pointers for the entire data set, which are
> not produced by the algorithm.
As it seemed to be homework I didn't want to be specific, but Rahul
appears to have lost interest now so... his code looks like a broken
implementation of the following:
View minimum_node as the top of a second stack ("the min stack"), where
following next_minimum_value walks through it.
In push(), compare the value being pushed with the top of the min stack.
If less, also push to the min stack. (Looks to be what the code is
trying to do.)
In pop(), if the top of the stack is also the top of the min stack (ie,
the pointers are equal), also pop the min stack. (Rahul's code compares
the values, so it won't work if two equal values are pushed in certain
circumstances.)
Alex
James Antill
> On Apr 23, 11:35 pm, James Antill <james-netn...@and.org> wrote:
>> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
>> > 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.
>>
>> 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 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:
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.