Sunday, March 4, 2012

Simulating a Queue using two Stacks

// Simulating a queue by two stacks, one for enqueue, another for dequeue
#include <iostream>
#include <stack>
#include <queue>

using std::stack;
using std::queue;
using std::cin;
using std::cout;
using std::endl;
using std::boolalpha;

template<class T>
class squeue {
public:
 T& back()
 {
  assert (!empty());
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  return _s1.top();
 }
 
 T& front()
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  return _s2.top();
 }

 void push(const T& e) //enqueue
 {
  while (!_s2.empty())
  {
   _s1.push(_s2.top());
   _s2.pop();
  }
  _s1.push(e);
 }

 void pop() //dequeue
 {
  assert (!empty());
  while (!_s1.empty())
  {
   _s2.push(_s1.top());
   _s1.pop();
  }
  _s2.pop();
 }

 size_t size() const
 {
  return _s1.size() + _s2.size();
 }
 
 bool empty() const
 {
  return size() == 0;
 }
private:
 stack<T> _s1, _s2;
};

int main()
{ 
 squeue<int> sq;
 queue<int> q; // the control
 
 // push, back
 for (size_t i=0; i<5; i++)
 {
  sq.push(i); q.push(i);
  cout << sq.back() << " " << q.back() << "\n";
 }
 
 // size
 cout << "\n" << sq.size() << " " << q.size() << "\n\n";
 
 // front, pop
 for (size_t i=0; i<5; i++)
 {
  cout << sq.front() << " " << q.front() << "\n";
  sq.pop(); q.pop();
 }
 
 // empty
 cout << boolalpha << "\n" << sq.empty() << " " << q.empty() << endl;
 
 return 0;
}

No comments:

Post a Comment

(Coding && Eating) || Sleeping