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

在灌云等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作按需求定制制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),網(wǎng)絡(luò)營銷推廣,成都外貿(mào)網(wǎng)站制作,灌云網(wǎng)站建設(shè)費(fèi)用合理。

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

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

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

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

s2:8,3,2,2

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

#include
#include
using namespace std;
template
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"<_s1;
	stack_s2;
};

void test()
{
	Stack_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()<
（二）兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
#include
#include
#include
using namespace std;
template
class Stack
{
public:
	void Push(const T& d)
	{
		//剛開始如果兩個(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:
	queueq1;
	queueq2;
};

void test()
{
	Stackq1;
	q1.Push(1);
	q1.Push(2);
	q1.Push(3);
	q1.Push(4);
	cout<
#include
using namespace std;
template
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& ts)
		:_a(new T[ts._Capacity-ts._top2+ts._top1])
		,_top1(ts._top1)
		,_top2(ts._top2)
		,_Capacity(ts._Capacity-ts._top2+ts._top1)
	 {
		//逐次拷貝兩個(gè)棧對應(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& operator=(const TwoStack& 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ù)為："<=_top2;i--)
			{
			_tmp[i]=_a[i];
			}
			delete []_a;
			_a=_tmp;
			_top2=_Capacity-1-(_oldCapacity-1-_top2);
		}
	}
	void print()
	{
	cout<<"棧1為："<_top2;i--)
	  {
	   cout<<_a[i]<<" ";
	  }
	  cout<<"over"< 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();
	TwoStackts2(ts1);
	cout<<"ts2----------"<ts3;
	ts3=ts1;
	cout<<"ts3----------"<
（四）出棧，入棧順序的合法性
#include
#include
#include
using namespace std;
template

bool IsValid(const T* stack_in,const T* stack_out,size_t size1,size_t size2)
{
assert(stack_in);
assert(stack_out);
stacks;
//如果兩個(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<
（五）兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
#include
#include
#include
using namespace std;
template
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"<_s1;
	stack_s2;
	
};

void test()
{
	Queues1;
	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;
}
            
            
                        

            標(biāo)題名稱：淺談棧和隊(duì)列的有關(guān)面試題            

            網(wǎng)站鏈接：http://weahome.cn/article/pichpi.html