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).
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.
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++);
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:
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.
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.
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.