如何用兩個Java隊列實現一個棧？動力節點小編來告訴大家。我們通過一系列棧的壓入和彈出操作來分析用兩個隊列模擬一個棧的過程。如圖(a)所示，我們先往棧內壓入一個元素A。由于兩個隊列現在都是空的，我們可以選擇把A插入兩個隊列的任意一個。不妨插入queue1。接下來繼續往棧內壓入B、C兩個元素，我們把它們都插入queue1。這個時候queue1包含3個元素A、B和C，其中A位于隊列的頭部，C位于隊列的尾部。

現在我們考慮從棧內彈出一個元素。根據棧的后入先出原則，最后被壓入棧的C應該最先被彈出。由于C位于queue1的尾部，而我們每次只能從隊列的頭部刪除元素，因此我們可以先從queue1中依次刪除元素A、B并插入到queue2中，再從queue1中刪除元素C。這就相當于從棧中彈出元素C了(如圖(b)所示)。我們可以用同樣的方法從棧內彈出元素B(如圖©所示)

接下來我們考慮往棧內壓入一個元素D。此時queue1已經有一個元素，我們就把D插入到queue1的尾部(如圖(d)所示)。如果我們再從棧內彈出一個元素，此時被彈出的應該是最后被壓入的D。由于D位于queue1的尾部，我們只能先從有刪除queue1的元素并插入到queue2，直到在queue1中遇到D再直接把它刪除(如圖(e)所示)。

注意在此過程中，新push進來的元素總是插入到非空隊列中，空隊列則用來保存pop操作之后的那些元素，那么此時空隊列不為空了，原來的非空隊列變為空了，總是這樣循環。

完整代碼

#include <iostream>
#include <stdlib.h>
#include <stack>
#include <queue>
using namespace std;
template <typename T> class CStack{
public:
    CStack(void){};
    ~CStack(void){};
    void push(const T& node);
    T pop();
private:
    queue<T> queue1;
    queue<T> queue2;
};
//插入元素：往非空的隊列中增加元素，若都為空，則默認往queue1中添加
template <typename T> void CStack<T>::push(const T& element)
{
    if (queue1.size() > 0)//如果queue1不為空則往queue1中插入元素
        queue1.push(element);
    else if (queue2.size() > 0)//如果queue2不為空則往queue2中插入元素
        queue2.push(element);
    else//如果兩個隊列都為空，則往queue1中插入元素
        queue1.push(element);
}
//刪除元素
template <typename T> T CStack<T>::pop()
{
    if (queue1.size() == 0)    //如果queue1為空
    {
        while (queue2.size() > 1)    //當queue2中大于一個元素時，則
            //將其余元素保存到queue1中，保證queue2中只有一個元素
        {
            queue1.push(queue2.front());//壓入queue1
            queue2.pop();//然后刪除
        }
        //只剩下一個元素時，即出列，此時對于由兩個隊列構成的棧而言，
        //彈出的即是最后進入的元素，符合后進先出
        T& data = queue2.front();//存儲
        queue2.pop();//而后刪除
        return data;
    }
    else   //如果queue2為空
    {
        while (queue1.size() > 1) // 當queue1中大于一個元素時，則
            //將其余元素保存到queue2中，保證queue1中只有一個元素
        {
            queue2.push(queue1.front());//壓入queue2
            queue1.pop();//然后刪除
        }
        //只剩下一個元素時，即出列，此時對于由兩個隊列構成的棧而言，
        //彈出的即是最后進入的元素，符合后進先出
        T& data = queue1.front();
        queue1.pop();
        return data;
    }
}
int main()
{
    CStack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    int len = 4;
    while (len>0)
    {
        cout << stack.pop() << " ";
        --len;
    }
    return 0;
}

對于push和pop操作，其時間為O(n).

運行結果：

以上就是關于“教你如何用兩個隊列實現一個棧”的介紹，大家如果想了解更多相關知識，不妨來關注一下本站的Java在線學習，里面的課程內容細致全面，適合沒有基礎的小伙伴學習，希望對大家的學習能夠有所幫助哦。