Question: I need help writing the Queue.cpp file I honestyl do not even know where to start Your Objective Here is a common interview question: implement
I need help writing the Queue.cpp file I honestyl do not even know where to start
Your Objective
Here is a common interview question: implement a queue using two stacks.
We will create an implementation of this interview question for Lab 5, and you will then be ready if you are asked this question on your next interview!
Given the below header file (must remain unchanged), write the Queue functions whose prototypes are provided in a file named Queue.cpp.
Test your functions inside a test file named QueueTest.cpp
Name your header file Queue.h and your source file Queue.cpp
These files should be placed inside of a C++ project in Eclipse, along with your Stack.h from Lab 3.
Queue.h
Copy and paste the below code into a file named Queue.h.
You are not permitted to alter anything about this file.
FYI: This file is not to be submitted. The instructor will test your code using the below file.
Thus, make sure your source code compiles with the below file:
#ifndef QUEUE_H_ #define QUEUE_H_ #include #include #include "Stack.h" using namespace std; class Queue { public: /**manipulation procedures*/ void dequeue(); //removes an element from the front of the queue //precondition: the queue isn't empty //postcondition: an element has been removed from the front of the queue void enqueue(string data); //adds an element to the end of the queue //postcondition: an element added to the end of the queue /**accessors*/ string getFront(); //returns the element at the front of the queue //precondition: the queue is not empty int getSize(); //returns the size of the queue bool empty(); //returns whether the queue is empty /**additional queue operations*/ void print(); //prints the elements in the queue in a programmer-specified format to stdout private: Stack s1; Stack s2; }; #endif /* QUEUE_H_ */
What to Submit
Submit your Stack.h, Queue.cpp and QueueTest.cpp files to Catalyst when you are finished.
-15 points for a missing test file
-14 points for each missing or incorrect function
No credit if your code does not compile with the above header file.
No credit if your code does not compile.
#ifndef Stack_H_
#define Stack_H_
#include
#include
#include
using namespace std;
template
class Stack
{
public:
/**constructors and destructors*/
Stack();
//initializes an empty stack
//postcondition: an empty stack
Stack(const Stack &S);
//initializes this stack to have same elements as S
//postcondition: a copy of stack
~Stack();
//frees memory allocated to the stack
//postcondition: memory for stack has been freed
/**manipulation procedures*/
void pop();
//removes an element from the top of the stack
//precondition: size != 0
//postcondition: an element has been removed from the top of the stack
void push(stackdata data);
//adds an element to the top of the stack
//postcondition: an element added to the top of the stack
/**accessors*/
bool operator==(const Stack &S) const;
//returns whether this stack is equal to another stack S
stackdata peek() const;
//returns the element at the top of the stack
//precondition: size != 0
int getSize() const;
//returns the size of the stack
bool empty() const;
//returns whether the stack is empty
/**additional operations*/
void print();
//prints the elements in the stack each element separate by a blank space to stdout
private:
struct Node {
stackdata data;
Node* link;
Node(stackdata data):data(data), link(NULL){}
};
typedef struct Node* NodePtr;
NodePtr top;
int size;
};
template
Stack::Stack()
{
top = NULL;
size = 0;
}
template
Stack::Stack(const Stack &S)
{
size = S.size;
if(S.top == NULL)
{
top = NULL;
}
else
{
top = new Node(S.top->data);
NodePtr temp = S.top;
NodePtr stemp = top; //create temporary iterator
while(temp->link != NULL)
{
temp = temp->link;
stemp->link = new Node(temp->data);
stemp = stemp->link;
}
top = stemp;
}
}
template
Stack::~Stack()
{
NodePtr temp = top;
NodePtr temp2 = top;
while(temp!=NULL)
{
temp = temp->link;
delete temp2;
temp2 = temp;
}
}
template
void Stack::pop()
{
assert(size!=0);
if(size == 1)
{
delete top;
top = NULL;
}
else
{
NodePtr N = NULL;
N = top;
top = top->link;
delete N;
}
size--;
}
template
void Stack::push(stackdata data)
{
if(size == 0)
{
NodePtr N = new Node(data);
top = N;
}
else
{
NodePtr N = new Node(data);
N->link = top;
top = N;
}
size++;
}
template
void Stack::print()
{
NodePtr temp = top;
while(temp!= NULL)
{
cout << temp->data << " ";
temp = temp->link;
}
cout << endl;
}
template
bool Stack::operator==(const Stack &S) const
{
if(size == S.size)
{
NodePtr temp1 = top;
NodePtr temp2 = S.top;
while(temp1 != NULL)
{
if(temp1->data != temp2->data)
{
return false;
}
temp1 = temp1->link;
temp2 = temp2->link;
}
return true;
}
else
{
return false;
}
}
template
stackdata Stack::peek() const
{
assert(size!=0);
return top-> data;
}
template
int Stack::getSize() const
{
return size;
}
template
bool Stack::empty() const
{
if(size==0)
{
//cout << "The list is empty!" << endl;
return true;
}
else
return false;
}
#endif /* STACK_H_ */
#ifndef QUEUE_H_
#define QUEUE_H_
#include
#include
#include "Stack.h"
using namespace std;
class Queue
{
public:
/**manipulation procedures*/
void dequeue();
//removes an element from the front of the queue
//precondition: the queue isn't empty
//postcondition: an element has been removed from the front of the queue
void enqueue(string data);
//adds an element to the end of the queue
//postcondition: an element added to the end of the queue
/**accessors*/
string getFront();
//returns the element at the front of the queue
//precondition: the queue is not empty
int getSize();
//returns the size of the queue
bool empty();
//returns whether the queue is empty
/**additional queue operations*/
void print();
//prints the elements in the queue in a programmer-specified format to stdout
private:
Stack s1;
Stack s2;
};
#endif /* QUEUE_H_ */
#include "Queue.h"
#include "Stack.h"
#include
using namespace std;
int main()
{
return 0;
}
void Queue::enqueue(string data)
{
s1.push(data);
}
void Queue::dequeue()
{
if(!s2.empty())
{
s2.pop();
}
if(!s1.empty())
{
while(!s1.empty())
{
s2.push(s1.pop());
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help