stacks/queues simulator
student_01
prog-011.pdf
Programming Assignment #1
Stacks / Queues Simulator
CSci 430 Fall 2018
Dates:
Assigned: Monday January 21, 2019 Due: Wednesday January 30, 2019 (before Midnight)
Objectives:
� Programming in C/C++ review.
� Introduction to using STL data types
� Review of queues, stacks and other data types.
� Introduction to class programming assignment structures.
� Introduction to class style guidelines and expectations.
Description:
The programming assignments for this class have several objectives in mind. You are required to do the programming assignments using the C/C++ lan- guage. C and C++ are widely used for system programming tasks, such as building operating systems software, and other low level computing tasks that require good performance. This �rst programming assignment also acts as a review for several topics. In this assignment you need to use a simple queue data structure to perform the assigned task. You are required to im- plement your queue using C++ standard template library (STL) data types. So we will be reviewing or introducing you to using STL library types for programming. And �nally, this assignment will introduce you to the struc- ture and format of programming assignments for this class. The assignments
1
for this class take the form of terminal based simulations. We make use of command line parameters in order to specify options and inputs. Most of the assignments after this �rst ones are implementations of simulations of various aspects of operating system functions, such as memory management or process scheduling.
In this �rst assignment, you are to implement a simple simulation that supports a stack and a queue of items being either enqueued and dequeued (onto the queue) or pushed and popped (onto the stack). You are required to use STL data structures to implement and create the stack and queue for your program. There are several tutorials and references for the C++ STL library listed in our class website. I tend to use the following site as a reference for the STL container data types:
http://www.cplusplus.com/reference/stl/
The input �le for this simulation will simply be a list of operations to perform on either a stack or a queue. For example:
----- testfile1.tst --------
enqueue 5
enqueue 7
push blooper
push rookie
dequeue
push demerits
pop
enqueue 3
enqueue 8
push showplace
enqueue 9
dequeue
pop
dequeue
push palmetto
push zebra
pop
push collapse
dequeue
dequeue
dequeue
pop
pop
2
pop
pop
pop
enqueue 2
enqueue 4
push penguins
push sleeping
exit
---------------------------
Example correct output for this set of enqueue/dequeue operations will look like the following:
Processing stack/queue simulation file: simfile-01.sim
Enque : 5
Stack :
Queue : 5
Enque : 7
Stack :
Queue : 5 7
Push : blooper
Stack : blooper
Queue : 5 7
Push : rookie
Stack : rookie blooper
Queue : 5 7
Dequeue: 5
Stack : rookie blooper
Queue : 7
Push : demerits
Stack : demerits rookie blooper
Queue : 7
Popped : demerits
3
Stack : rookie blooper
Queue : 7
Enque : 3
Stack : rookie blooper
Queue : 7 3
Enque : 8
Stack : rookie blooper
Queue : 7 3 8
Push : showplace
Stack : showplace rookie blooper
Queue : 7 3 8
Enque : 9
Stack : showplace rookie blooper
Queue : 7 3 8 9
Dequeue: 7
Stack : showplace rookie blooper
Queue : 3 8 9
Popped : showplace
Stack : rookie blooper
Queue : 3 8 9
Dequeue: 3
Stack : rookie blooper
Queue : 8 9
Push : palmetto
Stack : palmetto rookie blooper
Queue : 8 9
Push : zebra
Stack : zebra palmetto rookie blooper
Queue : 8 9
Popped : zebra
4
Stack : palmetto rookie blooper
Queue : 8 9
Push : collapse
Stack : collapse palmetto rookie blooper
Queue : 8 9
Dequeue: 8
Stack : collapse palmetto rookie blooper
Queue : 9
Dequeue: 9
Stack : collapse palmetto rookie blooper
Queue :
Dequeue request from empty queue
Stack : collapse palmetto rookie blooper
Queue :
Popped : collapse
Stack : palmetto rookie blooper
Queue :
Popped : palmetto
Stack : rookie blooper
Queue :
Popped : rookie
Stack : blooper
Queue :
Popped : blooper
Stack :
Queue :
Pop request from empty stack
Stack :
Queue :
Enque : 2
5
Stack :
Queue : 2
Enque : 4
Stack :
Queue : 2 4
Push : penguins
Stack : penguins
Queue : 2 4
Push : sleeping
Stack : sleeping penguins
Queue : 2 4
Simulation ends
The stack should be a stack of strings, able to push and pop string items onto it. And your queue should be a queue of integers. A summary of the simulation commands
� enqueue intval
� Put the indicated integer onto the back of the current queue.
� dequeue
� Remove the item from the head of the current queue and display it.
� push stringval
� Push the indicated string onto the top of the current stack.
� pop
� Pop the top string from the stack and display it.
You will note that after each simulated operation, the contents of the stack and queue are always displayed. You should always show all of the items on your stack and queue. The front of the queue should be the �rst item shown (reading from left to right), and the back item will be the last item displayed. Likewise, for the stack, the top of the stack is always the
6
�rst item shown, and the bottom of the stack is the last item. If the stack is empty then of course nothing is displayed. Also note, that if a pop or dequeue is attempted from an emtpry stack or queue, you should detect this and display an error message, but then ignore the request. Subsequent pushes or enqueues should work normally to add items to your data structures.
The C++ STL library has stack and queue containers. However, unfor- tunately, these containers do not allow you to iterate over and display all of the contents of the containers. You can use any STL container you want that you can get to work. However I would suggest you use a simple list container for both your stack and queue. The list has methods to push_front() and push_back() as well as pop_front() and pop_back(). Thus you can use these methods to implement either stack (FILO) or queue (FIFO) behavior of the items you manage in the container.
A starting template has been provided for you named p1-start.cpp. You are required to use this template for your assignment. I have given you code to open and read in the simulation commands. In addition, you will see that a single command line parameter is expected and required for the template �le. For this �rst assignment, we simply specify the name of a �le of commands to open and simulate (e.g. `sim�le-01.sim`). Future assignments might require more complex initial arguments and parameters for your simulations. We will discuss using command line arguments in class.
Also besides `sim�le-01.sim` I have provided a `sim�le-01.res` �le. You need to display your output to standard output (do not open and write output to a �le). And your output needs to exactly match the expected output given in the result �le. I partially grade your assignments by doing a di� between your output, and the expected correct output. There are also some additional simulation and result �les provided, so that you can further test your program against the expected results.
Assignment Submission and Requirements
All source �les you create for you solution (.c or .cpp/.c++ and .h header �les) should be uploaded to the MyLeo Online submission folder created for this assignment by the deadline. You should not attach any �les besides the source �les containing your C/C++ code. But you should make sure you attach all needed �les you create to your submission, so that I can compile and run your solution.
You are required to write the program in standard C/C++ programming language. You should use a relatively recent version of the C/C++ compiler
7
(C90 C++98 is �ne, or the more recent C99 C++11 will also be acceptable), and/or recent IDE that has an up to date compiler. You should only use standard C/C++ libraries, do not use Microsoft speci�c or other third-party developed external libraries. You must use the C++ standard template library containers (like the list and queue items) to implement the data structures you need.
8
