Stack and queue

CSC-391. Data Structure and Algorithm course material

1. Stack and Queue CSC 391

2. Fundamental data types. Value: collection of objects. Operations: insert , remove , iterate , test if empty. Stack and Queue Stack. Examine the item most recently added. Queue. Examine the item least recently added. LIFO = "last in first out“ FIFO = "first in first out"

3. Stack operation

4. Stack algorithm

5. Maintain pointer first to first node in a singly-linked list. Push new item before first . Pop item from first . Stack: linked-list implementation inner class private class Node { String item; Node next; }

6. Stack: linked-list implementation

7. Sta ck : PUSH()

8. Sta ck : POP()

9. Fixed-capacity stack: array implementation Use array s[] to store N items on stack. push() : add new item at s[N] . pop() : remove item from s[N-1] . Defect. Stack overflows when N exceeds capacity.

10. Fixed-capacity stack: array implementation

11. Queue : Implementation Maintain one pointer first to first node in a singly-linked list. Maintain another pointer last to last node. Dequeue from first . Enqueue after last .

12. Queue algorithm

13. Queue operation

14. Enqueue

15. Queue : Implementation

16. Application Parsing in a compiler. Undo in a word processor. Back button in a Web browser. PostScript language for printers. Implementing function calls in a compiler. Parsing code: Matching parenthesis XML (e.g., XHTML) Reverse-Polish calculators Assembly language Goal. Evaluate infix expressions.

17. Polish notation Infix notation : a + b Prefix notation : + a b Postfix notation: a b + (Reverse Polish Notation) Prefix notation was introduced by the Polish logician Lukasiewicz , and is sometimes called “Polish notation”. Postfix notation is sometimes called “reverse Polish notation” or RPN. infix postfix prefix (a + b) * c a b + c * * + a b c a + (b * c) a b c * + + a * b c Infix form : <identifier> <operator> <identifier> Postfix form : <identifier> <identifier> <operator> Prefix form : <operator> <identifier> <identifier>

18. Operator Precedence

19. Operator Precedence

20. Operator Precedence

21. Prefix operation using stack Infix to Prefix Conversion Move each operator to the left of its operands & remove the parentheses: ( ( A + B) * ( C + D ) ) ( + A B * ( C + D ) ) * + A B ( C + D ) * + A B + C D

22. Infix Stack Prefix Operation ( ( ( A + B ) * ( C - E ) ) / ( F + G ) ) ---- ---- ---- ( ( A + B ) * ( C - E ) ) / ( F + G ) ) ( ----- push ( A + B ) * ( C - E ) ) / ( F + G ) ) (( ---- push A + B ) * ( C - E ) ) / ( F + G ) ) ((( ---- push + B ) * ( C - E ) ) / ( F + G ) ) ((( A output B ) * ( C - E ) ) / ( F + G ) ) (((+ A push ) * ( C - E ) ) / ( F + G ) ) (((+ AB output * ( C - E ) ) / ( F + G ) ) (( AB+ pop ( C - E ) ) / ( F + G ) ) ((* AB+ push C - E ) ) / ( F + G ) ) ((*( AB+ push - E ) ) / ( F + G ) ) ((*( AB+C output E ) ) / ( F + G ) ) ((*(- AB+C push ) ) / ( F + G ) ) ((*(- AB+CE output Prefix operation using stack

23. Infix Stack Prefix Operation ) / ( F + G ) ) ((* AB+CE- pop / ( F + G ) ) ( AB+CE-* pop ( F + G ) ) (/ AB+CE-* push F + G ) ) (/( AB+CE-* push + G ) ) (/( AB+CE-*F output G ) ) (/(+ AB+CE-*F push )) (/(+ AB+CE-*FG output ) (/ AB+CE-*FG+ pop ---- ---- AB+CE-*FG+/ pop Prefix operation using stack

24. Postfix operation using stack Infix Stack Postfix Operation A * (B + C) – D / E ---- ---- ---- * (B + C) – D / E ---- A output (B + C) – D / E * A push B + C) – D / E *( A push + C) – D / E *( AB output C) – D / E *(+ AB push ) – D / E *(+ ABC output – D / E * ABC+ pop D / E - ABC+* pop and push / E - ABC+*D output E -/ ABC+*D push ----- -/ ABC+*DE output ----- ---- ABC+*DE/- pop The precedence of operator on the top of Stack  ‘ * ‘ is more than that of Minus. So we pop multiply

25. Postfix operation using stack

26. Convert from Infix to Prefix and Postfix (Practice) x x + y ( x + y ) - z w * (( x + y ) - z) (2 * a ) / (( a + b ) * ( a - c )) Convert from Postfix to Infix (Practice) 3 r - 1 3 r - + s t * 1 3 r - + + v w x y z * - + *

27. Parsing HTML HTML is made of nested opening tags , e.g., < some_identifier > , and matching closing tags , e.g., </ some_identifier > <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html>

28. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> Parsing HTML

29. <html> <head> <title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <head> Parsing HTML

30. <html> <head> <title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <head> <title> Parsing HTML

31. <html> <head><title> Hello </title> </head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <head> <title> Parsing HTML

32. <html> <head><title> Hello </title> </head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <head> Parsing HTML

33. <html> <head><title> Hello </title></head> <body> <p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <body> Parsing HTML

34. <html> <head><title> Hello </title></head> <body> <p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <body> <p> Parsing HTML

35. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <body> <p> < i > Parsing HTML

36. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> <body> <p> <i> Parsing HTML

37. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p> </body> </html> <html> <body> <p> Parsing HTML

38. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p> </body> </html> <html> <body> Parsing HTML

39. <html> <head><title> Hello </title></head> <body><p> This appears in the < i > browswer </ i > . </p></body> </html> <html> Parsing HTML