// 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; }
Sunday, March 4, 2012
Simulating a Queue using two Stacks
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment
(Coding && Eating) || Sleeping