implementing the STACK & QUEUE ADT using a Singly Linked

The programming assignment is built on implementing the STACK & QUEUE ADT using a Singly LinkedList.Use the LLTemplate provided along with this project as a starting point.

C++ code to do the following:

Implementing a Print Queue using two Stacks (which are in turn implemented as a Single Linked List). CS210
Fall 2023
CS210 FALL 2023
Programming Assignment 2
Points Possible: 100

The programming assignment is built on implementing the STACK & QUEUE ADT using a Singly Linked
List.

Use the LLTemplate provided along with this project as a starting point.

Author original C++ code to do the following:
Implementing a Print Queue using two Stacks (which are in turn implemented as a Single Linked List).
Class Descriptions & Constraints :
Constraints:
•
•
•
•
•
•
Container classes must not be datatype dependent. Maintain the integrity of the template.
All Classes must have a constructor that accepts arguments to initialize variables. You may
overload constructors.
All classes must have a valid destructor.
Mandatory variables must be added to each class. Additional variables may be declared.
Mandatory method for every class is void print(). Additional methods may be defined.
Do not change the names or data types of classes, variables or methods given below.
1. The Data class:
Name : PrintItem
This class will contain the details of the item to be printed.
Mandatory Variables:
string fileName
float fileSize
2. The Node : (Uses Template)
Name: Node
This class is the node for the linked list.
Mandatory variables:
1
CS210
Fall 2023
T* data;
Node* nextNode;
3. The Stack Container : (Uses Template)
Name: LLStack
This class IMPLEMENTS Stack ADT methods. Stack is implemented using Singly Linked List.
Mandatory variables :
Node* top
int stackSize
const int SMAXITEMS
Mandatory Methods:
bool IsFull ()
bool IsEmpty()
void push( T* item )
void pop()
T* peek();
4. The Implementation : (Uses Template)
Name: StackQ
This class IMPLEMENTS the Queue ADT Methods.
The Queue is implemented using 2 LLStack objects. The underlying data structure is a combination of
push and pop methods over the two stack objects.
Mandatory variables:
LLStack* enQStack
LLStack* deQStack
int queueSize
const int QMAXITEMS
Mandatory Methods:
bool IsFull()
2
CS210
Fall 2023
bool IsEmpty()
void enqueue( T* item )
void dequeue()
T* peek();
Implementation Strategy:
As you can notice, there are two Stacks (enQStack and deQStack) declared as member variables in the
StackQ class. You need to use these two Stacks for implementing the functionalities of a queue.
How to perform deQ() – the dequeue method
• pop the topmost element from the deQStack.
• If the deQStack is empty, pop all the elements from the enQStack and push them
one by one into the deQStack then pop from deQStack to perform deQ().
How to perform enQ() – the enqueue method
• Add the new node to the top of the enQStack.
• Empty condition for the enQStack is only to maintain the top reference.
main method:
Create an object of the StackQ class to demonstrate all the functions of the
Queue implemented as two stacks.
Display a Menu (like PA1) to perform the following options:
a. Add Item to print queue
b. Delete from print queue
c. Peek from the print queue
d. Display the print queue
e. Display print queue size
f. Display enQStack and deQStack
g. Exit
3
CS210
Fall 2023
Constraints:
Do not change the menu or the order of the menu.
The queue may be pre-populated by you, but the user must still have the option to add and delete items
from the queue.
The menu loops infinitely till the user chooses to exit.
Error Handling:
Handle the following errors:
1. If user enters an option from the menu that is not valid, display error to the User and repeat the
menu.
2. Show appropriate error messages for underflow and overflow conditions of the queue
3. Handle null responsibly
Files to be submitted:
Submit a ZIP file (ZIP file must have your First and Last Name) containing the following:
1. C++ File
2. ReadMe.pdf
•
•
•
Author Name
Project structure: For each class in the project, list and describe the function / usage of every
variable, constructor and method.
Problem definition: For the StackQ class, draw (pictorial representation of stacks) and explain
with an example how enQ() and deQ() functions work with two stacks.
Comments are useful for understanding specific parts of the code, a deep dive. ReadMe helps
with an understanding of overall design. Comments are appreciated but not necessary.
4