"Dann Corbit" wrote in message news:...
> "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;
> }


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.


** Posted from http://www.teranews.com **