淺談棧和隊(duì)列的有關(guān)面試題

  最近本博主在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)，不不不?。?！應(yīng)該是預(yù)習(xí)，因?yàn)榘焉蠈W(xué)期學(xué)的基本上全都還給腦四了，之前寫(xiě)過(guò)有關(guān)實(shí)現(xiàn)庫(kù)里邊棧和隊(duì)列的文章，經(jīng)過(guò)這幾天的堅(jiān)持不懈的努力，硬是啃了幾道有關(guān)棧和隊(duì)列的面試頻率較高的題，今天就和大家分享一下下啦！

（一）實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu) 使得pop push min(獲得棧中最小元素)操作的時(shí)間復(fù)雜度為O(1)

思路：可以用兩個(gè)棧來(lái)實(shí)現(xiàn)，一個(gè)棧用來(lái)push,pop,一個(gè)棧用來(lái)保存這個(gè)過(guò)程的最小值，

比如有一組數(shù)要入棧

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

s2:8,3,2,2

要實(shí)現(xiàn)這種功能我們可以通過(guò)給第二個(gè)棧中的每個(gè)元素添加一個(gè)計(jì)數(shù)器，當(dāng)有重復(fù)元素進(jìn)棧的時(shí)候，只需給計(jì)數(shù)器加加即可，那么問(wèn)題來(lái)了，當(dāng)元素很多的時(shí)候，這種方法很浪費(fèi)空間，所以最好的方法就是重復(fù)元素只要比當(dāng)前第二個(gè)棧的棧頂元素小，都可以進(jìn)棧哦 

#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;
}

（二）兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

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

}
（三）一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧
#include<iostream>
#include<assert.h>
using namespace std;
template<typename T>
class TwoStack
{
public:
	//棧的構(gòu)造函數(shù)實(shí)現(xiàn)
	TwoStack()
		:_a(0)
		,_top1(0)
		,_top2(0)
		,_Capacity(0)
	{}
	//棧的析構(gòu)函數(shù)實(shí)現(xiàn)
	~TwoStack()
	{
		if(_a!=NULL)
		{
		delete [] _a;
		}
	}
	//棧的拷貝構(gòu)造函數(shù)實(shí)現(xiàn)
	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)
	 {
		//逐次拷貝兩個(gè)棧對(duì)應(yīng)的數(shù)組序列
	   
	   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];
	   }
	}
	//棧的賦值運(yùn)算符重載函數(shù)的實(shí)現(xiàn)
	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;
	}
	//壓棧函數(shù)
	 void Push(const T& d,int choice )
	{
		_CheckCapacity();
		if(choice==1)
		{
		_a[_top1++]=d;
		}
		if(choice==2)
		{
		_a[_top2--]=d;
		}
	}
 //元素出棧函數(shù)
	void Pop(int choice)
	{
		if(choice==1)
		{
		assert(_top1>0);
			--_top1;
		}
		if(choice==2)
		{
		assert(_top2<_Capacity-1);
		++_top2;
		}
	}
	//求棧頂元素函數(shù)
	T&Top(int choice)
	{
	if(choice==1)
	{

	return _a[_top1-1];
	}
	if(choice==2)
	{
	return _a[_top2+1];
	}
	}
	//判空函數(shù)
	bool empty(int choice)
	{
		if(choice==1)
		{
		return _top1==0;
		}
		if(choice==2)
		{
		return _top2==_Capacity-1;
		}
	}
	//求棧的元素個(gè)數(shù)函數(shù)
	size_t Size(int choice)
	{
	if(choice==1)
	{
		cout<<"棧1的元素個(gè)數(shù)為："<<endl;
	   return _top1;
	}
	if(choice==2)
	{
		cout<<"棧2的元素個(gè)數(shù)為："<<endl;
	    return _Capacity-1-_top2;
	}
	}
	//容量檢測(cè)函數(shù)
	void _CheckCapacity()
	{
		if(_a==NULL)
		{
		//保證如果數(shù)組為空的時(shí)候至少能開(kāi)辟到空間
		_a=new T[2*_Capacity+3];
		_top2=_Capacity-1;
		}
		//當(dāng)兩個(gè)棧頂相遇時(shí)需要開(kāi)辟空間
		if(_top1==_top2)
		{
			size_t _oldCapacity=_Capacity;
			//開(kāi)辟新空間
			T* _tmp=new T[_Capacity*2+3];
			//將原來(lái)的內(nèi)容拷貝到新的空間，然后釋放原來(lái)的舊空間
			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;//數(shù)組
	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;
//如果兩個(gè)序列不相等，則直接返回
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;
}

（五）兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

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

	//隊(duì)列入隊(duì)操作
	void Push(const T& d)
	{
	_s1.push(d);
	}
	//隊(duì)列出隊(duì)操作
	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;
}