使用兩個隊列實現一個棧

  首先，我們得了解隊列和棧的基本原理。

  隊列是一個“先進先出“的一個結構。隊列的定義是在隊尾插入，在隊頭刪除，這就要求要用一種在尾部插入容易的，在頭部刪除容易的結構，你一定會想到單鏈表，對，庫的實現就是用一個鏈表實現的。

  棧，相信大家都不會陌生，函數棧幀等的實現，它是一種”先進后出“的結構。棧的插入刪除都是在尾部進行的。

  所以要用隊列實現一個棧，要解決的問題就是在刪除時要刪除最后插入的那個元素。

  我們先來模擬一下出棧和入棧的情況：

 （1）入棧：Q1：1，2，3，4入隊列（相當于入棧）；

 （2）出棧：Q1：1，2，3出隊列，Q2：1，2，3入隊列；（此時Q1只剩4，正是我們要出棧的元素）

 （3）

     1>入棧：Q1：5入隊列（每次入棧都用Q1入隊列實現，而不入隊列Q2，這樣會提高效率，后面會說到）

     2>出棧：判斷：如果Q1隊列不為空就用（1）（2）步的方法出棧最后一個元素。否則，出棧Q2隊列的最后一個元素。

 我們首先來搭建這個棧的結構：

#pragma once
#include<iostream>
#include<queue>
#include<string>
#include<assert.h>

using namespace std;

template<class T>
class MYStack
{
public:
	MYStack()
		:_size(0)
	{
	}
	~MYStack()
	{
	}
	void Push(const T& x);
	void Pop();
	bool Empty();
	size_t Size();
	void Print();


private:
	queue<T> q1;
	queue<T> q2;
	size_t _size;
};

  一個棧具有的功能我們都實現一下，Psh(),Pop(),Empty(),Size()等等。

  在這個結構中數據成員是兩個隊列的對象，因為我們是用兩個隊列來實現的，還有一個_size用來記錄棧中元素的個數。

下面是函數具體實現：

template<class T>
void MYStack<T>::Push(const T& x)
{
	q1.push(x);
	++_size;
}

template<class T>
void MYStack<T>::Pop()
{
	//assert(_size > 0);
	//size_t plen = q1.size();
	//while (plen != 1)
	//{
	//	T tmp = q1.front();
	//	q2.push(tmp);
	//	q1.pop();
	//	--plen;
	//}
	//q1.pop();
	//plen = q2.size();
	//while (plen)
	//{
	//	T tmp = q2.front();
	//	q1.push(tmp);
	//	q2.pop();
	//	--plen;
	//}
	//--_size;


	assert(_size > 0);
	size_t plen = q1.size();
	if (plen == 0)
	{
		//if (q2.size() == 0)
		//	return;
		plen = q2.size();
		while (plen != 1)
		{
			T tmp = q2.front();
			q1.push(tmp);
			q2.pop();
			--plen;
		}
		q2.pop();
	}
	else
	{
		size_t plen = q1.size();
		while (plen != 1)
		{
			T tmp = q1.front();
			q2.push(tmp);
			q1.pop();
			--plen;
		}
		q1.pop();
	}
	--_size;
}


template<class T>
bool MYStack<T>::Empty()
{
	return _size ? false : true;
}

template<class T>
size_t MYStack<T>::Size()
{
	return _size;
}

template<class T>
void MYStack<T>::Print()
{
	//size_t plen = q1.size();
	//while (plen--)
	//{
	//	cout << q1.front() << " ";
	//	q1.pop();
	//}


	size_t plen = q2.size();
	while (plen--)
	{
		cout << q2.front() << " ";
		q2.pop();
	}
	plen = q1.size();
	while (plen--)
	{
		cout << q1.front() << " ";
		q1.pop();
	}
}

  注釋掉的部分也可以實現，它的原理是不管第（3）步是出棧還是入棧，都把剩下的元素從Q2出棧入棧到Q1，輸出的時候只用輸出Q1中的元素。但是它的效率較低。如果有這種情況：1，2，3.....100000入棧，然后1，2，3......100000出棧，這會導致Q1和Q2頻繁的出棧和入棧，效率非常之低。

  優化方法就是沒有注釋部分。它的實現就是入棧都是Q1入隊列，出棧后不把Q2的元素移到Q1，這樣的話效率就會提高，只是在輸出的時候要先輸出Q2里的元素，再輸出Q1里的元素。因為Q1里的元素總是棧頂的元素。