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.

NorthGuy

Well-Known Member
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.

electroRF

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

NorthGuy

Well-Known Member
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?

electroRF

Member
Hi NorthGuy,

Great solution!

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

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

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

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;

if (!stack->count) return;

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

electroRF

Member

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

NorthGuy

Well-Known Member
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
{
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.

electroRF

Member
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

NorthGuy

Well-Known Member

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.

electroRF

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

NorthGuy

Well-Known Member
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.

electroRF

Member
Thank you NorthGuy!

Status
Not open for further replies.

Replies
13
Views
2K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
4
Views
1K
Replies
2
Views
2K