Description
Goal: This lab is split up into 2 parts, each of which will give you practice with queues, stacks, and
algorithmic design:
1. MyQueue.h: Implement a queue using two stacks
2. MyStack.h: Implement a stack using two queues
There are two files: stackT.cpp and queueT.cpp. These two files use stack and queue defined by C++
STL. Read these two files, understand how stack and queue work, then work on your own files. After
you finish implementing MyQueue.h and MyStack.h, use MyQueueTest.cpp and MyStackTest.cpp to
test that your new stack and queue implementations work properly.
You do not have to implement all functions of stack and queue STL.
http://www.cplusplus.com/reference/stack/stack/
http://www.cplusplus.com/reference/queue/queue/
Just implement push(), pop(), top() for MyStack class; push(), pop(), and front() for MyQueue class.
In this lab, you MUST use template to implement both classes.
Part 1: MyQueue
———————————————-
MyQueue implementation
Implement the stubbed out functions in the MyQueue class using two stacks. The function
specifications are shown below. The MyQueue class has 2 stacks as instance variables, which
represent the inner state of the queue. Therefore, if an object has been dequeued from the queue it
should not be in either stack. If an object is enqueued into the queue it should be present in at least
one stack.
Methods to implement (specs also in the .h file):
#include
#include
using namespace std;
template
class MyQueue {
// these two stck are instance variables
// by default, the access is private
stack first;
stack second;
public:
// return the value of the oldest member
T front(){
// please implement this method
}
// add value val to MyQueue
void push(T val){
// please implement this method
}
// remove the oldest member from MyQueue
void pop(){
// please implement this method
}
};
Use queueTest.cpp to test your implementation of the MyQueue class.
Part 2: MyStack
————————————————-
MyStack implementation
Implement the stubbed out functions in the MyStack class using two queues. The MyStack class has 2
queues as instance variables, which represent the inner state of the stack. So, like with MyQueue, if
an item is pushed onto the stack, it should be in at least one queue, and if an object is popped, it
should not be in either queue.
#include
#include
using namespace std;
template
class MyStack {
// define two instance variables
// by default, they are private
queue first;
queue second;
public:
// return the latest value of MyStack
T top(){
// please implement this method
}
// add value val to MyStack
void push(T val){
// please implement this method
}
// remove the oldest value from MyStack
void pop(){
// please implement this method
}
};
Use stackTest.cpp to test your implementation of the MyStack class.
Hint:
Both stack class and queue class from C++ STL have a method called empty(), which
checks whether the stack object/queue object is empty or not. You will need this method
when you implement MyQueue class and MyStack class.
Wrap up
————————
Jar all you files of your lab8 into lab8.jar. Submit the completed file to Canvas.
