Complete Guide To Stacks

Stack is a linear data structure that follows LIFO (Last In, First Out) or FILO (First In, Last Out) principle. It is an abstract data type of predefined capacity in which elements can be removed and added in a specific order.

Insertion and deletion happen at the same end in stack data structure.

Visualise stack as a pile of plates in a restaurant.
Only the topmost plate is accessible.
To access any other plate, the plates on top of that plate need to be removed first.
The plate at the bottom of the pile can only be removed at the last after all plates on top of it have been removed.

Array Implementation of Stacks

Array can be used to implement stack data structure. Only one element of a stack can be accessed at a time. This element is located at the index top.

class Stack{
    int arr[50]
    int size
    int top

Array can be of any datatype.
Constructor to initialize size and top :

        Stack(int n)
        size = n
        top = -1 //denotes that stack is empty

Operations on Stacks

Push Operation

Push operation adds an item in the stack. If the stack is full, then it is said to Overflow .
When a new element is inserted on top, the value of top increases by 1

  1. Check if the stack is full before insertion.
  2. If it is full, then display error and exit.
  3. If the stack is not full, then increment the index on adding an element.

3 is added to the stack after push operation


void push()
  if(top == size-1)// Check if the index is beyond the stack size  
   print(”Stack Overflow")
   top=top+1//Increment the index on adding an element
   s[top]=item// Add the element into the stack (array) as pointed by the index }

Pop Operation

Pop operation removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

  1. Check if the stack index is beyond the initial index
  2. Return a value -1 if the stack is empty
  3. If the stack is not empty, return the topmost element

12 is removed from the top of the stack by performing pop operation


//operation returns the removed element
int pop()
    if(top== -1) //Check if the stack index is beyond the initial index 
    print(”Empty Stack")  
    return -1 //Return a value -1 if the stack is empty 
return s[top--] // Return the topmost element


Returns true if stack is empty, else false.

   bool isEmpty()
        return true// stack empty
        return false

Top or peek

Returns top element of stack.

int top()
    if (top==-1)
        print( "Stack is empty!")
        return -1
        return arr[top]

Time Complexities


Time Complexity