Stack

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means the last element added to the stack is the first one to be removed.

Primary Operations:

  • Push: Add an element to the top of the stack.
  • Pop: Remove the top element from the stack.

Secondary Methods:

  • Peek: Get the top element of the stack without removing it.
  • isEmpty: Check if the stack is empty.
  • isFull: Check if the stack is full.

Why Stack?

Stack is one of the most used data structures due to its nature of Reverse ordering. Let me explain:

Use Cases:

  • Function Call Stack: Every time a function is called, it is pushed onto the stack. When the function returns, it is popped off the stack.
    Stack: Function Call Stack Example

    Function Call Stack Example

  • Undo Functionality: In text editors, when you hit "Undo", the most recent change is reversed first. A stack keeps track of your actions so you can undo them in reverse order.

Core Idea

The main concept of a stack is the TOS (Top of the Stack). It's a variable that keeps track of the top item in the stack.
  • TOS starts at -1 because when the stack is empty, there's no top item.
  • As you add items to the stack, TOS changes to show the index of the top item.
If the stack has items, TOS will tell you where the top item is. If it's -1, it means the stack is empty.
TOS is sometimes also referred as "head"
By using TOS, we can easily implement stack using an Array.

Playground

TOS: -1
Peek: NULL
isFull: No
isEmpty: Yes

Operations

No operations yet.

Stack Operations

Push

Adds an element on top of the stack.

Algorithm:

  1. Check if the stack is full. If it is, we print an error message and return.
  2. Increase TOS by 1 and assign the data at "newly increased" TOS index.

Why ++tos and not tos++?

If we did tos++, when doing the push operation first time, we will be accidentally doing the following: which is NOT allowed and correct. so, in-order to avoid that, we first increase TOS by 1 and then assign the data at "newly increased" TOS index.

Pop

Removes the top element from the stack.

Algorithm:

  1. Check if the stack is empty. If it is, we print an error message and return.
  2. Decrease the TOS by 1 and return the data from the old TOS index.

isFull

Checks if the stack is full.

For limited size stack, if the TOS reaches the maximum index, it means the stack is full.

Why MAX - 1?

MAX is the number of elements a stack can hold and here TOS is index which starts with 0, so to account that we need to subtract 1 from MAX.

isEmpty

Checks if the stack is empty.

Fundamentally, we know that if TOS is -1, it means the stack is empty.

Peek

Returns the top element of the stack.

Condition is that if the stack is empty, TOS will be -1. So if we try to access stack[-1], we will get error. In order to prevent that we are first checking if the stack is empty.