用两个栈实现一个队列
思路：
栈s1和栈s2，s1用来Push数据，s2用来Pop数据
入队：数据直接压入栈s1中
出队：若s2为空，则把s1中除过最后一个压入的元素全部移入s2中，然后弹出s1的栈顶元素
若s2不为空，直接弹出s2的栈顶元素
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<assert.h>
using namespace std;
template<typename T>
class Queue
{
public:
Queue()
{
//利用库里面的stack的构造函构造s1和s2
}
Queue( const Queue & que)
{
s1 = que.s1;
s2 = que.s2;
}
~Queue()
{
//利用stack类来完成s1和s2的释放
}
void Push(const T&t)
{
s1.push( t);
}
void Pop()
{
assert(s1.size() != 0 || s2.size() != 0);
if (s2.size() == 0)
{////把s1中除了栈底元素，其他全部push进s2中
while (s1.size() != 1)
{
s2.push(s1.top());
s1.pop();
}
s1.pop();
}
else
{
s2.pop();
}
}
T& Front() //读取队列的队首元素
{
assert(s1.size() != 0 || s2.size() != 0);
if (s2.size() != 0)
{
return s2.top();
}
else
{
while (s1.size() != 1)
{
s2.push(s1.top());
s1.pop();
}
return s1.top();
}
}
T& Back() //读取队列的队尾元素
{
assert(s1.size() != 0 || s2.size() != 0);
if (s1.size() != 0)
{
return s1.top();
}
else
{
while (s2.size() != 1)
{
s1.push(s2.top());
s2.pop();
}
return s2.top();
}
}
bool Empty() //判断空
{
if (s2.size() == 0 && s2.size() == 0)
{
return true ;
}
else
{
return false ;
}
}
size_t Size()
{
return s1.size() + s2.size();
}
template<typenameT>
friend ostream &operator<<(ostream& _cout, const Queue <T>&que);
private:
stack<T > s1;
stack<T > s2;
};
template<typename T>
ostream& operator<<(ostream &_cout, const Queue <T>& que)
{
Queue<T >coutque(que);
_cout << "Queue:" ;
while (coutque.s2.size() > 0)
{
_cout << coutque.s2.top() << " ";
coutque.s2.pop();
}
while (coutque.s1.size() > 0)
{
coutque.s2.push(coutque.s1.top());
coutque.s1.pop();
}
while (coutque.s2.size() > 0)
{
_cout << coutque.s2.top() << " ";
coutque.s2.pop();
}
_cout << " " ;
return _cout ;
}
void Test()
{
Queue<int > que;
que.Push(1);
que.Push(2);
que.Push(3);
que.Push(4);
que.Push(1);
que.Push(2);
que.Push(3);
que.Push(4);
cout << que << endl;
/*que.Pop();
que.Pop();
que.Pop();
cout << que << endl;*/
/*int head1=que.Front();
cout << head1<<endl;
que.Pop();
int head2 = que.Front();
cout << head2<<endl;*/
/*int tail1 = que.Back();
cout << tail1 << endl;*/
int ret=que.Size();
cout << ret << endl;
}
int main()
{
Test();
return 0;
}
声明：本站所有文章资源内容，如无特殊说明或标注，均为采集网络资源。如若本站内容侵犯了原著者的合法权益，可联系本站删除。
