You will use two stacks to implement a queue. You will implement all of the basi

Question

You will use two stacks to implement a queue. You will implement all of the basic functions of a queue container:

push: add an element onto the end of the queue (remember that a queue has a FIFO structure)

pop: remove the element at the front of the queue

front: look at the front element

back: look at the back element

size: check the queue's size

empty: check if the queue is empty

You can use the std::stack container (reference: http://www.cplusplus.com/reference/stack/stack/) in order to implement your queue. The basic idea is that you will have one stack to take in your inputs, and another stack you will use to output values. Here is the basic pseudo code for enqueuing and dequeuing an element:

Enqueue: push element onto input stack

Dequeue: if output stack is not empty, pop element from output stack. Otherwise, pop elements from input stack and push them onto output stack. Then you can pop elements output stack

You should be able to run this main code with no issues:

int main(){
    myQueue<int> q1, q2;
  
   for(int i = 0; i < 10; ++i){
       q1.push(i);
   }
   cout<< "Initial Queue:"<<endl;
   while(!q1.empty()){
       cout << q1.front() << " " ;
       q2.push(q1.front());
       q1.pop();
   }
   cout<<endl<<"Size of Q2 (Q1 Reversed): "<<q2.size()<<endl;
   cout<<"Back element of Q2: "<<q2.back()<<endl;
  
}

The output for the above main program should be:

Initial Queue:
0 1 2 3 4 5 6 7 8 9
Size of Q2 (Q1 Reversed): 10
Back element of Q2: 9

Explanation / Answer

#include <iostream>
using namespace std;
template <class T>
class myQueue{
private:
int queue[100];
int f, r;
public:
myQueue(){
f = 0;
r = 0;
}
void push(int item){
queue[r++] = item;
}
int pop(){
return queue[f++];
}
int size(){
return r - f;
}
bool empty(){
if(f == r) return true;
return false;
}
int front(){
return queue[f];
}
int back(){
return queue[r - 1];
}
void swap(myQueue q){
myQueue temp;
while(!empty()){
temp.push(front());
pop();
}
while(!q.empty()){
push(q.front());
q.pop();
}
while(!temp.empty()){
q.push(temp.front());
temp.pop();
}
}
};
int main(){
myQueue<int> q1, q2, q3;
  
for(int i = 0; i < 10; ++i){
q1.push(i);
}
for(int i = 0; i < 10; ++i){
q2.push(i);
}
cout << "Initial Queue:" << endl;
while(!q1.empty()){
cout << q1.front() << " ";
q3.push(q1.front());
q1.pop();
}
cout << endl << "Size of Q3 (Q1 Reversed): " << q3.size() << endl;
cout << "Back element of Q2: " << q2.back() << endl;  
q3.swap(q2);  
cout << endl << "Size of Q3 (after swap): " << q3.size() << endl;
cout << endl << "Size of Q2 (after swap): " << q2.size() << endl;    
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.