面试题:用两个栈实现队列,用两个队列实现栈
两个栈实现一个队列:
template<class T> class CQueue { public: void Push(const T& element) { stack1.push(element); } void Pop() { if (stack2.empty()) { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } } if (stack2.empty()) { cout<<"queue is empty"<<endl; assert(false); } stack2.pop(); } bool Empty() { if (stack1.empty() && stack2.empty()) return true; else return false; } T Front() { if (!stack2.empty()) { return stack2.top(); } else { while (!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } if (stack2.empty()) { cout<<"queue is empty"<<endl; assert(false); } return stack2.top(); } } private: stack<T> stack1; stack<T> stack2; };
两个队列实现一个栈:
template<class T> class CStack { public: void Push(const T& element) { queue1.push(element); } void Pop() { if (queue1.empty()) { cout<<"stack is empty"<<endl; assert(false); } while (queue1.size() != 1) { queue2.push(queue1.front()); queue1.pop(); } queue1.pop(); while (!queue2.empty()) { queue1.push(queue2.front()); queue2.pop(); } } bool Empty() { if (queue1.empty()) return true; else return false; } T Top() { if (queue1.empty()) { cout<<"stack is empty"<<endl; assert(false); } return queue1.back(); } private: queue<T> queue1; queue<T> queue2; };