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.isEmpty`

Sets var to true if the stack is empty. Sets to false if the stack has elements.

`stack.count`

Sets 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