Stack
< Linear List Queue >
A stack is a last-in-first-out (LIFO) data structure. This means that most recent element is the first to be removed.
It can be compared to building a tower with blocks. The topmost block is the only block that can be removed from the tower without having it collapse.
Jenga (pictured to the right) obliges players to violate this last-in-first-out principle. Players take turns to remove a block from the tower and then have to put it back on top. Hilarity ensues when gravity kicks in.
Operations
There are two operations that can be performed on a stack.
- A push operation adds a new element to the top of the stack.
- A pop operation removes the element on the top from the stack and returns it to the caller.
Additionally, sometimes a third operation called top or peek is defined. It will return the topmost element to the caller like pop does, but it doesn't remove the element from the stack.
Time complexity
Linked list implementation
| Push | Constant. Create the new element and link it to the current list head. Finally, set the list head to the new element. |
|---|---|
| Pop | Constant. Create a local copy of the first element. Then delete the first element and set the list head is set to the second element. Return the local copy of the removed element. |
| Top | Constant. Return the list head. |
Ready-to-use implementations
Here's a list of programming languages that have a built-in stack data structure.
- C++: std::stack<TYPE>
- Java: java.util.Stack<TYPE> - Documentation
< Linear List Queue >