# Stack question

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

1. ### electroRFMember

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. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
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 x 1
3. ### electroRFMember

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

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

5. ### NorthGuyWell-Known Member

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

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

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?

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

typedef struct stack_t
{
int count; //init to 0
} stack;

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;

if (!stack->count) return;

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

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

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 x 1
8. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
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 x 1
9. ### electroRFMember

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

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

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

Thank you

10. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
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 x 1
11. ### 3v0Coop Build CoordinatorForum 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. ### electroRFMember

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. ### NorthGuyWell-Known Member

Joined:
Sep 8, 2013
Messages:
1,218
Likes:
206
Location:
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 x 1
14. ### electroRFMember

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