栈的特点：FILO(First In Last Out)
仅能从栈顶插入，删除元素。
最基本的接口包括push() —— 从栈顶压入元素 ,pop()——从栈顶弹出元素
队列的特点：FIFO(First In First Out)
仅能从队头删除元素，从队尾插入元素。
最基本的接口包括enque()——从队尾插入元素, deque()——从队头删除元素
1.用两个栈实现队列
思路：
新入队列的元素压入stack1中，当元素出队列时，若stack2为空，则将stack1的全部元素依次弹出，压入stack2中，这样stack2的栈顶元素即为队头元素。
[cpp]
template
class MyQueue
{
public:
T front();
T back();
void enque(const T& ele);
void deque();
private:
void move(std::stack& from, std::stack& to);
private:
std::stack stack1;
std::stack stack2;
};
template
void MyQueue::move(std::stack& from, std::stack& to)
{
if (to.empty()) {
while (!from.empty()) {
to.push(from.top());
from.pop();
}
}
}
template
T MyQueue::front()
{
T ele;
move(stack1, stack2);
if (!stack2.empty()) {
ele = stack2.top();
}
return ele;
}
template
T MyQueue::back()
{
T ele;
move(stack2, stack1);
if (!stack1.empty()) {
ele = stack1.top();
}
return ele;
}
template
void MyQueue::enque(const T& ele)
{
stack1.push(ele);
}
template
void MyQueue::deque()
{
move(stack1, stack2);
if (!stack2.empty()) {
stack2.pop();
}
}
2.用两个队列实现栈
思路：
新元素入栈时，若两个队列都为空，向任意一个队列队尾插入元素，否则向其中一个非空队列插入元素。栈弹出元素时，将非空队列的元素依次删除，
插入另一个空队列，只留下队尾元素(此即栈顶元素)，弹出栈顶即从队列中删除此元素。
[cpp]
template
class MyStack
{
public:
T top();
void push(const T& ele);
void pop();
private:
std::queue queue1;
std::queue queue2;
};
template
T MyStack::top()
{
T ele;
if (queue1.empty() && !queue2.empty()) {
ele = queue2.back();
}
else if (!queue1.empty() && queue2.empty()) {
ele = queue1.back();
}
return ele;
}
template
void MyStack::push(const T& ele)
{
if (queue1.empty())
{
queue2.push(ele);
}
else if (queue2.empty())
{
queue1.push(ele);
}
}
template
void MyStack::pop()
{
if (queue1.empty())
{
while(queue2.size() > 1)
{
queue1.push(queue2.front());
queue2.pop();
}
if (!queue2.empty())
{
queue2.pop();
}
}
else if (queue2.empty())
{ www.2cto.com
while(queue1.size() > 1)
{
queue2.push(queue1.front());
queue1.pop();
}
if (!queue1.empty())
{
queue1.pop();
}
}
}