>>17
A stack can be implemented in any way internally, but it's usually considered a data structure which can do 2 operations:
Push object into stack
Pop object from stack
Check if stack is empty
(Optional)Peek at the top of the stack.
(Optional)Get total item count.
Pushing/popping/checking for empty/peeking should be O(1).
Aritrary access or length may or may not be implemented, and the time-space needed is unspecified.
How the stack is internally represented is usually irrelevant. Here's a few possible implementations:
1) Fixed size array which cannot grow. Items are either added from low indexes to high indexes, or from high to low. It doesn't really matter how it's done. Such approach can let you access any element in the stack at O(1).
2) Same as 1, but the implementation may re-allocate it to grow it.
3) Linked list or doubly linked list. This is rather common when using Lisp. (cons/push is push, car is peek, cdr/pop is pop, length is length, null is empty check) Arbitrary element access and length are O(n).
4) The assembly stack is a convention which usually operates by having some push/pop instructions which operate on the data in the proximity(-4,0,4(sizeof(int)) of esp (stack pointer). The operating system usually sets up a stack segment and sets the stack pointer register to it (at its end), push instruction places a value at [esp-4] and subtracts 4 from esp, pop takes the value from [esp] and writes it where it needs to be written (argument) and increments esp by 4. The stack pointer can be operated directly on, as well as any stack memory (just like any memory). Functions usually set up stack frames for local variables in the function prologue, and clean up the stack frame in the function epilogue. During a functions execution, register values that need to be saved may be staved on the stack and popped when they're needed, or accessed directly on the stack. Doing a function call will push the address of where to return (after the call) on the stack and jump to the function address. A return instruction would pop a value from the stack into the instruction pointer, thus returning to before the function call. Accessing local variables or arguments is done by looking them in the stack directly (you usually have a base stack pointer register which is set at the beginning of the function allowing you to index appropriately, but such a stack pointer is not absolutely needed and a compiler (or human) can just address the stack directly through relative offsets into the current stack pointer. Having a base pointer just helps in keeping such offsets fixed as opposed to varying (the stack pointer usually varies)).
These are intended usages, but nothing says you can't use the instructions for their behaviour if you need to. The OS may grow the stack if it reaches its limits. This is usually done by reserving the area under the stack and setting special page protection bits that would cause the OS (usermode or kernel mode) to allocate a few more stack pages under the current stack. This can continue until a certain amount has been hit, and once it hits that, a stack overflow exception would be signaled. (I mostly described x86 / Win32 stack here, but it's true for a variety of architectures, with some differences).
The CPU stack is more specialized as you can see, and while you can use it as a normal stack as well, it's usually used for doing interprocedural control-flow, accessing arguments and local variables. I've used the CPU stack as a normal data structure on a few ocasions, but I do consider such use to be abuse(incorrect use can and will cause crashes and if you're setting esp to your memory, you won't be able to access the normal callstack until you're done), altough not of the 'very wrong' kind.