In c++, I need to use queues to simulate a stack . I can only use the queue oper
ID: 3571864 • Letter: I
Question
In c++, I need to use queues to simulate a stack. I can only use the queue operations empty, front, pop and push.
template<class T>
class Stack
{
public:
Stack(); // create an empty stack
bool empty(); // returns true if the stack is empty
void push(T item);// adds item to the top of stack
void pop( );// removes an item from the stack
T top( );// returns at the top of the stack
private:
queue<T> items; // holds the items you push (in reverse)
queue<T> aux; // helpful for pop and top
}
And then pushes "cat", "dog", "frog", "fish" into a Stack<string> and then pops them out (printing each one as it popped).
Explanation / Answer
#include <iostream>
#include <string>
#include <queue>
using namespace std;
template<class T>
class Stack
{
public:
Stack(); // create an empty stack
bool empty(); // returns true if the stack is empty
void push(T item);// adds item to the top of stack
void pop( );// removes an item from the stack
T top( );// returns at the top of the stack
private:
queue<T> items; // holds the items you push (in reverse)
queue<T> aux; // helpful for pop and top
};
template<class T> int size( queue<T> q ){
int size = 0;
while( !q.empty() ){
size = size + 1;
q.pop();
}
return size;
}
int main()
{
Stack<int> s;
for( int i = 1; i <= 10; i++){
s.push( i );
}
while( !s.empty() ){
cout << s.top() << endl;
s.pop();
}
//
Stack<string> s1;
s1.push( "cat" );
s1.push( "dog" );
s1.push( "frog" );
s1.push( "fish" );
cout << endl;
while( !s1.empty() ){
cout << s1.top() << endl;
s1.pop();
}
return 0;
}
template<class T> Stack<T>::Stack(){
//automatically creates empty stack, by using default constructor of queue
}
template<class T> bool Stack<T>::empty(){
return ( items.empty() && aux.empty() );
}
template<class T> void Stack<T>::push( T item ){
items.push( item );
}
template<class T> void Stack<T>::pop(){
if( empty() ){
throw("Error occured while popping value: Stack is Empty");
}
while( size(items) != 1 ){
T dequedValue = items.front();
items.pop();
aux.push( dequedValue );
}
items.pop();
//change both queues
while( !aux.empty() ){
items.push( aux.front() );
aux.pop();
}
}
template<class T> T Stack<T>::top(){
if( empty() ){
throw("Error occured while popping value: Stack is Empty");
}
while( size(items) != 1 ){
T dequedValue = items.front();
items.pop();
aux.push( dequedValue );
}
T value = items.front();
T dequedValue = items.front();
items.pop();
aux.push( dequedValue );
//change both queues
while( !aux.empty() ){
items.push( aux.front() );
aux.pop();
}
return value;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.