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

This is a discussion on stack, pop, push and min in o(1) - Unix ; 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. ...

+ Reply to Thread
Results 1 to 17 of 17

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

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

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

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

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

    On Apr 22, 2:05 pm, Rahul 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...

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

    On Apr 22, 2:05 pm, Rahul 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
    #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));
    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;
    }

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

    On Apr 22, 2:41 pm, Rahul wrote:
    > On Apr 22, 2:05 pm, Rahul 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.

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

    On Apr 22, 8:34*pm, vipps...@gmail.com wrote:
    > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul 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.


    I don't see the advantage of your method.

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

    On Apr 23, 7:03 am, K-mart Cashier wrote:
    > On Apr 22, 8:34 pm, vipps...@gmail.com wrote:
    >
    >
    >
    > > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul 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.

    >
    > I don't see the advantage of your method.

    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.

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

    On Apr 22, 9:31*pm, vipps...@gmail.com wrote:
    > On Apr 23, 7:03 am, K-mart Cashier wrote:
    >
    >
    >
    > > On Apr 22, 8:34 pm, vipps...@gmail.com wrote:

    >
    > > > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul 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.

    >
    > > I don't see the advantage of your method.

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


    Okay. I see the advantage of qsort beig a higher order function.

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

    On Apr 23, 8:34 am, vipps...@gmail.com wrote:
    > On Apr 22, 2:41 pm, Rahul wrote:> On Apr 22, 2:05 pm, Rahul 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.


    I didn't get the logic of your suggestion, what is nextval? could you
    explain with an example?

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

    ARRRGL. Stop the fullquotes. Everyone! Now!

    Please....

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

    On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:

    > On Apr 22, 2:41 pm, Rahul wrote:
    >> On Apr 22, 2:05 pm, Rahul 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();

    >
    > 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 -- james@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/

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

    "James Antill" wrote in message
    newsan.2008.04.23.18.35.19@and.org...
    > On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
    >
    >> On Apr 22, 2:41 pm, Rahul wrote:
    >>> On Apr 22, 2:05 pm, Rahul 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();
    >
    >>
    >> 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.


    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/...ions/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 **

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

    In article <536fa$480fa1c9$3473@news.teranews.com>,
    Dann Corbit wrote:

    > This thing:
    > http://www.pmg.lcs.mit.edu/~chandra/...ions/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).


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

    On Apr 23, 11:35 pm, James Antill wrote:
    > On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
    > > On Apr 22, 2:41 pm, Rahul wrote:
    > >> On Apr 22, 2:05 pm, Rahul 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


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

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

    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?

    Alex

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

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




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

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

    On Wed, 23 Apr 2008 22:27:29 -0700, Rahul wrote:

    > On Apr 23, 11:35 pm, James Antill wrote:
    >> On Tue, 22 Apr 2008 20:34:37 -0700, vippstar wrote:
    >> > On Apr 22, 2:41 pm, Rahul wrote:
    >> >> On Apr 22, 2:05 pm, Rahul 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.

    --
    James Antill -- james@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/

+ Reply to Thread