【數據結構】（面試題）使用兩個棧實現一個隊列(詳細介紹)

使用兩個棧實現一個隊列

思路一：

我們設定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。