48. Stack & queue-1: implementation

ONLY FOR INTERVIEWS:

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

1. Implementing stack using arrays-

all ops take O(1)

we need fixed size array & 1 variable: topidx(-1)


push: topidx++ ==> arr[topidx]=x
pop:  topidx--
size:  topidx +1 
top: return st[topidx]

---------------------------------------------------------------------------------------------------------------------------                                                2. Implementing Queue using arrays-🔥
all ops will take O(1)
alot of edge cases

we need a fixed size array & 4 variables: start(-1), end(-1), 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 or 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- disadvantage of using array for implementing stack and queue is we use fixed size , so to have dynamic size we use linked list
-----------------------------------------------------------------------------------------------------------------------------

3. Implementing stack using LL-

all ops will take O(1)
we need 1 pointer (top) pointing initially to NULL & 1 variable (size)

1. push(x):  create a new node for x ==> point node's next to top wala node ==> update top to new node ==> size++
2. top(): return top->val
3. pop(): (temp=top) ==> (top=top->next) ==> (free temp) ==> size--
4. size(): return size
--------------------------------------------------------------------------------------------------------------------------

4. Implementing queue using LL-

all ops will take O(1)
we will use 2 pointers (start, end - both initially pointing to NULL) & 1 variable (size)

1. push(x):  create new node temp => (end->next = temp) => (end = temp) => size++
                    if first node is inserted--> point start & end both to this node
2. pop(): temp = start => (start=start->next) => free temp ==> size--
                if start points to null/ queue becomes empty after pop => point end to null, as well
3. top(): return (start-->val)
----------------------------------------------------------------------------------------------------------------------------

5. Implementing stack using queue-

simple- reverse the queue after each push

like q,front ko push kro queue mein aur fir top ko pop krdo toh jisko upar chadaya vo niche se nikal jayega

here push will take O(n), rest ops will take O(1)
-----------------------------------------------------------------------------------------------------------------------------

6. Implementing queue using stack-🔥

(non intuitive)
we will use 2 stacks
push: firstly move all st1 elements into st2, then push x into st1, then move all elements from st2 to st1
 
----------------------------------------------------------------------------------------------------------------------------
Approach-2 of 
implementing queue using stack:

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

7. Balanced parenthesis-


for checking closed bracket, we just need ki last open bracket konsa tha, agar same type ka tha toh theek aage badho nhi toh false return krdo
So, we have to preserve opening brackets & want which was last opening bracket we encountered
-----------------------------------------------------------------------------------------------------------------------------

8. Min Stack-

Approach-1: time=O(1) , space=O(2N)

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

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

PUSH:
if(x<mini), then instead of st.push(x), we push: ((2*curr)-pmini) into stack & set mini = x
POP:
along with st.pop() , if reqd: also update mini back to pmini using formula
TOP: 
if,  st.top > mini => return st.top()
if, st.top < mini =>  return mini 
-------------------------------------------------------------

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

Comments

Post a Comment

Popular posts from this blog

18. greedy algorithm

Image
assign greedily  like sabse kam distribute kro starting mein bade number last k liye bacha k rakho we use 2 pointer here ---------------------------------------------------------------------------------------------------------------------------- if smj ni aara ki konsa stl use kru, u can even solve ques with few varibles also. ----------------------------------------------------------------------------------------------------------------------------- Shortest Job First Problem Jump game 1 Jump game 2 Job Sequencing problem N Meetings in a room Insert Intervals Min platforms Valid parenthesis Candy Fractional Knapsack ------------------------------------------------------------------------------------------------------------------------ Shortest Job First Problem- --------------------------------------------------------------------------------------------------------------------------- JUMP GAME-1 --------------------------------------------------------------------------------------...
Read more

19. strings (LB)

Image
strings are 1d character array. e.g., char ch[10]; cin>>ch; string ends with '\0' cin with string works only if till space, tab or new line is absent in input... ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------- STRING- dynamic size no null termination in built functions --------------------------------------------------- ------------------------------------------------------------------------- --------...
Read more

17. BINARY SEARCH on 2d arrrays

Image
 1.)   ROW WITH MAX 1s- given each row is sorted. BRUTE - simple 2 loops OPTIMAL - binary search lagalo to find index of 1st occurence of 1 in a row -------------------------------------------------------------------------------------------------------------- 2.) Search in 2d Matrix-(sorted rows consecutive) BRUTE - use 2 loops BETTER - check for only that row jisme target is between a[i][0] and a[i][c-1]  OPTIMAL - 2d array ko hypothetically 1d me karke binary search lagalo --------------------------------------------------------------------------------------------------------------- 3.) Search in matrix(sorted row and col but not consecutive) BETTER- use binary search for every row OPTIMAL -(time: N+M) --------------------------------------------------------------------------------------------------------------- 4.) Peak elements in matrix- BRUTE- 1.) we can do linear search and for each element compare with its 4 neighbours 2.) Or, we can find max element in matrix BET...
Read more