1. Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.
    Dismiss Notice

Stack question

Discussion in 'Mathematics and Physics' started by electroRF, Jan 17, 2014.

  1. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    I encountered this question and i'm trying to see logically how to implement it.

    Design a stack which allows pop / push / peek min/ delete min in O(1).

    please notice that when one deletes the min, the stack should know now what is the next min, in O(1) of course.

    Do you have an idea how to approach it?

    Thank you.
     
  2. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    If such thing existed, you could use it to sort something in O(n). Just push everything in, then [peek min/delete min] n times. It'll come out sorted.

    Hundreds of very clever people tried to find a sorting solution in O(n) and they all failed. If you're going to find it, it'll be very hard at best.

    So, unless you work with some special kind of data, such as 8-bit integers, I don't think the solution can be found.
     
    • Like Like x 1
  3. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    hi NorthGuy,

    Thank you, your logic seems right, and its a good explanation for why this problem hasn't a solution, i didn't see it.

    I tried thinking of how you could solve it if there were 8-bit integers, but its still too difficult to delete the min and point on the next min in O(1).

    You have an idea?

    I should say that if weren't for the 'delete min' operation, i could implement the push / pop / peek min in O(1).
     
  4. dave

    Dave New Member

    Joined:
    Jan 12, 1997
    Messages:
    -
    Likes:
    0


     
  5. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada

    Create a double-linked list for the stack. This is necessary for O(1) removal. Call it S.

    Create 256 single-linled lists. One list for every possible value of 8-bit integer. Call them L(i) where i is the 8-bit integer value.

    push x

    1. Insert x into the head of S
    2. Insert pointer to the current head of S into the head of L(x)

    pop x

    1. Set x equal to the value stored in the head element of S
    2. Remove an element from the head of S
    3. Remove an element from the head of L(x)

    peek min

    1. Scan throuhg the heads of L lists (i = 0; i++) until you find first non-empty list L(i). Set M = L(i)
    2. Follow the pointer from the head of M to the element of S (call it Smin)

    delete min

    1. Do peek min to get M and Smin
    2. Delete an element from the head of M
    3. Delete Smin from S.

    Not that easy neither. Pop operations may delete your current min, then what?
     
  6. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    Hi NorthGuy,

    Great solution!

    your solution's time complexity is actually O(256) (which is O(1)), right?

    Your stack would be that:
    Code (C):
    typedef struct dlist_t
    {
        char data; //8-bit integer
        dlist_t *next, *prev;
    };

    typedef struct stack_t
    {
        dlist_t *head; //init to NULL;
       int count; //init to 0
    } stack;
     
    Your solution implements an Array (the signly linked list stores 'next pointer' and 'stack_element address' right?)

    Code (C):
    typedef struct slist_t
    {
       dlist_t *stack_element; //points to element in stack
       slist_t *next;
    };

    slist_t *L[256];

    //init L to NULL
    for (i=0; i<256; L[i]=NULL; i++);

    POP operation would look like that:

    Code (C):

    char pop(stack_t *stack, slist_t *L[])
    {
         char value;
         dlist_t *head = stack->head;

         if (!stack->count) return;

        value = head->data;

        RemoveStackElement(stack, head);
        removeNode(L[value]);

        return value;
    }
     
    Delete Min Operation would look like that:
    Code (C):

    void deleteMin(stack_t *stack, slist_t *L[])
    {
        dlist_t stackElement;
        char minval;

        for (int i=0; i<256; i++)
        {
            if (L[i])
           {   //min element was found
               stackElement = L[i]->stackElement;
               removeStackElement(stack, stackElement);
               removeNode(L[i]);
               break;
           }
        }
    }
     
     
  7. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    regarding your question

    you can use an auxiliary stack, which for every push into the original stack, you push the current min to the auxiliary stack.

    Pops are done on both stack.

    that way the Aux. Stack's top is the min.

    It'd look like that:

    Say you push numbers in the following order: 2 -> 5 -> 6 -> 1 -> 3

    the stacks would become:

    Original Stack : 2, 5, 6, 1, 3
    Auxiliary Stack: 2, 2, 2, 1, 1
     
    • Like Like x 1
  8. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    There's no such thing as O(256). That's not really true, but to simplify, you can think of "1" here to mean a ratio of time spent to perform some operation with large n, m (or whatever) to the time spent do to the first operation.

    You do not really need the count. When head goes to NULL you know the list is empty. Instead, I would add to this the slist_t array. This way you do not need to pass it to every call.

    With lists, instead of just a pointer to the head/tail I often create a fixed "Head/Tail" element of the same type as others. Like this:

    Code (C):
    typedef struct stack_t
    {
       dlist_t head; //init prev and next to point to this head element
       // other stuff, inclusing slist arrays.
    } stack;
     
    This way, my list management routines do not need to do anything special when they encounter ends.

    E.g. to remove an element

    Code (C):
    void remove_element (dlist_t*  x) {
      x->prev->next = x->next;
      x->next->prev = x->prev;
      // free memory occupied by x
    }
    See. You do't need to check about prev and next being NULL - the head/tail pointers are valid pointers pointing to your "Head/Tail" element.

    Also, it's a good idea to shape your function in such a way that you could distingush between "stack is empty" "stack contains zero" situations.
     
    • Like Like x 1
  9. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    Hi NorthGuy,
    Thanks for your comments!

    Regarding your method of having a fixed 'head' element.

    It sounds great, however i did not quite understand it.

    When the dlist (doubly-linked list) is empty, then head is NULL or you notice it by head->prev = head->next = head?

    I mean, how do you check that the dlist is empty in your method?

    Thank you :)
     
  10. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    If you do that, you do not have a head pointer at all. Your head is not a pointer, but the structure of the same kind as you use for ordinary elements. You set both prev and next pointers to point to the head itself.

    If you want to find out if some element is the first you just check if it's prev points to the head. For the last element you check if it's next point to the head. If the head's next points to itself then the list is empty.

    Sometimes you can set the data part of the head structure so that your algorithm will not go through the end because of the data (e.g. when you do ordered insertion). This way you don't need to check pointers neither.

    Sometimes you can have separate head and tail structures with different data.
     
    • Like Like x 1
  11. 3v0

    3v0 Coop Build Coordinator Forum Supporter

    Joined:
    Jul 14, 2006
    Messages:
    9,404
    Likes:
    227
    Location:
    OKLAHOMA USA
    Chances are that if they wanted to used a linked list they would have said so.
     
  12. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    Thank you very much NorthGuy :)

    3V, if the solution requires removing an element from a series of numbers in O(1), then a doubly-linked list must be used, or a circular linked list.
     
  13. NorthGuy

    NorthGuy Well-Known Member

    Joined:
    Sep 8, 2013
    Messages:
    1,218
    Likes:
    206
    Location:
    Northern Canada
    If you are willing to sacrifice some speed (but still stay in O(1)), you can get rid of the double-list completely. Then, of course, instead of saving pointers to the stack positions, you use consecutive index of the push (1 for the first push, 2 for the second etc.). When you need to do "pop", you simply find one of the 256 small lists with the highest index stored in its head element, and pop it out.

    You can also organize small lists not as lists but as stacks (because you only need LIFO operations). This will make it close to what is intended to be the answer. This is not a solution anyway, because the original question doesn't mention any restrictions on the data type.
     
    • Like Like x 1
  14. electroRF

    electroRF Member

    Joined:
    Jun 23, 2012
    Messages:
    689
    Likes:
    9
    Location:
    Portugal
    Thank you NorthGuy!
     

Share This Page