48. Stack & Queue-1: (Basics)

Only For Interviews:

---------------------------------------------------------------------------------------------------------------

# Implementing Stack using Arrays-

use a fixed size array: arr[n]
& a pointer variable: idx(-1)
---------
push: (idx++) & arr[idx]=x
top:    return arr[idx]
pop:   idx--
size:   idx+1 

--------------------------------------------------------------------------------------------------------------# Implementing Queue using Arrays-

use a fixed size array

& 2 pointer variables: start(-1), end(-1)
& 2 variables: cap(n), currsize(0) 
----------------------------

 push:  if(currsize<cap)    ==> end+=1 ==>  arr[end]=x  ==> currsize++

               if start=(-1)          ==> start+=1⭐

 front:  if(currsize!=0)  ==> return arr[start]

 pop:   if(currsize>1)  ==> start+=1 & currsize--

              if(currsize==1)==> start=(-1), end=(-1)⭐

--------------------------

if (start / end goes out of bounds),
so instead of (y+1) do (y+1)%cap
which will force them to repeat in a circular array, where y can be start or end

----------------------------------------------------------------------------------------------------------------------------

Note-

Dis-advantage of using array for implementing stack & queue: we use fixed size.
So to have dynamic size we use linked list

-----------------------------------------------------------------------------------------------------------------------------

# Implementing Stack using LL-

we need 1 pointer (top) pointing initially to NULL
& 1 variable (size)

--------------

1. push(x):  create a new node => point its next to top => update top to new node => size++

2. top():       return top-->val

3. pop():      delete temp node & move top to top-->next & size--

4. size():      return size

-----------------------------------------------------------------------------------------------------------------------------

# Implementing Queue using LL-

just take another extra pointer, in the stack implementation code using LL

---------------------

1. push(x):  handle 1st node insertion along with a general node insertion

2. pop():      handle edge case of n==0 after pop, along with a general node deletion

3. front():    return (start-->val)

----------------------------------------------------------------------------------------------------------------------------

# Implementing Stack using Queue-

Push- O(n)
1. push x
2. now reverse the queue ( insert element at start of queue to the end and pop it from the start )

-----------------------------------------------------------------------------------------------------------------------------

# Implementing Queue using Stack-🔥

Method-1:

using 2 stacks [costly push]
-------------------

push- time: O(n)
move all elements from stack-1 into stack-2, then push x into st1, then move all elements from st2 to st1

-------------------------------------------------------

Method-2: [costly pop]
using 2 stacks

push: insert into s1
pop: if s2 is empty then move all elements from s1 to s2 & now pop from s2
front: if s2 is empty then move all elements from s1 to s2 & now return s2.top

-----------------------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------------------

1. Balanced parenthesis-

-------------------------------------
Stack based solution-

for checking closed bracket, we need type of last open bracket we saw
-----
if same type => move forward 
else return false
-----
hence, store all opening brackets you encounter in a stack and then whenever you see a closing bracket then compare its type with st.top()

-----------------------------------------------------------------------------------------------------------------------------

2. Implement Min Stack-

Implement a min stack which supports push, pop, top and returning min element in O(1)
---------------------
Approach-1: time:O(1)  space: O(2n)

associate each value in stack with a minimum value

---------------------------------------------------

Approach-2: space optimised
(non intuitive)⭐
------------------------

instead of storing elements directly into the stack, we will store encoded values into stack
val = (2*x-mini)

if (x>=mini) push normally
else  push encoded value & update mini
on pop, decode prev mini & update mini if required

just use 1 variable to store min till curr element in stack

---------------------------
TOP:-

if,  st.top > mini => return st.top()

if,  st.top < mini =>  return mini 

-------------------------------------------------------------

----------------------------------------------------------------------------------------------------------------------------