Skip to content

Files

Latest commit

2353bcf · May 8, 2022

History

History

Stack

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Feb 19, 2022
Feb 2, 2022
Feb 3, 2022
Feb 10, 2022
May 8, 2022
Feb 27, 2022
Feb 27, 2022
Feb 2, 2022
Feb 19, 2022
Feb 22, 2022
Feb 19, 2022
Mar 10, 2022
Mar 10, 2022
Feb 20, 2022
Feb 4, 2022

readme.md

Stack

  • is a linear DS that works like a box, i.e one end is closed
  • insertion operation is called push operation
  • removal is called pop
  • follows Last in first out order (LIFO)

Operations on stack

  • isEmpty() or empty(): return true if stack is empty, else false
  • push(x): inserts an item to top of stack
  • pop(): removes an item from the top
  • peak() or top(): returns the top item
  • size(): returns size of stack

Corner conditions on stack

  • underflow: when pop() or peek() function is called on empty stack
  • overflow: when push called on a full stack

Implementation

Applications of stack DS

  • function calls
  • checking for balanced parentheses
  • reversing items
  • infix to prefix/postfix conversion
  • evaluation of postfix/prefix
  • stock span problem and it's variations
  • undo/redo cmd
    • since stack follows LIFO, whatever was done last, has to be undone
    • and whatever was undone last has to be re-do
  • forward/backward in web-browsers

Problems on Stack DS

sort

sort

operator | associativity    ^   
^ (power)| R to L           |   precedence
*, /     | L to R           |
+, -     | L to R           |

if there are two operators 
and you need to decide which operator to evaluate first
you look at precedence table
but if two operators have same precedence
then look at associativity

Design questions on stack

Intuition for stack problems

  • Usually used for optimising your O(N^2) idea with a tradeoff for space
  • when you need to play with greater/smaller indices
  • keeping a track of certain kind (next greater/prev greater) of elements