用栈实现队列-用队列实现栈

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

补充：软件开发 , C++ ,