Implementing arrays using a stack
In my programming language, there are no arrays, no lists, no pointers, no eval and no variables. All he has:
-
Regular variables, for example, you know them in most programming languages: they all have a precise name and meaning.
-
One stack. Functions provided: push (add element to start), pop (remove element from top, get value) and empty (check if empty)
My tongue is complete. (Basic arithmetic, conditional jumps, etc.). This means that it should be possible to implement some sort of list or array, right?
But I have no idea how ...
What I want to achieve: Create a function that can pop and / or modify the x element of the stack.
I could easily add this functionality to my language implementation in the interpreter, but I want to do it in my programming language.
- "Solution" one (access to element x, counting from the top of the stack)
Create a loop. Throw an item from the top stack x
once. The last element is element number x
. I end up with a shattered stack.
- Solution two:
Do the same as above, but store all popped values onto the stack second . Then you can move all items when finished. But do you know what? I don't have a second stack!
a source to share
Sounds like a homework question, as it bends random bits of computer science ...
I think you will want to use recursion for this. Let's say I have something like this.
Queue globalQueue = new Queue();
Then I could have code that got element X like this
public Object findElement(stepsToTake s) {
if (queue.empty()) {
throw new EmptyQueueYouFailException();
}
Object o = queue.pop();
if (s == 0) {
queue.push(o);
return o;
}
Object actualResult = findElement( s - 1 );
//restore this element to the stack
queue.push(o);
//return actual result
return actualResult;
}
So, chances are I made some mistakes ... didn't think it through very well. Particularly worrisome that I will reorder the stack due to the order of my calls.
Hopefully this can get you thinking in the right line to get a solution?
a source to share
If you only have one stack, this is equivalent to a pushdown automaton, which can recognize context free languages and is not Turing complete. Your proof of Turing completeness should tell you how you can implement free memory access.
In general, to prove the completeness of Turing, you have to show how your language can move from left to right on top of the ribbon (or indirectly mimic this process), which roughly corresponds to one higher-level array.
a source to share