Unformatted text preview:

Stacks• Linear list.• One end is called top.• Other end is called bottom.• Additions to and removals from the top end only. Stack Of Cups• Add a cup to the stack.bottomtopCABDEF• Remove a cup from new stack.• A stack is a LIFO list.bottomtopCABDEThe Interface Stackpublic interface Stack{ public boolean empty();public Object peek();public void push(Object theObject);public Object pop();}Parentheses Matching• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)–Output pairs (u,v) such that the left parenthesis atposition u is matched with the right parenthesis at v.• (2,6) (1,13) (15,19) (21,25) (27,31) (0,32) (34,38)• (a+b))*((c+d)– (0,4)– right parenthesis at 5 has no matching left parenthesis– (8,12)– left parenthesis at 7 has no matching right parenthesisParentheses Matching• scan expression from left to right• when a left parenthesis is encountered, add its position to the stack• when a right parenthesis is encountered, remove matching position from stackExample• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)012Example• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)01(2,6) (1,13)15Example• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)01(2,6) (1,13) (15,19)21Example• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)01(2,6) (1,13) (15,19) (21,25)27Example• (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)01(2,6) (1,13) (15,19) (21,25)(27,31) (0,32)• and so onTowers Of Hanoi/BrahmaA B C1234• 64 gold disks to be moved from tower A to tower C• each tower operates as a stack• cannot place big disk on top of a smaller oneTowers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C1 2 3Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C1 23Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123Towers Of Hanoi/Brahma• 3-disk Towers Of Hanoi/BrahmaA B C123• 7 disk movesRecursive SolutionA B C1• n > 0 gold disks to be moved from A to C using B• move top n-1 disks from A to B using CRecursive SolutionA B C1• move top disk from A to CRecursive SolutionA B C1• move top n-1 disks from B to C using ARecursive SolutionA B C1• moves(n) = 0 when n = 0• moves(n) = 2*moves(n-1) + 1 = 2n-1 when n > 0Towers Of Hanoi/Brahma•moves(64) = 1.8 * 1019 (approximately)• Performing 109 moves/second, a computer would take about570 years to complete.• At 1 disk move/min, the monks will take about 3.4 * 1013 years.Chess Story• 1 grain of rice on the first square, 2 for next, 4 for next, 8 for next, and so on.• Surface area needed exceeds surface area of earth.Chess Story• 1 penny for the first square, 2 for next, 4 for next, 8 for next, and so on.• $3.6 * 1017 (federal budget ~ $2 * 1012) .Switch Box Routing1 2 3 4 5 6 7 8 9 1030 29 28 27 26 25 24 23 22 211112131415161718192040393837363534333231Routing region17Routing A 2-pin Net1 2 3 4 5 6 7 8 9 1030 29 28 27 26 25 24 23 22 2111121314151618192040393837363534333231417Routing for pins 5 through16 is confined to upper right region.Routing for pins 1-3 and 18-40 is confined to lower left region.17Routing A 2-pin Net1 2 3 4 5 6 7 8 9 1030 29 28 27 26 25 24 23 22 2111121314151618192040393837363534333231417(u,v), u<v is a 2-pin net.u is start pin.v is end pin.Examine pins in clock-wise orderbeginn-ing with pin 1.17Routing A 2-pin Net1 2 3 4 5 6 7 8 9 1030 29 28 27 26 25 24 23 22 2111121314151618192040393837363534333231417Start pin => push onto stack.End pin => start pin must be at top of stack.Method Invocation And Returnpublic voida(){ …; b(); …}public void b(){ …; c(); …}public void c(){ …; d(); …}public void d(){ …; e(); …}public void e(){ …; c(); …}return address in a()return address in b()return address in c()return address in d()return address in e()return address in c()return address in d()Try-Throw-Catch•When you enter a try block, push the address of this block on a stack.• When an exception is thrown, pop the try block that is at the top of the stack (if the stack is empty, terminate).• If the popped try block has no matching catch block, go back to the preceding step.• If the popped try block has a matching catch block, execute the matching catch block.Rat In A MazeRat In A Maze• Move order is: right, down, left, up• Block positions to avoid revisit.Rat In A Maze• Move order is: right, down, left, up• Block positions to avoid revisit.Rat In A Maze• Move backward until we reach a square from which a forward move is possible.Rat In A Maze• Move down.Rat In A Maze• Move left.Rat In A Maze• Move down.Rat In A Maze• Move backward until we reach a square from which a forward move is possible.Rat In A Maze• Move backward until we reach a square from which a forward move is possible.• Move downward.Rat In A Maze• Move right.• Backtrack.Rat In A Maze• Move downward.Rat In A Maze• Move right.Rat In A Maze• Move one down and then right.Rat In A Maze• Move one up and then right.Rat In A Maze• Move down to exit and eat cheese.• Path from maze entry to current position operates as a


View Full Document

UF COP 3530 - Stacks

Download Stacks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Stacks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Stacks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?