面试题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;
}

补充：软件开发 , C++ ,

上一个：面试题8：旋转数组中的最小数字
下一个：POJ 3276 反转开灯问题 每次选取连续k个反转方向 问多少次方向相同