Algorithm --> 两个栈实现队列和两个队列实现栈

两个栈实现队列和两个队列实现栈

　　队列（queue）先进先出的线性表；栈（stack）先进后出的线性表。

两个栈实现队列

法一思路：

    s1是入栈的，s2是出栈的。

• 入队列：直接压入s1即可；
• 出队列：如果s2不为空，把s2中的栈顶元素直接弹出；否则，把s1的所有元素全部弹出压入s2中，再弹出s2的栈顶元素。

代码：

#include <stack>
#include <iostream>
#include <cassert>
using namespace std;
 
template <class T>
class Queue {
public:
    bool empty( ) const { return m_stack1.empty() && m_stack2.empty(); }
    size_t size( ) const { return m_stack1.size() + m_stack2.size(); }
    void push( const T& x );
    void pop( );
private:
    stack<T> m_stack1;
    stack<T> m_stack2;
};
 
template <class T>
void Queue<T>::push( const T& x )
{
    m_stack1.push( x );
}
 
template <class T>
void Queue<T>::pop( )
{
    // if m_stack2 is empty, and there are some elements in m_stack1, push them in m_stack2
    if( m_stack2.empty() ) {
        while( !m_stack1.empty() ) {
            T& data = m_stack1.top( );
            m_stack1.pop( );
            m_stack2.push( data );
        }
    }
    // push the element into m_stack2
    assert( !m_stack2.empty() );
    m_stack2.pop( );
}
 
int main( )
{
    Queue<int> q;
    for( int i = 1; i <= 5; ++i )
        q.push( i );
    q.pop( );
    q.push( 6 );
    q.pop( );
    q.pop( );
    q.push( 7 );
    q.pop( );
    q.pop( );
    q.pop( );
    q.pop( );
     
    return 0;
}

法二思路：

用两个栈来实现，令其中一个栈inStack专门处理入队工作，另一个栈outStack专门处理出队工作。

• 入队列：直接把元素加入到 inStack中，复杂度为O(1)；
• 出队列：因为队列是先入先出的，而栈是先入后出，所以输出应该反序。比如inStack接收到的元素顺序为1, 2, 3，栈顶元素是3，但出队希望让1先出。解决方法是把inStack里的元素放到outStack中，这样outStack接收到的元素顺序就是3, 2, 1了，栈顶元素就是我们想要的1，时间复杂度为O(N)。

总结，入队直接inStack.push(元素)，出队先判断outStack是否为空，若不为空，则直接outStack.pop()，若为空，则把inStack元素导入到outStack里，再执行outStack.pop()。

#include <stack>
#include <string>
#include <iostream>
#include <cassert>

using namespace std;

template <class T>
class YL_Queue
{
public:
       void enqueue(const T &element); //入队
       T dequeue();   //出队
       T top();   //队首元素
       bool empty() const;  //判断队列是否为空
       size_t size() const;  //队列的尺寸大小

private:
        stack<T> inStack;
        stack<T> outStack;
};

template <class T>
void YL_Queue<T>::enqueue(const T &element)
{
    inStack.push(element);
}

template <class T>
T YL_Queue<T>::dequeue()
{
    assert(!empty());

    T temp;
    if (!outStack.empty())
    {
        temp=outStack.top();
        outStack.pop();
        return temp;
    }
    else
    {
        while(!inStack.empty())
        {
            temp=inStack.top();
            inStack.pop();
            outStack.push(temp);
        }
        temp= outStack.top();
        outStack.pop();
        return temp;
    }
}

template <class T>
T YL_Queue<T>::top()
{
    assert(!empty());

    T temp;
    if (!outStack.empty())
    {
        temp=outStack.top();
        return temp;
    }
    else
    {
        while(!inStack.empty())
        {
            temp=inStack.top();
            inStack.pop();
            outStack.push(temp);
        }
        temp= outStack.top();
        return temp;
    }
}

template <class T>
bool YL_Queue<T>::empty() const
{
    return (size()==0);
}

template <class T>
size_t YL_Queue<T>::size() const
{
    return inStack.size()+outStack.size();
}

void main()
{
    YL_Queue<int> myqueue;
    myqueue.enqueue(1);
    myqueue.enqueue(2);
    myqueue.enqueue(3);
    myqueue.enqueue(4);
    myqueue.enqueue(5);
    cout<<"1队列的大小为: "<<myqueue.size()<<endl;
    cout<<"1队首的元素为: "<<myqueue.top()<<endl;
    myqueue.dequeue();
    myqueue.dequeue();
    cout<<"2队列的大小为: "<<myqueue.size()<<endl;
    cout<<"2队首的元素为: "<<myqueue.top()<<endl;
    myqueue.dequeue();
    myqueue.dequeue();
    myqueue.dequeue();
    cout<<"3队列的大小为: "<<myqueue.size()<<endl;
}

两个队列实现栈

思路

    s1是入队列的，s2是辅助s1入队列的。

• 入队列：如果s1不空，把s1的元素push到s2中，之后push新元素到s1，再把s2的元素都push到s1中；否则，直接push元素到s1
• 出队列：直接从s1中pop

代码：

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

template <class T>
class Stack {
public:
    bool empty( ) const { return m_queue1.empty() && m_queue2.empty(); }
    size_t size( ) const { return m_queue1.size() + m_queue2.size(); }
    T& top( );
    const T& top( ) const;
    void push( const T& x );
    void pop( );
private:
    queue<T> m_queue1;
    queue<T> m_queue2;
};

template <class T>
T& Stack<T>::top( )
{
    assert( !m_queue1.empty() );
    return m_queue1.front( );
}

template <class T>
const T& Stack<T>::top( ) const 
{
    assert( !m_queue1.empty() );
    return m_queue1.front( );
}

template <class T>
void Stack<T>::push( const T& x )
{
    while( !m_queue1.empty() ) {  //s1不空，把元素push到s2 
        const T& val = m_queue1.front( );
        m_queue1.pop( );
        m_queue2.push( val );
    }
    m_queue1.push( x );   //push新元素到s1 
    while( !m_queue2.empty() ) {   //s2不空，把元素在push回s1 
        const T& val = m_queue2.front( );
        m_queue2.pop( );
        m_queue1.push( val );
    }
}

template <class T>
void Stack<T>::pop( )
{
    assert( !m_queue1.empty() );
    m_queue1.pop( );
}

int main( )
{
    Stack<int> s;
    for( int i = 1; i <= 5; ++i )
        s.push( i );
    cout << "1.栈元素个数：" << s.size( ) << endl;
    cout << "1.栈顶元素：" << s.top( ) << endl;
    
    s.pop( );
    s.push( 6 );
    cout << "2.栈元素个数：" << s.size( ) << endl;
    cout << "2.栈顶元素："<< s.top( ) << endl;
    
    s.pop( );    
    s.pop( );
    s.pop( );
    s.push( 7 );
    cout << "3.栈元素个数：" << s.size( ) << endl;
    cout << "3.栈顶元素："<< s.top( ) << endl;
    
    s.pop( );    
    s.pop( );    
    s.pop( );
    cout << "4.栈元素个数：" << s.size( ) << endl;

    return 0;
}