面試題7：用兩個隊列實現棧

題目：用兩個隊列實現一個棧。實現兩個函數push和pop，完成從棧頂插入和刪除結點的功能。

思路：

（1）入棧：總是插入到非空隊列中

（2）出棧：將非空隊列中的前n-1個元素依次出隊列push進空隊列中，然後將最後一個元素出隊列，完成出棧操作。

C++代碼：

#include "stdafx.h"   
#include <iostream>   
#include <deque>   
#include <assert.h>   
using namespace std;  
  
// 兩個隊列實現一個棧   
template<class T>  
class CStack  
{  
public:  
    CStack() {}  
    ~CStack() {}  
    void PushData(const T& element);  
    void PopData(T& element);  
  
private:  
    deque<T> m_queue1;  
    deque<T> m_queue2;  
};  
  
template<class T>   
void CStack<T>::PushData(const T& element)  
{  
    if (m_queue1.size() > 0)  
    {  
        m_queue1.push_back(element);  
    }  
    else if (m_queue2.size() > 0)  
    {  
        m_queue2.push_back(element);  
    }  
    else  
    {  
        m_queue1.push_back(element);  
    }  
}  
  
template<class T>  
void CStack<T>::PopData(T& element)  
{  
    if (m_queue1.size() == 0)  
    {  
        while (m_queue2.size() > 1)  
        {  
            T& data = m_queue2.front();  
            m_queue2.pop_front();  
            m_queue1.push_back(data);  
        }  
  
        assert(m_queue2.size() == 1); //確保隊列2內有一個元素   
  
        element = m_queue2.front();  
        m_queue2.pop_front();         
    }  
    else if (m_queue2.size() == 0)  
    {  
        while (m_queue1.size() > 1)  
        {  
            T& data = m_queue1.front();  
            m_queue1.pop_front();  
            m_queue2.push_back(data);  
        }  
  
        assert(m_queue1.size() == 1); //確保隊列1內有一個元素   
  
        element = m_queue1.front();  
        m_queue1.pop_front();         
    }  
}  
  
int main()  
{  
    CStack<int> myStack;  
    int nPopData = 0;  
    myStack.PushData(1);  
    myStack.PushData(2);  
    myStack.PushData(3);  
    myStack.PopData(nPopData);  
    cout << nPopData << endl;  
    myStack.PushData(4);  
    myStack.PopData(nPopData);  
    cout << nPopData << endl;  
      
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
#include <deque>
#include <assert.h>
using namespace std;

// 兩個隊列實現一個棧
template<class T>
class CStack
{
public:
	CStack() {}
	~CStack() {}
	void PushData(const T& element);
	void PopData(T& element);

private:
	deque<T> m_queue1;
	deque<T> m_queue2;
};

template<class T> 
void CStack<T>::PushData(const T& element)
{
	if (m_queue1.size() > 0)
	{
		m_queue1.push_back(element);
	}
	else if (m_queue2.size() > 0)
	{
		m_queue2.push_back(element);
	}
	else
	{
		m_queue1.push_back(element);
	}
}

template<class T>
void CStack<T>::PopData(T& element)
{
	if (m_queue1.size() == 0)
	{
		while (m_queue2.size() > 1)
		{
			T& data = m_queue2.front();
			m_queue2.pop_front();
			m_queue1.push_back(data);
		}

		assert(m_queue2.size() == 1); //確保隊列2內有一個元素

		element = m_queue2.front();
		m_queue2.pop_front();		
	}
	else if (m_queue2.size() == 0)
	{
		while (m_queue1.size() > 1)
		{
			T& data = m_queue1.front();
			m_queue1.pop_front();
			m_queue2.push_back(data);
		}

		assert(m_queue1.size() == 1); //確保隊列1內有一個元素

		element = m_queue1.front();
		m_queue1.pop_front();		
	}
}

int main()
{
	CStack<int> myStack;
	int nPopData = 0;
	myStack.PushData(1);
	myStack.PushData(2);
	myStack.PushData(3);
	myStack.PopData(nPopData);
	cout << nPopData << endl;
	myStack.PushData(4);
	myStack.PopData(nPopData);
	cout << nPopData << endl;
	
	system("pause");
	return 0;
}