浅谈栈和队列的有关面试题

  最近本博主在复习数据结构，不不不！！！应该是预习，因为把上学期学的基本上全都还给脑四了，之前写过有关实现库里边栈和队列的文章，经过这几天的坚持不懈的努力，硬是啃了几道有关栈和队列的面试频率较高的题，今天就和大家分享一下下啦！

在灌云等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站建设、成都网站制作 网站设计制作按需求定制制作,公司网站建设,企业网站建设,高端网站设计,网络营销推广,成都外贸网站制作,灌云网站建设费用合理。

（一）实现一个栈结构 使得pop push min(获得栈中最小元素)操作的时间复杂度为O(1)

思路：可以用两个栈来实现，一个栈用来push,pop,一个栈用来保存这个过程的最小值，

比如有一组数要入栈

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

s2:8,3,2,2

要实现这种功能我们可以通过给第二个栈中的每个元素添加一个计数器，当有重复元素进栈的时候，只需给计数器加加即可，那么问题来了，当元素很多的时候，这种方法很浪费空间，所以最好的方法就是重复元素只要比当前第二个栈的栈顶元素小，都可以进栈哦 

#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()<
（二）两个队列实现一个栈
#include
#include
#include
using namespace std;
template
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:
	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:
	//栈的构造函数实现
	TwoStack()
		:_a(0)
		,_top1(0)
		,_top2(0)
		,_Capacity(0)
	{}
	//栈的析构函数实现
	~TwoStack()
	{
		if(_a!=NULL)
		{
		delete [] _a;
		}
	}
	//栈的拷贝构造函数实现
	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)
	 {
		//逐次拷贝两个栈对应的数组序列
	   
	   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& 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;
	}
	//压栈函数
	 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的元素个数为："<=_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;
//如果两个序列不相等，则直接返回
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<
（五）两个栈实现一个队列
#include
#include
#include
using namespace std;
template
class Queue
{
public:

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

            分享文章：浅谈栈和队列的有关面试题            

            网站URL：http://cqcxhl.cn/article/pichpi.html