Menu Close

Stack data structure

Stack:

  • Stack is a linear data structure.
  • Stack is an ordered list of similar data type.
  • Stack in which elements follow a specific order and operations will be performed.
  • Stack follows LIFO(Last In First Out).
  • Elements will be added from the end called TOP of stack and removes from the same end.

Stack ADT: Abstract Data Type specifies the operations can be performed on Stack

  1. Push: Push an element on to the Stack. Returns “Overflow” if stack is full.
  2. Pop: Deletes an item from Stack. Returns “Underflow” if Stack is empty.
  3. Peek: Returns top element of stack but not removes.       
  4. isEmpty: Returns true if stack is empty, else false
  5. isFull: Returns true if stack is full, else false

Stack workflow:

  • A pointer called TOP is used to keep track of the top element in the stack.
  • The initial value of TOP is -1 so that the stack is empty if TOP == -1.
  • We increase the value of TOP and place the new element in the position pointed to by TOP on PUSH.
  • TOP value modified by -1 on POP and returns the item which is deleted.
  • Before push, we need to test if the Stack is Full or Not
  • Before pop, we need to test if the Stack is Empty or Not

Stack operations:

  • ‘top’ of stack represents the top element.
  • While removing the elements from stack, top value decreases.

Applications of stack:

  1. Function recursion.
  2. Finding the Binary value of Decimal value.
  3. Infix to Post fix or Prefix conversion
  4. Forward and backward feature in web browsers
  5. Tower of Hanoi problem
  6. Tree traversals
  7. Backtracking
  8. DFS algorithm of Graph

Stack can be implemented in 2 ways:

  • Using arrays
  • Using linked lists