Continue to Site

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.

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

Stack question

Status
Not open for further replies.

electroRF

Member
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.
 
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.
 
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).
 
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?

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.

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

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

Great solution!

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

Your stack would be that:
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?)

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:

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:
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;
       }
    }
}
 
regarding your question

NorthGuy said:

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

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
 
your solution's time complexity is actually O(256) (which is O(1)), right?

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.

C:
typedef struct stack_t
{
    dlist_t *head; //init to NULL;
   int count; //init to 0
} stack;

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:

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

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.
 
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 :)
 
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?

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.
 
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.
 
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.
 
Status
Not open for further replies.

Latest threads

New Articles From Microcontroller Tips

Back
Top