Re: stack, pop, push and min in o(1) - Unix

This is a discussion on Re: stack, pop, push and min in o(1) - Unix ; "Dann Corbit" wrote in message news:... > "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) ...

+ Reply to Thread
Results 1 to 2 of 2

Thread: Re: stack, pop, push and min in o(1)

  1. Re: stack, pop, push and min in o(1)

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


    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.

    #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);
    }
    }

    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;
    }


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

  2. Re: stack, pop, push and min in o(1)

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

    >> 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.

    >
    > 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

+ Reply to Thread