栈:先进后出
队列:先进先出
首先构建队列q1,q2。
入栈:入队列q1。
出栈:将q1队列中的前n-1个元素倒入到q2中,在pop q1中的第n个元素,即为要出栈的元素,下次,则对q2操作,每次保证有一个队列为空。
栈顶:将q1中前n-1个元素倒入q2中之后,第n个元素即为栈顶。
考虑到我们取栈顶元素的便利性,我们在实现时使得栈顶等于队列头,由于栈的pop弹出栈顶元素,而队列的pop也是弹出栈顶元素,所以我们需要特别处理的是插入操作。
由于往栈中添加元素相当于往队列头添加元素,因此我们需要在两个队列中进行元素的转移,实现如下:
1.q1和q2在任何时刻至少有一个为空,即如果有元素,所有元素均在同一个队列中。
2.当有元素需要插入时,将插入的元素插入到空的队列中,并将另一非空队列的元素转移到该队列中,于是插入的元素添加到了队列头中。
代码实现如下:
#include <iostream>
#include <queue>
#include <assert.h>
using namespace std;
template <class T>
class Stack
{
public:
Stack()
:_size(0)
{}
~Stack()
{}
void Push(const T& x) //入栈
{
q1.push(x); //开始先在q1中插入
++_size;
}
void Pop() //出栈
{
assert(_size > 0); //先判断栈中是否有元素
size_t size = q1.size(); //q1中元素的个数
if (size == 0)
{
if (q2.size() == 0)
{
return;
}
size = q2.size(); //q2中元素的个数
while (size != 1) //次时需要将q2中的元素压入到q1中,在q2中留一个元素
{
T temp = q2.front(); //取q2的队头元素
q1.push(temp);
q2.pop();
--size;
}
//此时,q2中只有一个元素
q2.pop(); //真正栈中弹出的元素
}
else if (size != 0) //q1不为空
{
size_t size = q1.size(); //q1中的元素个数
while (size != 1)
{
T temp = q1.front(); //取q1的队头元素
q2.push(temp);
q1.pop();
--size;
}
//此时,q1中只有一个元素
q1.pop(); //真正栈中弹出的元素
}
--_size; //pop一次,栈中数据个数--
}
bool Empty() //判空
{
return _size ? false : true;
}
size_t Size()
{
return _size; //栈中数据的个数
}
void Print() //打印
{
size_t size = q2.size();
while (size)
{
cout << q2.front() << " ";
q2.pop();
--size;
}
size = q1.size();
while (size)
{
cout << q1.front() << " ";
q1.pop();
--size;
}
cout << endl;
}
protected:
queue<T> q1; //队列1
queue<T> q2; //队列2
size_t _size; //栈中数据的个数
};
#include "stack.h"
#include <windows.h>
void TestStack()
{
Stack<int> pp;
pp.Push(1);
pp.Push(2);
pp.Push(3);
pp.Push(4);
pp.Push(5);
pp.Push(6);
pp.Push(7);
pp.Push(8);
pp.Push(9);
pp.Push(10);
pp.Pop();
pp.Pop();
pp.Pop();
pp.Pop();
pp.Pop();
//pp.Pop();
//pp.Pop();
//pp.Pop();
pp.Print();
cout << pp.Empty() << endl;
cout << pp.Size() << endl;
}
int main()
{
TestStack();
system("pause");
return 0;
}