A stack is a data structure in computer science for the storage of a varying number of elements, for which, as with an ordinary stack, the element that was added last is retrieved first. This principle is also known as LIFO (Last In First Out).
The stack’s counterpart is the queue, which works according to the FIFO (First In First Out) principle.
Data structure
The operations that can be applied to a stack are:
- push: puts the given element on the stack
- pop: takes the top element of the stack and returns it.
Other instructions, exclusive to a call stack, are:
- call: the program counter is placed on the stack and execution is continued elsewhere.
- return: pop to the program counter. This will resume the call interrupted program.
Sometimes the following are still supported:
- isempty or null: returns true if the stack is empty and can act as protection for a stack underflow.
- top (or peek): returns the top element of the stack without taking it off; can be simulated when the stack is used by one thread at a time.
A stack can be compared to a stack of boards: the last board placed on the stack is taken from it first. An even better comparison is a pile like a plate trolley, where only the top element is visible, and any rest in the interior disappears.
A stack can be implemented as a linked list, or, if size is limited, as an array, with a pointer pointing to the last stack element.
Two errors can occur if used incorrectly:
- Stack underflow: a pop operation on an empty stack. The caller should have foreseen this: it indicates a programming error.
- Stack overflow: a push operation on a full stack.
Stacks when running programs
A so-called call stack is used when calling subroutines in computer programs. The program counter, which refers to the next instruction to be executed, is one of the elements that is stored and retrieved. The stack pointer points to the top of the stack. The stack can also be used for local variables.
When calling a procedure, the following happens:
- the current parameters are put on the stack.
- the current program counter is set to it.
- the base pointer (also called frame pointer) is put on it. This base pointer is used so that one knows where the current stack frame starts.
- the stack pointer is equated with the base pointer, so they point to the same element on the stack.
- memory is freed (stack space) for the local variables. This is done by moving the stack pointer.
After performing the procedure, the following will happen:
- the stack pointer is set equal to the base pointer, so that all local variables are ‘removed’ (they are still there, but will be overwritten later).
- the base pointer will be reset to what it was before (ie the start of the stack frame from the previous procedure).
- the old value of the program counter (the return address) is taken from the stack and execution continues there.
The stack pointer is usually one of the registers of a processor. In the Intel x86 architecture, this is the (E) SP registry. Registry operations take very little time. Some microprocessors have different stack pointers.
The stack is used to store local variables and procedure parameters. A coherent block of stack data with return address, call parameters and local variables is called a frame.
Hardware stack
Modern processors are always equipped with a hardware stack, which means that part of the memory can be reserved for the stack and there are instructions for operating the stack. The hardware stack already exists on the PDP11. The traditionally widely used IBM 360 does not yet have a hardware stack.
Stack oriented programming
Many calculators use Reverse Polish Notation (RPN) which means that the calculator puts the intermediate results of a calculation on the stack. Performing an operation, such as an addition, means that the top two elements of the stack are replaced by their sum.
Microprocessors are still being manufactured with a stack-oriented instruction set, for example the ST20 from ST Microelectronics. Due to their simplicity, multiple cores can be realized per chip and this appears to outweigh the higher clock speed that is possible with a register architecture.