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.

Diagram of a Stack

A stack S can be implemented easily with a fixed-length array. We can track which element is at the top with The size of the array is the maximum size of the stack.

Stack array

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

Intro to Algorithms cover

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