【数据结构】（面试题）使用两个栈实现一个队列(详细介绍)

使用两个栈实现一个队列

思路一：

我们设定s1是入栈的，s2是出栈的。

入队列，直接压到s1即可

出队列，先把s1中的元素倒入到s2中，弹出s2中的栈顶元素；再把s2的剩余元素全部倒回s1中。

缺点：

每次只要出栈一个元素就要将元素倒来倒去，麻烦！！！

思路2：

入队列时：
如果s1为空，把s2中所有的元素倒出压到s1中。否则直接压入s1   

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

思路1无条件地每次都要将元素倒来倒去，思路2出队时较思路1简单

思路3：

我们设定s1是入栈的，s2是出栈的

入队列：直接压入元素至s1即可

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

相比于方法2，入队直接压入即可~

那么，我们可以看出，思路三最简单，我们下面看下代码。

代码实现：

1）我们直接调用库里的stack来实现。（一般调用库里的就行了）

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
//两个栈实现一个队列
#include<stack>

template<class T>
class Queue
{
public:
    void appendTail(const T& x)
    {
        s1.push(x);
    }

    void deleteHead()
    {
          if (s2.empty())
          {
              while (!s1.empty())
              {
                  s2.push(s1.top());
                  s1.pop();
              }
              cout << s2.top() << "  ";
              s2.pop();
          }
          else
          {
               cout << s2.top() << "  ";
               s2.pop();          
          } 
    }
private:
    stack<T> s1;
    stack<T> s2;
    
};


void Test()
{
    Queue<int> q;
    q.appendTail(1);
    q.appendTail(2);
    q.appendTail(3);
    q.appendTail(4);
    q.deleteHead();
    q.deleteHead();
    q.deleteHead();
    q.deleteHead();
}

int main()
{
    Test();
    system("pause");
    return 0;
}

2）自己实现栈实现。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>

//直接实现Stack，也可以用适配器实现栈，或者用库。
//将Stack基本功能实现如下：
template<class T>

class Stack
{
public:
    Stack()
        :_array(NULL)
        , _size(0)
        , _capacity(0)
    {}

    Stack<T>(const Stack<T>& s)
        : _array(new T[s._capacity])
    {
        swap(_array, s._array);
        swap(_size, s._size);
        swap(_capacity, s._capacity);
    }

    Stack<T>& operator=(const Stack<T>& s)
    {
        if (&s != this)
        {
            swap(_array, s._array);
            swap(_size, s._size);
            swap(_capacity, s._capacity);
        }
        return *this;
    }

    ~Stack()
    {
        if (_array)
        {
            delete[] _array;
            _array = NULL;
        }
    }

    void _CheckCapacity()
    {
        if (_size == 0)
        {
            _capacity = 3;
            _array = new T[_capacity];
        }
        if (_size >= _capacity)
        {
            _capacity *= 2;
            T* tmp = new T[_capacity];
            for (int index = 0; index < _size; index++)
            {
                tmp[index] = _array[index];
            }
            delete[] _array;
            _array = tmp;
        }
    }

    void Push(const T& x)
    {
        _CheckCapacity();
        _array[_size++] = x;
    }

    void Pop()
    {
        if (_size == 0)
        {
            return;
        }
        --_size;
    }

    size_t Size()
    {
        return _size;
    }

    bool Empty()
    {
        return Size() == 0;
    }

    T& Top()
    {
        assert(_size > 0);
        return _array[_size - 1];
    }

private:
    T* _array;
    size_t _size;
    size_t _capacity;
};


template<class T>
class Queue
{
public:
    void InQueue(const T& x)
    {
        s1.Push(x);
    }

    void OutQueue()
    {
        //栈s2为空，则将栈s1的元素全部倒入s2中，再弹出最上面的那个元素
        if (s2.Empty())
        {
            while (!s1.Empty())
            {
                s2.Push(s1.Top());
                s1.Pop();
            }
            s2.Pop();
        }

        //栈s2不为空，直接弹出元素
        else
        {
            s2.Pop();
        }
    }

    
    void Print()    //打印队列元素，分四种情况。
    {
        if (s1.Empty() && s2.Empty())
        {
            cout << "The Queue is Empty!";
        }

        else if (!s1.Empty() && s2.Empty())
        {
            while (!s1.Empty())
            {
                s2.Push(s1.Top());
                s1.Pop();
            }

            while (!s2.Empty())
            {
                cout << s2.Top() << "  ";
                s2.Pop();
            }
        }

        else if (s1.Empty() && !s2.Empty())
        {
            while (!s2.Empty())
            {
                cout << s2.Top() << "  ";
                s2.Pop();
            }
        }

        else
        {
            while (!s2.Empty())
            {
                cout << s2.Top() << "  ";
                s2.Pop();
            }

            while (!s1.Empty())
            {
                s2.Push(s1.Top());
                s1.Pop();
            }

            while (!s2.Empty())
            {
                cout << s2.Top() << "  ";
                s2.Pop();
            }
        }
        cout << endl;
    }

private:
    Stack<T> s1;    //入队
    Stack<T> s2;    //出队
};



//测试两个栈实现一个队列
void Test1()
{
    Queue<int> q1;
    q1.InQueue(1);
    q1.InQueue(2);
    q1.InQueue(3);
    q1.InQueue(4);
    /*q1.Print();*/

    q1.OutQueue();
    /*q1.Print();*/
    q1.InQueue(5);
    q1.InQueue(6);
    q1.InQueue(7);

    q1.Print();
}



int main()
{
    Test1();
    system("pause");
    return 0;
}

(1个细节)：

      注意再将元素倒入另一个栈时，代码并不是先pop,再push。因为这样push后元素就找不到了。因此要先访问到栈顶元素top,再push,而后pop。