LIFO vs FIFO
LIFO stands for Last In, First Out. As in, the Last item put Into the stack is the First item taken out of the stack.
What you described with your dishes analogy (in the first revision), is a queue or FIFO, First In, First Out.
The major difference between the two, being that the LIFO/stack pushes (inserts) and pops (removes) from the same end, and a FIFO/queue does so from opposite ends.
// Both:
Push(a)
-> [a]
Push(b)
-> [a, b]
Push(c)
-> [a, b, c]
// Stack // Queue
Pop() Pop()
-> [a, b] -> [b, c]
The stack pointer
Let's take a look at what's happening under the hood of the stack.
Here's some memory, each box is an address:
...[ ][ ][ ][ ]... char* sp;
^- Stack Pointer (SP)
And there's a stack pointer pointing at the bottom of the currently empty stack (whether the stack grows up or grows down isn't particularly relevant here so we'll ignore that, but of course in the real world, that does determine which operation adds, and which subtracts from the SP).
So let's push a, b, and c again. Graphics on the left, "high level" operation in the middle, C-ish pseudo code on the right:
...[a][ ][ ][ ]... Push('a') *sp = 'a';
^- SP
...[a][ ][ ][ ]... ++sp;
^- SP
...[a][b][ ][ ]... Push('b') *sp = 'b';
^- SP
...[a][b][ ][ ]... ++sp;
^- SP
...[a][b][c][ ]... Push('c') *sp = 'c';
^- SP
...[a][b][c][ ]... ++sp;
^- SP
As you can see, each time we push, it inserts the argument in the location the stack pointer is currently pointing, and adjusts the stack pointer to point at the next location.
Now let's pop:
...[a][b][c][ ]... Pop() --sp;
^- SP
...[a][b][c][ ]... return *sp; // returns 'c'
^- SP
...[a][b][c][ ]... Pop() --sp;
^- SP
...[a][b][c][ ]... return *sp; // returns 'b'
^- SP
Pop is the opposite of push, it adjusts the stack pointer to point at the previous location and removes the item that was there (usually to return it to whoever called pop).
You probably noticed that b and c are still in memory. I just want to assure you that those are not typos. We'll return to that shortly.
Life without a stack pointer
Let's see what happens if we don't have a stack pointer. Starting with pushing again:
...[ ][ ][ ][ ]...
...[ ][ ][ ][ ]... Push(a) ? = 'a';
Er, hmm... if we don't have a stack pointer, then we can't move something to the address it points to. Maybe we can use a pointer that points to the base instead of the top.
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
...[a][ ][ ][ ]... Push(a) *bp = 'a';
^- bp
// No stack pointer, so no need to update it.
...[b][ ][ ][ ]... Push(b) *bp = 'b';
^- bp
Uh oh. Since we can't change the fixed value of the stack's base, we just overwrote the a by pushing b to the same location.
Well, why don't we keep track of how many times we've pushed. And we'll also need to keep track of the times we've popped.
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
int count = 0;
...[a][ ][ ][ ]... Push(a) bp[count] = 'a';
^- bp
...[a][ ][ ][ ]... ++count;
^- bp
...[a][b][ ][ ]... Push(a) bp[count] = 'b';
^- bp
...[a][b][ ][ ]... ++count;
^- bp
...[a][b][ ][ ]... Pop() --count;
^- bp
...[a][b][ ][ ]... return bp[count]; //returns b
^- bp
Well it works, but it's actually pretty similar to before, except *pointer is cheaper than pointer[offset] (no extra arithmetic), not to mention it's less to type. This seem like a loss to me.
Let's try again. Instead of using the Pascal string style of finding the end of an array-based collection (tracking how many items are in the collection), let's try the C string style (scan from the beginning to the end):
...[ ][ ][ ][ ]... char* bp; // "base pointer"
^- bp bp = malloc(...);
...[ ][ ][ ][ ]... Push(a) char* top = bp;
^- bp, top
while(*top != 0) { ++top; }
...[ ][ ][ ][a]... *top = 'a';
^- bp ^- top
...[ ][ ][ ][ ]... Pop() char* top = bp;
^- bp, top
while(*top != 0) { ++top; }
...[ ][ ][ ][a]... --top;
^- bp ^- top return *top; // returns '('
You may have already guessed the problem here. Uninitialized memory is not guaranteed to be 0. So when we look for the top to place a, we end up skipping over a bunch of unused memory location that have random garbage in them. Similarly, when we scan to the top, we end up skipping well beyond the a we just pushed until we finally find another memory location that just happens to be 0, and move back and return the random garbage just before that.
That's easy enough to fix, we just have to add operations to Push and Pop to make sure the top of the stack is always updated to be marked with a 0, and we have to initialize the stack with such a terminator. Of course that also means we can't have a 0 (or whatever value we pick as a terminator) as an actually value in the stack.
On top of that, we've also changed what were O(1) operations into O(n) operations.
TL;DR
The stack pointer keeps track of the top of the stack, where all of the action occurs. There are ways to sort of get rid of it (bp[count] and top are essentially still the stack pointer), but they both end up being more complicated and slower than simply having the stack pointer. And not knowing where the top of the stack is means you can't use the stack.
Note: The stack pointer pointing to the "bottom" of the runtime stack in x86 might be a misconception related to the entire runtime stack being upside down. In other words, the base of the stack is placed at a high memory address, and the tip of the stack grows down into lower memory addresses. The stack pointer does point to the tip of the stack where all the action occurs, just that tip is at a lower memory address than the base of the stack.
