Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
Characteristics
- LIFO (Last In First Out)
- Think “Stack of Plates”
Applications
- Stacks associated with Recursion, Function Stacks
- Re-do, Un-do
- Back, Forward in Web Browser
- Music Playlists
- Infix to Postfix conversion
- Balancing of Symbols
- Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
- Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver
- In Graph Algorithms like Topological Sorting and Strongly Connected Components
Structure
stack.peek() -> Element?Returns the Element of the top of the stack without removing it. Returns nil if there is nothing in the stack.
stack.push(_ element: Element)Pushes the given Element onto the stack. Returns void.
stack.pop() -> Element?Removes the Element at the top of the stack. Returns the Element of the top of the stack. Returns nil if there is nothing in the stack.
stack.isEmptySets var to true if the stack is empty. Sets to false if the stack has elements.
stack.countSets var to number of elements in the stack.
Stack with Array Implementation
Advantages
- Easy to implement.
- Saves memory because no need to use pointers.
Disadvantages
- Memory for stack is not dynamically created at runtime.
Code
Stack with Linked List Implementation
Advantages
- Size is dynamic. Can grow and shrink with little cost.
Disadvantages
- Requires more space because each node stores pointer(s).
Code
