淺談棧和隊列的有關面試題

  最近本博主在復習數據結構，不不不！！！應該是預習，因為把上學期學的基本上全都還給腦四了，之前寫過有關實現庫里邊棧和隊列的文章，經過這幾天的堅持不懈的努力，硬是啃了幾道有關棧和隊列的面試頻率較高的題，今天就和大家分享一下下啦！

（一）實現一個棧結構 使得pop push min(獲得棧中最小元素)操作的時間復雜度為O(1)

思路：可以用兩個棧來實現，一個棧用來push,pop,一個棧用來保存這個過程的最小值，

比如有一組數要入棧

s1:8,9,10,3,2,2

s2:8,3,2,2

要實現這種功能我們可以通過給第二個棧中的每個元素添加一個計數器，當有重復元素進棧的時候，只需給計數器加加即可，那么問題來了，當元素很多的時候，這種方法很浪費空間，所以最好的方法就是重復元素只要比當前第二個棧的棧頂元素小，都可以進棧哦 

#include<iostream>
#include<stack>
using namespace std;
template<class T>
class Stack
{
public:

	void Push(const T& d)
	{
		if(_s2.empty()||_s2.top()>=d)
		{
		_s2.push(d);
		}
	  _s1.push(d);
	}

	void Pop()
	{
		if(_s1.top()==_s2.top())
		{
		_s2.pop();
		}
		_s1.pop();
	}

	T min()
	{
		if(_s2.empty())
		{
		return -1;
		}
		return _s2.top();
	}

	void PrintStack()
	{
	   while(!_s1.empty())
	   {
		   cout<<_s1.top()<<" ";
		   _s1.pop();
	   }
	   cout<<"over"<<endl;
	}
private:
	stack<T>_s1;
	stack<T>_s2;
};

void test()
{
	Stack<int>_s;
	_s.Push(9);
	_s.Push(10);
	_s.Push(8);
	_s.Push(5);
	_s.Push(2);
	_s.Push(2);
	_s.Push(23);
    _s.PrintStack();
	_s.min();
	cout<<_s.min()<<endl;
}
int main()
{
test();
system("pause");
return 0;
}

（二）兩個隊列實現一個棧

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<typename T>
class Stack
{
public:
	void Push(const T& d)
	{
		//剛開始如果兩個隊列都為空，則給q1壓入數據
		if(q1.empty()&&q2.empty())
		{
	    q1.push(d);
		return;
	   }
		//如果q2不為空q1為空，則給q2壓入數據
	   if(!q2.empty()&&q1.empty())
		{
		q2.push(d);
		return;
		}
	   //如果q1不為空，q2為空。則給q1壓入數據
		if(!q1.empty()&&q2.empty())
		{
		q1.push(d);
		}
	}
	T Pop()
	{
		//如果q2為空，將q1中元素（除了最頂部）一次出隊壓入q2中，然后再將q1中剩下的那個元素彈出
		if(q2.empty())
		{
			while(q1.size()>1)
			{
	        q2.push(q1.front());
			q1.pop();
			}
			T& data=q1.front();
			q1.pop();
			return data;
		}
		//如果q2不為空，將q2中元素一次出隊（除了最定部元素）壓入q1中，然后再將q2中剩下的那個元素彈出
		else
		{
			while(q2.size()>1)
			{
			q1.push(q2.front());
			q2.pop();
			}
			T& data=q2.front();
			q2.pop();
			return data;
		}
	}
	
private:
	queue<T>q1;
	queue<T>q2;
};

void test()
{
	Stack<int>q1;
	q1.Push(1);
	q1.Push(2);
	q1.Push(3);
	q1.Push(4);
	cout<<q1.Pop()<<endl;
	
}
int main()
{
test();
system("pause");
return 0;

}
（三）一個數組實現兩個棧
#include<iostream>
#include<assert.h>
using namespace std;
template<typename T>
class TwoStack
{
public:
	//棧的構造函數實現
	TwoStack()
		:_a(0)
		,_top1(0)
		,_top2(0)
		,_Capacity(0)
	{}
	//棧的析構函數實現
	~TwoStack()
	{
		if(_a!=NULL)
		{
		delete [] _a;
		}
	}
	//棧的拷貝構造函數實現
	TwoStack(const TwoStack<T>& ts)
		:_a(new T[ts._Capacity-ts._top2+ts._top1])
		,_top1(ts._top1)
		,_top2(ts._top2)
		,_Capacity(ts._Capacity-ts._top2+ts._top1)
	 {
		//逐次拷貝兩個棧對應的數組序列
	   
	   for(size_t i=0;i<=ts._top1;i++)
	   {
	   _a[i]=ts._a[i];
	   }

	   for(size_t i=ts._Capacity-1;i>=ts._top2;i--)
	   {
	    _a[i]=ts._a[i];
	   }
	}
	//棧的賦值運算符重載函數的實現
	TwoStack<T>& operator=(const TwoStack<T>& ts)
	{
	_top1=ts._top1;
	_top2=ts._top2;
	_Capacity=ts._Capacity;
	for(size_t i=0;i<_Capacity;i++)
	{
	_a[i]=ts._a[i];
	}
	return *this;
	}
	//壓棧函數
	 void Push(const T& d,int choice )
	{
		_CheckCapacity();
		if(choice==1)
		{
		_a[_top1++]=d;
		}
		if(choice==2)
		{
		_a[_top2--]=d;
		}
	}
 //元素出棧函數
	void Pop(int choice)
	{
		if(choice==1)
		{
		assert(_top1>0);
			--_top1;
		}
		if(choice==2)
		{
		assert(_top2<_Capacity-1);
		++_top2;
		}
	}
	//求棧頂元素函數
	T&Top(int choice)
	{
	if(choice==1)
	{

	return _a[_top1-1];
	}
	if(choice==2)
	{
	return _a[_top2+1];
	}
	}
	//判空函數
	bool empty(int choice)
	{
		if(choice==1)
		{
		return _top1==0;
		}
		if(choice==2)
		{
		return _top2==_Capacity-1;
		}
	}
	//求棧的元素個數函數
	size_t Size(int choice)
	{
	if(choice==1)
	{
		cout<<"棧1的元素個數為："<<endl;
	   return _top1;
	}
	if(choice==2)
	{
		cout<<"棧2的元素個數為："<<endl;
	    return _Capacity-1-_top2;
	}
	}
	//容量檢測函數
	void _CheckCapacity()
	{
		if(_a==NULL)
		{
		//保證如果數組為空的時候至少能開辟到空間
		_a=new T[2*_Capacity+3];
		_top2=_Capacity-1;
		}
		//當兩個棧頂相遇時需要開辟空間
		if(_top1==_top2)
		{
			size_t _oldCapacity=_Capacity;
			//開辟新空間
			T* _tmp=new T[_Capacity*2+3];
			//將原來的內容拷貝到新的空間，然后釋放原來的舊空間
			for(size_t i=0;i<=_top1;i++)
			{
			_tmp[i]=_a[i];
			}
			for(size_t i=_Capacity-1;i>=_top2;i--)
			{
			_tmp[i]=_a[i];
			}
			delete []_a;
			_a=_tmp;
			_top2=_Capacity-1-(_oldCapacity-1-_top2);
		}
	}
	void print()
	{
	cout<<"棧1為："<<endl;
	  for(size_t i=0;i<_top1;i++)
	  {
	  cout<<_a[i]<<" ";
	  }
	  cout<<"over"<<endl;
	  cout<<"棧2為："<<endl;
	  for(size_t i=_Capacity-1;i>_top2;i--)
	  {
	   cout<<_a[i]<<" ";
	  }
	  cout<<"over"<<endl;
	}
private:
	T* _a;//數組
	size_t _top1;
	size_t _top2;
	size_t _Capacity;
};

void test()
{
	TwoStack<int> ts1;
	ts1.Push(1,1);
	ts1.Push(2,1);
	ts1.Push(3,1);
	ts1.Push(4,1);
	ts1.Pop (1);

	ts1.Size(1);
	ts1.Push(4,2);
	ts1.Push(5,2);
	ts1.Push(6,2);
	ts1.Push(7,2);
	ts1.print();
	TwoStack<int>ts2(ts1);
	cout<<"ts2----------"<<endl;
	ts2.print();
	TwoStack<int>ts3;
	ts3=ts1;
	cout<<"ts3----------"<<endl;
	ts3.print();
}
int main()
{
	test();
	system("pause");
	return 0;
}

（四）出棧，入棧順序的合法性

#include<iostream>
#include<assert.h>
#include<stack>
using namespace std;
template<class T>

bool IsValid(const T* stack_in,const T* stack_out,size_t size1,size_t size2)
{
assert(stack_in);
assert(stack_out);
stack<T>s;
//如果兩個序列不相等，則直接返回
if(size1!=size2)
{
	return false;
}
  s.push(*stack_in++);
  --size1;
  while(size2)
  {
	  //輸入序列為1,2,3,4,5輸出序列為1,3,2,4,5
	  if(s.top()==*stack_out)
	  {
	   s.pop();
	   stack_out++;
	   --size2;
	   continue;
	  }
	  if(s.empty()&&size1)
	  {
		s.push(*stack_in++);
		--size1;
	  }
	
	  while((s.top()!=*stack_out)&&size1)
	  {
		s.push(*stack_in++);
		--size1;
	  }
	  if(size1==0&&(s.top()!=*stack_out))
	  {
		return false;
	  }
  }
  return true;
}

int main()
{
	int arr1[]={1,2,3,4,5};
	int arr2[]={4,3,5,2,1};
	size_t size1=sizeof(arr1)/sizeof(arr1[0]);
	size_t size2=sizeof(arr2)/sizeof(arr2[0]);
	bool ret=IsValid(arr1,arr2,size1,size2);
	cout<<ret<<endl;
	getchar();
	return 0;
}

（五）兩個棧實現一個隊列

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<typename T>
class Queue
{
public:

	//隊列入隊操作
	void Push(const T& d)
	{
	_s1.push(d);
	}
	//隊列出隊操作
	void Pop()
	{
		if(_s1.empty()&&_s2.empty())
		{
		cout<<"Queue is empty"<<endl;
		}
		if(!_s1.empty ()&&_s2.empty())
		{
			while(!_s1.empty())
			{
			_s2.push(_s1.top());
			_s1.pop();
			}
		}
		if(_s1.empty ()&&!_s2.empty())
		{
			cout<<_s2.top()<<" ";
			_s2.pop();
		}
	}
	bool Empty()
	{
	 return (_s1.()==0&&_s2.size()==0);
	}
private:
	stack<T>_s1;
	stack<T>_s2;
	
};

void test()
{
	Queue<int>s1;
	s1.Push(1);
	s1.Push(2);
	s1.Push(3);
	s1.Push(4);
	s1.Pop();
	s1.Pop();
	s1.Pop();

}
int main()
{
test();
system("pause");
return 0;
}