Stack
C++Definition
The stack is a data structure that hold objects in the order of LIFO (Last In First Out) entry. This means that the first element to be added will be the last element to exit. In its most classic form it implements following operations:
- Top : this operation returns the last element added to the stack, in some cases it can also be implemented as Peek
- Push: the operation adds an element to the last stack position
- Pop : this operation removes an element from the last stack position. In some implementations, the operation removes and returns the element that you removed
Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(n) | O(n) |
| Top | O(1) | O(1) |
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
Implementation
The stack can be implemented in two ways: through a fixed-size static vector where the index of the position of the last added element is stored (in this case the stack has a fixed capacity), or through a linked list (in this type of implementation the stack capacity is variable).
When deploying with a threaded list it is necessary to make some modifications and keep a pointer to the first position in the list so that insertion and removal maintain the complexity O(1). In the structure of the list we will add an element at the beginning and at the time of removing we also remove the element from the beginning. The difference from the queue to the stack in the implementation using a list is that the queue inserts the element in the last position and you need to keep a pointer to it.