## Stack

A **stack** is a simple data structure based on the Last In, First Out (LIFO) principle, where only the **Top** element is accessible.

Think of a stack of plates - you can only add or retrieve from the top.

When we add an item to a stack, we call that operation **push**. When you take an item off the stack, we call it **pop**.

A stack `S`

can be implemented easily with a fixed-length array. We can track which element is at the top with `S.top`

. The size of the array is the maximum size of the stack.

*Example of array-based stack implementation - From Introduction to Algorithms, Third Edition*

If we attempt to add to a stack beyond its max size, Stack Overflow error. If we try to pop from an empty stack, we get the **Stack Underflow** error.

Programming languages use a stack called a Call Stack to keep track of functions running.

A stack supports the following operations in its typical form:

Operation | Pseudocode | Description |
---|---|---|

push | `PUSH(o, s)` |
Place `o` on top of stack. |

top | `TOP(s)` |
Show the element at the top of the stack. |

pop | `POP(s)` |
Remove and return the element at the top of the stack. |

isEmpty? | `EMPTY(s)` |
Return True or False if empty. |

new empty stack | `new STACK s` |
Create a new, empty stack. |

## Recommended Reading

Introduction to Algorithms, Third Edition

**Chapter 10** covers Elementary Data Structures like a Stack or Queue.