Target Language: Whatever you want, to be honest, but it's probably harder in C (don't use anything beyond POSIX/Win32/whatever).
Normally, you can use an array or a linked list or something to implement a stack. In a linked list, each "push" onto the stack is just making the new linked list node, but at the beginning of the list. For example, if you push 1, 2, 3, you have:
If you pop from the stack, it just removes the head node and moves the head to the second node, like this:
This is kind of straightforward, however. We do not want things to be straightforward.
Functions in and of themselves are pushed onto a stack when called, and when the function returns, the function is poppsed off the stack (I think this is a naïve explanation, the stack pointer is subtracted from to push onto the stack (because execution stack grows downwards) and the stack pointer is added to to pop the function from the stack). Either way, the implementation details of how the function stack works is not particularly important.
The idea is that functions and stacks go hand in hand, and we should try to capitalize on that in implementing a stack for fun.
Three different "weirdly implemented stack" ideas, that are all tangentially related to this idea:
Implement a stack following the following API (fake pseudocode language);
function push(fn head, void* value) -> fn;
function pop(fn head) -> (fn, void*) { return head(); }
The fun part is that head is a function that returns the new head and the new value. So push returns a function, which you would subsequently set to head. Also, pop returns a function (which you would also subsequently set to head), along with a value. Note that the pop actually just calls head, so you don't need to make a pop function, but rather just call head later.
So, some example usage:
head = null;
// Push 1, 2, 3, 5 onto stack
head = push(head, 1);
head = push(head, 2);
head = push(head, 3);
head = push(head, 5);
// Pop two values
head, popped = head();
println(popped); // Prints 5
head, popped = head():
println(popped); // Prints 3
For added challenge, try to make the head (aka pop) function modify itself during execution , and only return the value. Suppose we pushed 1, 2, 3, 5 onto the stack already:
// Pop two values
println(head()); // Prints 5
println(head()); // Prints 3
This is probably easier. Use the actual execution stack as your stack. You will probably need multithreading for this. You can use a structure or whatever to store your thread, etc. In C, something like this, maybe?
typedef struct stack_t {
pthread_t exec_stack;
// other things
} stack;
void push(stack_t* stack);
void* pop(stack_t* stack);Make sure your stack implementation does not have excessive amounts of CPU usage.