Scribd
Upload
247 views24 pages

Data Structures and Algorithms Unit-2 Notes

data structures and algo

Uploaded by

sarwath sultana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
247 views24 pages

Data Structures and Algorithms Unit-2 Notes

data structures and algo

Uploaded by

sarwath sultana
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 24
Macks | Absa Mocks lent Pipnarrie Assays Awaluabing Postki heAsions Sift b hip Comrie Quiowes — ADT Dperations on Queues Chreular, Ynowee Scanned with CamScanner A Black is om adored lat in which. imeentions fedso callecl® pris” amel © add? | amd deletions [also called © pop? and “remove? | ane made ak one end called the top. Giver a Stack 82 (doore-9 Ant)? % the bottom elements Ans is the lap element. 94 ommend ore added im the scl A> BoCo DoE to the Stack, the E ls the fish element to be duleted from tae Made | EeL4op D4 gyre Ceytop | ’ c ° *P 7 B B B y Ayia lal [2 . A A push push push — puch. pop ines the last clement imsvrtel nls a slack the past dumurk Yemovedl , 0 &ack is olto Knovon 04 w ‘Lost-In- Fine Ont” CLIFO) liek, the Stack is onply initially the “lop =- 47 the stoek ld ati 1 tions Hhm"top? prowl be the maaterunn Be of the Stack. Soe naar ede 22) ey CSE, DCET.: 3h, Scanned with CamScanner ADT Stark is objecle : & bimile oxdurod Wt with oa eae 0 . re tumetions : fox alk Stack € Stuck, Hem € element , maxStackSige € positive integer Stack CuateS(manstackSize) * = vwals on empl, Abaak, se maxinum Sige ‘6 MonSteickSize Booleom SeFinkl (stowk , max StackSize) z= Hy (nwmnbsr home im Staek == > meocPtackSize ) cet Wwe else reli False Stuck Pash (Slack item) := If (Bs Full (ctack)) Stack Fall Use wud tem Int top ofs Stack ; & tack ie ih (Stnok == Creal (maxStnchS3.) rele nt f nen qh dse vrdim Folee Ch (stack) rela es Pop ( ee =if Cote fap the clack, fe Mp og A sheateomun jie stack nnplymentadion wing, arnouy. cia ee Marke coparily [sige ob conti time ed yf i a et axing the Sige % this ntiauy os veeded - Scanned with CamScanner PROGRAM TO PERFORM STACK OPERATIONS Hinclude int pop0); void push(int); int topelementQ; void display; int top = -1,data; int stack[10]; int mainQ { push(3); push(5); push(9); push(1); push(12); push( printf("Elements in the stack are: \n"); display0; printf("\n\nTop element of the stack is : Yod\n\n" ,topelement())s data = popQ; printf("\n Element %d popped \n",data); data = pop0; print{(‘"\n Element %d popped \n",data); printf(""\n\nStack after elements being popped: \n")s display| return } int topelement0, return stack(top]; } int popO. { if(top<=-1) { printf("\n\t Could not retrieve data Stack is Empty") } else ~ otic Si Scanned with “A{.QSE, DCET, Soma. wa SIDDIQUI Asst. Professor: CamScanner return data; } 3 void push(int data) { if(top==10) { print{("Could not insert data, Stack is full.\n"); 3 else { top +4; stack[top] = datas } 3 display() int i; for(i=top; >=05 i-) printf("\n%d",staek{i)); 3 Scanned with CamScanner Queues A gue ie an eralircel liek in whi Fete das Coban end "tage oe bs [odso callect © remevals” and “ degue? | takes eo dct ode The end st ht ts dn adlocl 1s cobledl the Crean, amd that whacky old dermonta ore cluletcd i& cailled the “front?. Y demu ane Inborked. in the oder ArBCoP.E Au the pou ant be dit fom Hoe aun A AB ABC ABCD ABCDE BCDE Peary ed! cule add add ada dulele Hiner the ‘ - domnunts imaerted inlo a gpone i the fost ebmunt hemor > qpouss ane also kum a © Fixt- Tn- Foat-Ont’ (FIFO Whe. Y the Quene in empl thon initiolly front = rean=4. a the Qua ns jt thon rear wonld be the SUBIR ANA sippiQul st. Professor Scanned with CamScanner ADT Queue & 7 Objels + a fire osdad lik with gro a osse elemenle jovi = Fo all € Quent stem E element maxCueweSige © postive Ivobeges Brune Gate Cran Grmnetige) = Cxtalt an omplie whose “wadimuny Size aw oe Borkan I FullQ (qpere » manbueneSize) 22) (number of dmenis 'm gpent == marlon size) aul Tne else retwm Fodse - Quore Add Q Cqpeine oitem) == |p (4a Full Q (opnerdd) qpeme Full else ‘wrherk em ab veos of ype” j Boolean, Sa Srmpi ACopnune) = ' Caperse == Cas O(mantoesSp) yim Tome else rete Folse Clement Delete 8( p) w= if (LeEmply oGpere)) voli Saewe amd ed iil ak: fon pets md Quene Scanned with CamScanner PROGRAM TO PERFORM QUEUE OPERATIONS #include Hdefine size 5 void AddQ(int); void DelQ(); void display(); int queue{s int front = int rea int main() { AddQ(1); AddQ(2); AddQG); AddQ(4); AddQ); printf("\n\n Queue elements are: display; DelQO; DelQ0; printf("\n\n Queue after elements deleted:\n"); display; return 0; } void AddQ(int value) { if (rear = size-1) printf("\n\nQueue is Full!!\n"); else { if (front = -1) front reartt; queuerear] = value; printf("\n Element Inserted: %d\n", value); } } void DelQQ, { if (front == -1) printf("\nQueue is Empty!!\n"); else Somcana SIDDIGUT = Asst. Professor CSE, DCET... Scanned with CamScanner { printf("\nElement Deleted : %d\n", queue(front}); frontt+; if (front > rear) front = rear } 3 void display, { int i for (i= front; i<= rear; i+) printf("%d ", queuelil); } Scanned with CamScanner —7 Coroulan Queet A mote oficienle represent chon is unap around, the ond of the aera. The ansay. positions ane absamgeel as cinele, vathin than in a dbranghl- line . CTA KID TBS att SS Font (Qnitial) Frome (Addition) C Deion) The variable * pronk? points oe position Counl& Clockwise prom the locodton of the front clement ior the gpore- The “neon? corwention remains unchanged Whew the “neon” is ot Man_gueuesize - 4 sthe FE dimer & p inks position 0. To TH, 0 cinealos, gpone., rove the varitables Coen sid © reown? Lani cursanct position te the nent position (clockwise> (Frmt +) % moagpunesise | ; - To debts am varnunt , oduramet one position | dlockuise and t Old the elument:s advamee 7 one position Clockwise amd tment of en pe tea SIDDIQUI fessor Scanned with CamScanner Quene . « dhe on di betwee bintar 8 amd. Onoular, &. is thak 0 ince 9 arvarge, dele. Gegpwratelly» while Creulan amamger rte 0. circle by cormecting- the last dumunt back “te te fsck tomer + Lina ti pl i ee te amd twmove the items he : Dicalan Qs pocible isbn nebo dene ition from omg es < eudar, &- » Linear & anese mune : Daan effin thar ov Hine S 5 Applications Céroutar, Queues M Tea deadey mm * Compu conbioleel Trophic: Agra! Ayer Scanned with CamScanner PROGRAM FOR CIRCULAR QUEUE Hinclude Hdefine SIZE 5 int items[SIZE]; int front =-L, rear void enQueuc(int); int deQueue void displays t maind { enQueue(10); enQuewe(20); enQuewe(30): enQuewe(40); display ( deQuewe()s display; enQuewe(100); display 0: enQueuc($0); display); return 0; } void enQueue(int element) t if(front—-1 && rear==-1) // condition to check queue is empty items|rear]=element; 3 else if((rear+1)%SIZE==front) // condition to check queue is full printf("\n\nQueue is FULL"); else r#1)%SIZE; —_ // rear is incremented s[rear| int deQueue() { int clement; print{("\n Queue is empty !! \n"); else element; // assigning a value to the queue at the rear position. se 4g ase. DET... % SUMRANA SIDDIQUI ~ Asst. Professor el Scanned with CamScanner (front +1) % SIZES Htf("\n Deleted element > %d \n", element); n (elem print{("\n Hems >"); for (+1) % SIZE) printt("%u", items[rear]); print{("\n Front > %d ", items{front]); print{(’\n Rear -> %d \n", items[rear]); Scanned with CamScanner fvalucion of Sprasions Bn enpnussicon ontaims. oprale, (operands and parenthesis . Jhraogle + = (Ca/Co-ctd))* (e-9 xe Yhore ib a precedence ‘ that dbevrmirnss the Hd t& wabvote ie rnin with, bi precedence abe Wvalrnactecl fst Opaeskese willy Moor Precedence und on asocativila - Paserithues Oe sed to override precedence oon enpressions AFA Always walrested orm the Inmumest poremthesizzee expression jee Operas Assodativile QOL]. “Lt - be - Hight =- 4+ ; ft - - ight Jew 4- Lx Bigeor aight - be - Life ape ; mw — be Uft * 1% a il ae lt - be - mg ht BS) £67 Lut -b vght 3, [>> 2% lupe —b_ might io (se. le) lye — % right 7 Scanned with CamScanner uf aah ie H yt igh 2: might — be -life ste x= the 5 Talk be lye 2 Lt - bongs — Sualualing Post bine Sepnersion dhe i woiting onpruions sit is ix mototion is the most Common Wo ot ob ately mnt sel by compilun % wolmalc reion. Inctead. compiler We W parent hers - mototion aefpsredl ty of postfia: Yn this notation » daly opevaler, penne afta. a Operands. Inf. Postfve. G+ 3%4 A B4xt ‘ axb+s obx« 5+ (+2) «4 )24+ 7% ax ble abxe/ (Ca[Cb-c+d)) x (e-ol)xe. abe-d+/ea-Kc% OJ b-ctdxe-axc Beer | able-dextac *—- Scanned with CamScanner + to evaluate on exprenion sean yt te nighk. + Place Hat operomnds on a baek. until am operatic. appeors Remove rom tre Stacks Corruct number Operamnels fr the openalir > perform the Operation . ame place the Avsult back on the hack . * Continue thie until. the ond of the expression it reached « Now Rumeve the answer fom the lep of the stack . “ample; 431 *44~ Chaveaclin. Losumed| Stuck 7 tf D+ K FC ® Yoru BR Mw \* > Anoomple 2 | 62[S-42%4 Chonacli, Scanned Stack Contenli 6 6 62 2 / 3S 3d 2 0 me 04 >) SUaIRANA SIDDIQUI 4 a Pl Scanned with CamScanner Scanned with CamScanner PROGRAM TO EVALUATE A POSTFIX EXPRESSION Hinclude #include at stack{[20}; int top void push(int); int pop0s int main, { char exp|20]5 char * int n1.n2,n3,num3 Enter the expression %s"" exp); iffisdigit(*e)) { num = *e- 48; push(num); 3 else { nl = pops n2= pop0s switeh(*e) n3= 02/ nls break; } push(n3); os } print{("\nThe result of expression %s = %d\n\n",exp,pop(); Asst. Professor Scanned with CamScanner retuen 05 t void push(int x) stack[+-top] } int pop) return stack|top--13 Scanned with CamScanner ~ Safin tb Fecthin to produce a postpin entprussion from am infin me - Real the eapression from Litt - bo-night ~ Move the operators tm the stack, amd the operands one parsed t the ontpnt eapnusion as they arw - Thu ssdur in whiel the opercitrrs ane ordprt depends on Hh, preerdemes ice: Hae highsr. precedence oprradors ant ontpnk pest - / ~ Te Lye parunthaais whim froma im th expnution is placid Wn the Stack, but ub is wnstocked orl whim, Us right madkduong parenthesis it found . - Oto te una of the eaprurcion is Arowheel the Yemabning element. om the strecks Ow popped. ok. ty the ovtput - Acormple anc ey Choraelir Scanned Stack — Pectfix Sting SUMRANA SIDDIQUI aA st Professor ou “mpl % + 1 a b + ab * +% ab c + a be. ei - abe x+ a jie abext+d Scanned with CamScanner / ~/ $ -/ x ~¥ f brad Si wee Fostfin, SGumg abe xtd abe x+de abe x +de / abe x+de/t abe x +de/f #- nampa ZL: (a+bxe-d)/(exf) Chonack Scamnet Stack ov ( 7 C4 b (+ * (+* . (+% _ es a @ ty 5 / Ae € /C e /C a /(x 4 [Cx ) i bd yim Fostfia Shing ob ab ab abe Abcxt+ abe xt abe x+4- abe x+d- abe x+d- abe x+d-e abextd-e abex+d-ef abex+d-ef * abextd-edx/ Scanned with CamScanner PROGRAM TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION Hinclude —/* for exitQ */ Hinclude — /* for isdigit(char ) */ Hincludesstring.h> — /*for streat()*/ Adeline SIZE 100 void push(char); char pop0s int isoperator(char); void InfixToPostfix(charf],char[]); int precedenee(char); char stack[SIZE]; int top =-15 int inain() { char infixSIZE], postfix[SIZE]; __/* declare infix string and postfix string */ ‘er Infix expression print{(""Postfix Expressio puts(posttfix); return 0; } void push(char item) { tops; stack|top] = item; } char pop) / { char item = stack[top]; top--5 return(item); } } / 1 isoperator(char symbol) ” { Yi ilfeymbol == "™" i symbol == | symbol =" Symbol = "+ symbol return 1; / else / return 0; | i =". CSE, DET ‘ Scanned with CamScanner ‘SUNRANA SIDDIQUI “Asst. Professor — int precedence(char symbol) /assign precedence to operator*/ “y) /* exponent operator, highest precedence*/ ymbol == '** | symbol =='/') rn) else if(symbol == "+" || symbol /* lowest precedence */ return(1); else return(0); void InfixToPostfix(char infix_exp[], char postfix_exp[]) push(()s /* push '( onto stack */ streat(infix_exp,")"); /* add ')' to infix expression */ item=infix_expli; /* initialize before loop*/ /* run loop till end of infix expression */ push(item); else iff isdigit(item) || isalpha(item)) t postfix_exp|j /* add operand symbol to postfix expr */ jt \ 3 \ else iffisoperator(item) == 1) __/* means symbol is operator */ t x=pop()s while(isoperator(x) == 1 && precedence(x)>= precedence(item)) t postfix_expli /* so pop all higher precedence operator and */ ins \ x= pop0s J* add them to postfix expression id } \ [PUSII(X)5 tect bone mila wil erin we have popped ne esr te rw us and op rien ato push(item); /* push currentoperator symbol onto sthek */ 3 ‘\ else iffitem ==")')__/* if eurrent symbol is ')' then */ { \ x= pops nd keep poppiyg until */ while(x countered */ | { \ postfix_exp|j] =x; dhs { X= pop0s { \ Scanned with CamScanner = infix_expli}s /* go to next symbol of infix expression */ postfix_explj] ="\0';_ /* add null else puts() will print entire postfix{] array till SIZE */ 3 SUMbkANA SIDDIQUI , -Asst. Professor CSE, DCET Scanned with CamScanner

You might also like