浅谈栈和队列的有关面试题-创新互联

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

（一）实现一个栈结构 使得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;
}
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
                

                本文题目：浅谈栈和队列的有关面试题-创新互联                

                网页路径：http://wjwzjz.com/article/dhphop.html