Linear list.
One end is called top.
Other end is called bottom.
Additions to and removals from the top end only.
Stack Of Cups
bottom top C A B D E F Remove a cup from new stack.
A stack is a LIFO list. bottom top C A B D E Add a cup to the stack.
Picture is really a stack of cups and saucers.
LIFO = last in first out. The first cup that is removed from a stack of cups is the
Last one that was added to the stack.
Other examples of LIFO lists in real life: stack of trays in a cafeteria; paper stack in a printer or copy machine; newspaper stack at a news stand.
The Abstract data type of Stack
Choice of method names is the same as used in Java’s class java.util.Stack. Notice the difference in names of the method to check if an instance is empty—isEmpty for linear lists and empty for a stack.
Parentheses Matching
(((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
Output pairs (u,v) such that the left parenthesis at position 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 parenthesis
Parentheses 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 stack
0 1 (2,6) (1,13) (15,19) (21,25) (27,31) (0,32) and so on (((a+b)*c+d-e)/(f+g)-(h+j)*(k-l))/(m-n)
Class Stack
Class Stack – cont.
Class Stack – cont.
Towers Of Hanoi
A B C 1 2 3 4 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 one
Could use animation of towers of hanoi from animations page on Web site.
Also known as Towers of Brahma.
According to legend, on the day of creation Buddhist monks began the task of moving disks from tower A to tower C. When they get done, the world will come to an end.
Comments