每日一题---day6

基础题：

1、两个栈实现一个队列

思路：

栈的特点：后进先出

队列的特点：先进先出

两个栈可将一个栈用于入数据，另一个用于出数据；

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stack>
#include<cassert>
template <class T>
class myqueue
{
public:void Push(T x){s1.push(x);}void Pop()//删除头部数据{assert(!Empty());if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}}s2.pop();}T& Front()//取队首数据{assert(!Empty());if(s2.empty()){while(!s1.empty()){s2.push(s1.top());s1.pop();}}return s2.top();}T& Back() //取队尾数据{assert(!Empty());if(s1.empty()){while(!s2.empty()){s1.push(s2.top());s2.pop();}}return s1.top();}bool Empty(){return s1.empty() && s2.empty();}size_t Size(){return s1.size() + s2.size();}
private:stack<T> s1; //入数据stack<T> s2; //出数据
};

测试：
void TestQueue()
{myqueue<int> q;q.Push(1);q.Push(2);q.Pop();q.Push(3);//cout<<q.Back()<<endl;q.Push(4);q.Push(5);cout<<q.Back()<<endl;while(!q.Empty()){cout<<q.Front()<<" ";q.Pop();}cout<<endl;
}

2、两个队列实现一个栈

思路：队列的特性：在队尾入数据，队头出数据

          栈的特性：在栈顶出入数据

         注意：两个队列中总有一个队列为空

代码：

#include<queue>
#include<cassert>
template <class T>
class mystack
{
public:void Push(T x){if(!q1.empty()){q1.push(x);}else{q2.push(x);}}void Pop(){assert(!Empty());queue<T>* p1 = &q1;queue<T>* p2 = &q2;if(q1.empty()){swap(p1,p2);}while(p1->size() > 1){p2->push(p1->front());p1->pop();}p1->pop();}T Top(){assert(!Empty());queue<T>* p1 = &q1;queue<T>* p2 = &q2;if(q1.empty()){swap(p1,p2);}while(p1->size() > 1){p2->push(p1->front());p1->pop();}T top = p1->front();p2->push(top);p1->pop();return top;}size_t Size(){return s1.size() + s2.size();}bool Empty(){return q1.empty() && q2.empty();}
private:queue<T> q1;queue<T> q2;
};

测试：
void TestStack()
{mystack<int> s;s.Push(1);//s.Pop ();s.Push(2);//s.Pop ();s.Push(3);s.Push(4);s.Pop ();while(!s.Empty()){cout<<s.Top()<<" ";s.Pop();}cout<<endl;}

附加题：

替换字符串中的空格为$$$，要求时间复杂度为O(N)

例如：将“talk is cheap show me the code”替换为

“talk$$$is$$$cheap$$$show$$$me$$$the$$$code”.