Advanced Programming - CS239
Department of Computer Science
LAB 23: EXPERIMENTING WITH STACKS AND QUEUES

Submitting – Submit your lab by the beginning of class on Tuesday.  You may work on another piece of paper or you may use this lab to produce a worksheet.  When the instructions say “draw a model of” that means that you should show all memory locations, using appropriate names and or pointers to other memory locations. 

Getting Ready: Before going any further you should:
1. Make a directory on your N: drive for this lab.
2. Setup your development environment.
3. Copy the file named IntNode.java to your Lab 16 directory on your N drive:
4. Copy the file named Pile.java to your Lab 16 directory on your N drive:
5. Copy the file named Node.java to your Lab 16 directory on your N drive:
6. Copy the file named Quack.java to your Lab 16 directory on your N drive:
7. Copy the file named QuackDriver.java to your Lab 16 directory on your N drive:

Part II: This part of the lab will help you understand references in linked data structures.
1. Draw a model of an IntNode that contains the value 5.
5	

Ø	

Note:  the reference to this node is not described.  Ok if all you had was the node.

2. Draw a model of a Node that contains a reference to a String containing "JMU". (Hint: Your answer to this question should contain more arrows/pointers than your answer to the previous question.)

Ø	

“JMU”	

	The node contains a reference to the String literal “JMU”.

Part II: This part of the lab will help you understand the creation of simple linked data
structures.
3.	Draw a model of what memory looks like after the following is executed:
Pile pile;
pile = new Pile();
Ø	

pile                   last

	
The variable, pile, refers to a Pile object.  The Pile object contains a single attribute, last, which is a pointer to an IntNode object.	

4.	
Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
pile.push(10);

	

pile                   last                    temp

10	

Ø	

	
push adds a node.  In this case, last points to this new node.  The next pointer is null.  Temp was created during the method execution and points to the new node.  It exists up until the method completes execution, then is destroyed.	

5.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
pile.push(20);

	

10	

Ø	

pile                   last             temp

20	

	
push adds another node.  push causes the last attribute in the Pile object to point to the most recently (or last) added node.  The next pointer of the new node points to the prior node.  Temp was created during the method execution and points to the new node.  It exists up until the method completes execution, then is destroyed.	

6.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
pile.push(30);
pile                   last             

	

	

10	

Ø	

20	

	

30	

temp	
Just like before, push puts the node in the position pointed to by last.  	

Part III: This part of the lab will help you understand the creation of slightly more
complicated linked data structures.
7.	Draw a model of what memory looks like after the following is executed:
Quack quack;
quack = new Quack();

Ø	

Ø	

last	

quack                    first

                                                                                         

 

	
The variable quack refers to a Quack object.  The Quack object contains two attribute, first and last, which are pointers to Node objects.	

8.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.push("I");

	

last	

quack                    first

                                                                                         

 

At the conclusion of this method execution, first and last are both pointing to the new node.  That node has a pointer to the next node which in this case is null and a pointer to the object, in this case the String literal, “I”.  Of course, temp, which points to the newly created node is destroyed as we leave the method.
“I”	

Ø	

temp	

	

9.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.push("like");

	

	

last	

quack                    first

                                                                                         

	

 

“like”	

temp	

“I”	

	

Ø	

In this example, “like”, the new node, is pointed to by temp and last, and it points to the first node, “I”.  First remains unchanged, always pointing to the first node.	

10.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.push("ducks");

	

last	

quack                    first

                                                                                         

	

 

“I”	

“like”	

“ducks”	

	

Ø	

temp	

	

	
At the conclusion of this methd, we have three Nodes, the first added is pointed to by first, the last added is pointed to by last (and temp), and the middle node is linked from the last and itself points to the first node added.	

Part IV: This part of the lab will help you understand the use of linked data structures.
11.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.pep();

“I”	

return

		

	

last	

quack                    first

                                                                                         

	

Ø	

“like”	

“ducks”	

value	

	

	
In this example, the local variable, value, holds the value of the “pipped” node and returns it to the calling program.  The first attribute of quack points now to the “like” node.  last continues to point to the “ducks” node. 	

12.	Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.pep();
“like”	

return

		

	

last	

quack                    first

                                                                                         

 

value	

“ducks”	

	

	
In this example, the local variable, value, holds the value of the “pipped” node and returns it to the calling program.  Since there is only one node remaining, first and last both point to the same node. 	

13.	 Continuing with this same example, now draw a model of what memory looks like
after the following is executed:
quack.pep();
“ducks”	

return

	Ø	

Ø	

last	

quack                    first

                                                                                         

 

value	

	
When the final node’s value is returned, last and then first become null.	

14.	Trace the execution of the main() method in the QuackDriver class. [Note: This
example uses the pip() method in the Quack class, not the pep() method.]

§Ï
ÏÏ§Ïpip:
ÏÏ§Ï
ÏÏ§ÏAlice
ÏÏ§Ïand
ÏÏ§ÏTed
ÏÏ§Ïlike
ÏÏ§ÏCarol
ÏÏ§Ïand
ÏÏ§ÏBob
ÏÏ§Ï	
In this case, I am showing only the output (which is what you would do in a trace.)  The difference between pip and pep are the order in which the nodes are extracted.  pip begins with the first node added and works through from that direction (the “first” direction) while pep works with the last node in.  NOTE:  pep behaves as a queue.  pip behaves like a stack.