In this lab, you will implement stacks and queues using linked lists. After completing this lab, you should:
You may work with a partner for this lab. If you choose a partner, both members must contribute to the same work. That is, you cannot simply divide the lab in half, as everyone is responsible for all the content. Instead, you should use a pair programming style. In pair programming, one person acts as a driver, who takes control of the keyboard. The other person acts as a navigator, who reviews what the driver writes and offers advice. Oftentimes, the driver is occupied with details of the problem (e.g., variables, control flow, etc.), whereas the navigator is concerned with bigger-picture problems (e.g., functions, design, interactions). This works well for problems which are simply too large to fit into one person's head. If you're unfamiliar with the concept of pair programming, you may wish to watch this video on the topic.
With pair programming, oftentimes it works best if both participants are of approximately the same skill level. Generally, if the disparity in skill is large, the end result is frustrating for both parties - it really only works when both parties operate at approximately the same speed. With this in mind, you should select someone of approximately the same skill level.
You may wih to peruse these portions of the Dale textbook: 2.1 - 2.4, 3.3 - 3.4, 4.1, 5.1.
-bash-4.2$ cd -bash-4.2$ pwd /cs/student/yourusername -bash-4.2$ cd cs24 -bash-4.2$ pwd /cs/student/yourusername/cs24 -bash-4.2$ mkdir lab5 -bash-4.2$ cd lab5 -bash-4.2$ pwd /cs/student/yourusername/cs24/lab5
Now copy over the files for this week.
They are kept in the directory: /cs/student/kyledewey/cs24/labs/5
-bash-4.2$ cp /cs/student/kyledewey/cs24/labs/5/* .
Note that there is a '.' at the end of that line. cp means copy.
/cs/student/kyledewey/cs24/labs/5/* means all of the files contained
in the directory /cs/student/kyledewey/cs24/labs/5. The '.' means to
copy from that location to the current location.
Now check to make sure the copy worked correctly:
-bash-4.2$ ls
You should see a set of files listed that will be used for this week. You will be doing a lot of little development across a large number of files, detailed below:
IntNode.* - these are completed Node classes that hold ints
IntLinkedList.* - this is a linked list using a head and a tail pointer.
It is partially completed for you. Look for the TODO words to alert you
as to what to fill in.
Stack.* - this stack class uses the IntLinkedList class for its implementation.
You are implementing the .cpp file and fill in the instance variables to the
.h file.
Queue.* - this queue class uses the IntLinkedList class for its implementation.
You are implementing the .cpp file and fill in the instance variables to the
.h file.
main.cpp - this contains all of the test cases. You need to add test cases
to more fully test everything, but a framework is set up.
tail Pointer
In all methods in IntLinkedList.cpp, you need to add the code that modifies or uses the
tail pointer (including the constructor).
Fully implement the removeTail, peekHead, and peekTail methods
in IntLinkedList.cpp.
The tail pointer's job is to always point at the last node in
the linked list. If the list is empty, it is NULL.
For each method, you can draw pictures to show where the tail pointer
should be before and after a modification.
Finally, you need to implement a destructor for IntLinkedList
in IntLinkedList.cpp that goes through and deletes all Nodes
in the linked list.
main.cpp
Now add test cases to main.cpp. You can see that I've give you one
test case. This is a very nice way to make test cases - you determine a
test case, print out the expected result, and print out the actual result.
Then it is clear when the output is wrong.
Once you have it implemented, you can compile it and run it.
The main.cpp has test cases for the IntLinkedList,
Stack, and Queue classes.
Don't worry - the test cases for the others won't work yet, but you can
still test your IntLinkedList class.
clang++ *.cpp
Stack.h
You are implementing the Stack by using an IntLinkedList
(a linked list that holds ints). In Stack.h, I
have provided the public methods. What you need to do is fill in the
private instance variables. You need two variables - one that keeps track
of how many items are in the stack and another that is a linked list.
Stack.cpp
Now you need to implement the methods specified. Look at IntLinkedList.h and
Stack.h. For each method in Stack.h, plan how you are going to implement it,
given that you want to offload as much work as possible to methods in
IntLinkedList.h.
Begin with the constructor, initializing the two variables you
declared in the class. Then implement the push method and the isEmpty method.
For full credit, push must be efficient; it cannot, for instance, require you to traverse the entire list.
Have the second partner implement the pop, peek,
and printStack methods.
For full credit, pop and peek must be efficient;
they cannot, for instance, require a traversal of the entire list.
Once you have finished, you are ready to compile.
Let's do this in two steps - first compile just the
Stack class so you can make sure you have all the syntax correct:
clang++ -c Stack.cpp
Make sure you add test cases to main.cpp to fully test the stack.
Then compile and run the whole thing! The queue is not yet implemented,
but you can still run the other parts.
clang++ *.cpp
Now you need to implement the methods specified. Look at IntLinkedList.h and
Queue.h. For each method in Queue.h, plan how you are going to implement it,
given that you want to offload as much work as possible to methods in
IntLinkedList.h.
Begin with the constructor, initializing the two variables you
declared in the class. Then implement the enqueue and
isEmpty methods.
For full credit, enqueue and isEmpty must be efficient;
they cannot, for instance, require a traversal of the entire list.
Have the other partner implement the dequeue, peek,
and printQueue methods.
For full credit, dequeue and peek must be efficient;
they cannot, for instance, require a traversal of the entire list.
Once you have finished, you are ready to compile.
Let's do this in two steps - first compile just the
Queue class so you can make sure you have all the syntax correct:
clang++ -c Queue.cpp
Make sure you add test cases to main.cpp to fully test the queue.
Then compile and run the whole thing!
clang++ *.cpp
First, fill out the required fields in the provided README.txt file.
Once you have filled this in, you may submit everything with the following command:
-bash-4.2$ turnin lab5@cs24 IntLinkedList.cpp Queue.cpp Stack.h IntLinkedList.h Queue.h main.cpp IntNode.cpp README.txt IntNode.h Stack.cpp
All content was graciously provided by Professor Diana Franklin, with slight formatting-related adaptation.