大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

栈&队列的那些应用---常见面试题-创新互联

 首先呢,偶们先来回顾一下栈和队列的特征:

公司主营业务:网站设计、网站建设、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。成都创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。成都创新互联推出呼中免费做网站回馈大家。

 栈呢,只能在末端上进行操作,具有先进后出的特点。

 队列呢,只能在队头删除,队尾插入,具有先进先出的特点。

 偶们应该利用栈和队列的特征来解决一下几个问题:

  1.使用两个栈实现一个队列

  2.使用两个队列实现一个栈

  3.元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)

  4.一个数组实现两个栈

  5.实现一个栈,要求实现Push(出栈)、Pop(入栈)、Min(返回最小值的操作)的时间复杂度为O(1)

先来看第一个问题:

  1. 使用两个栈实现一个队列

    思路:栈(先进后出)  队列(先进先出)

    假设有两个栈为是s1,s2。将s1作为基础栈,而s2只是暂时维护数据栈。

  若压入1,2,3。则输出的也应该是1,2,3。

  “入队”:栈只能从栈顶出。所以现将s1中的数据压入s2中(如图)。

  “出队”:从s2中弹出即可。

栈&队列的那些应用---常见面试题

代码实现:

#include 
template 
class StackToQueue//栈s1为基本栈,s2维护栈
{
public:
	StackToQueue()
		:_size(0)
	{}
public:
void StackToQueuePush(const T& d)//s1入队
{
	s1.push(d);
	++_size;
}
void StackToQueuePop()//s2出队
{
	if(s2.empty())
	{
		while(!s1.empty())//将栈s1--->s2
	   {
		   s2.push(s1.top());
		   s1.pop();
		}
	}
	s2.pop();
	--_size;
}
void Print()
{
	while(!s1.empty())
	{
		cout< s1;//使用库函数stack
	stack s2;
	size_t _size;//栈中元素个数
};

2.使用两个队列实现一个栈

思路:队列(先进先出),栈(后进先出)

    队列和栈插入数据时都是在末端操作。删除数据不同,栈还是在末端操作而队列在队头操作。

    假设有队列q1,q2。

    “出栈”:假如现有个n数据,将数据压入q1,然后将n-1个数据弹入q2,将第n个数据弹出,此时  s1队列为空,将q2中的前n-1个数据弹入q1,将第n个弹出。此时q2队列为空,以此类推,知道弹出所有  数据。

代码实现:

template 
class QueueToStack
{
public:
	QueueToStack()
		:_size(0)
	{}
public:
	void QueueStackPush(const T& d)//q1入栈
	{
		q1.push(d);
		++_size;
	}
void QueueStackPop()//出栈
{
	size_t sz = 0;
	if(_size)
	{
		if(q2.empty())
		{
		    sz = _size - 1;
			while(sz--)
			{
				q2.push(q1.front());
				q1.pop();
			}
			q1.pop();
			--_size;
		}
		else //(q1.empty())
		{
			sz = _size - 1;
			while(sz--)
			{
				q1.push(q2.front());
				q2.pop();
			}
			q2.pop();
			--_size;
		}
	}
}
size_t Size()
{
	return _size;
}
T& Top()//栈顶元素
{
	return q1.back();
}
protected:
	queue q1;
	queue q2;
	size_t _size;//队列中元素的个数
};

3.元素出栈、入栈顺序的合法性。如入栈的序列(1,2,3,4,5),出栈序列为(4,5,3,2,1)

看到此题,首先想到栈的特征是后进先出。这就使得栈的出栈顺序有多种。

举一个简单的例子:

假如有一个入栈序列为1,2,3。出栈序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5种。

解题思路:

若要验证出入栈的合法性。首先呢,我们应该有两个数组将入栈序列和出栈序列保存起来。假设Push数组存入栈,Pop数组存出栈。从头开始判断数据是否相同,若相同,Push和Pop数组下标加加。若不同,应将数据保存起来,以便下一次比较。这就有一个问题。如何将数据保存起来呢,还要便于取出呢?这就需要一个栈将其保存。若不相同,将其压栈。比较下一个数据,如不相同,还要将栈中的数据弹出比较,相同弹出,不同继续压栈。

代码实现:

//借助两个数组以及一个栈
#include 
#include 
bool IsVail(int *Push,int *Pop,int n)
{
	assert(Push);//数组元素不为NULL
	assert(Pop);
	stack s;
	int i = 0;
	int j = 0;
	for(j=0;j

4.一个数组实现两个栈

解题思路:

(1)可将数组以奇数为下标的当为栈1,以偶数为下标的当为栈2。

(2)将数组一分为二,左边为栈1,右边为栈2。

(3)数组从左边开始为栈1,从右边开始为栈2。

分析:

思路(1),(2)虽然能解决问题,但是会浪费空间。若栈1存满,需要扩容。而栈2可能空无元素。

思路(3)可解决此缺憾。当栈1,栈2的栈顶相遇时,需要扩容。

以下用静态和动态分别实现:

(1)静态

代码实现

#define SIZE 10  
template 
class ArrayToStack
{
public:
	ArrayToStack()
		:_top1(0)//栈1从头开始
		,_top2(SIZE-1)//栈2从尾开始
	{}
public:
	//void Push2(const T& d)//从头压栈
	//{
	//	_a[_top1++] = d;
	//}
	//void Push3(const T& d)//从尾部压栈
	//{
	//	_a[_top2--] = d;
	//}
	void Push(const T& d,int choice)//给标志,若choice为0,压入栈1,若为1,压入栈2
	{
		if(choice == 0)
		{
			_a[_top1++] = d;
		}
		if(choice == 1)
		{
			_a[_top2--] = d;
		}
	}
	void Pop(int choice)//choice为0,弹出栈1,choice为1,弹出栈2
	{
   	       if(choice == 0)
		{
			if(_top1 == 0)
				return;
			else
			_top1--;
		}
		if(choice == 1)
		{
			if(_top2 == 0)
				return;
			else
			_top2++;
		}
	}
	size_t size(int choice)
	{
		if(choice == 0)
		{
			return _top1;
		}
		if(choice == 1)
		{
			return _top2;
		}	
	}
	T& Top(int choice)
	{
		if(choice == 0)
		{
			return _a[_top1];
		}
		if(choice == 1)
		{
			return _a[_top2];
		}	
	}
protected:
	T _a[SIZE];//数组
	int _top1;//栈1的栈顶
	int _top2;//栈2的栈顶
};

(2)动态

代码实现

class ArrayToStack
{
public:
	ArrayToStack()
		:_a(NULL)
		,_top1(0)
		,_top2(0)
		,_capacity(0)
	{}
	~ArrayToStack()
	{
		if(_a)
		{
			delete[] _a;
		}
	}
public:
	void _CheckCapacity()//扩容
	{
		if(_a == NULL)
		{
			_capacity = 3;
			_a = new T[_capacity];
			_top1 = 0;
			_top2 = _capacity-1;
		}
		else
		{
			if(_top1 == _top2)
			{
				int capacity = _capacity; //保存之前的容量,在下面复制时方便找到最后一个元素
				_capacity = 2*_capacity;
				int i = 0;
				int j = 0;
				T* tmp = new T[_capacity];
				for(i=0;i<_top1;i++)//将原来的复制到新开辟的空间上
				{
					tmp[i] = _a[i];
				}
				int k = _capacity - 1;//扩容后的最后一位
				for(j=capacity-1;j>_top2;j--)
				{
					tmp[k--] = _a[j];
				}
				_top2 = k;//将_top2更新
				delete[] _a;
				_a = tmp;
			}
		}
	}
	void Print()
	{
		int i = 0;
		int j = 0;
		for(i=_top1-1;i>=0;i--)
		{
			cout<<_a[i]<<" ";
		}
		cout<

5.实现一个栈,要求实现Push(入栈)、Pop(出栈)、Min(返回最小值的操作)的时间复杂度为O(1)

看到此题,我们都知道Push(入栈)、Pop(出栈)的时间复杂度为O(1)。而解决此题的难点在于Min(返回最小值的操作)的时间复杂度为O(1)。我们不可能从头开始遍历,这样复杂度不可能为O(1)

解决此题的方法有如下两种:

(1)使用一个栈

每一次入栈都压两次,第一次压入原始数据,第二次压入当前栈中最小的。在第二压栈之前,需和上一次的比较,若小于则压栈,否则将上一次的再次压栈。出栈时,每次都弹出两次。

(2)使用两个栈

第一个栈用来保存原始数据,第二栈用保存当前栈中最小值。第一次两个栈中都压入,若再次压入栈,需要和当前栈2中的元素比较,若小于等于则入栈,否则只压入栈1。

分析:

 若要是数据量庞大,可见第一种方法使用的空间很大。

 此处实现的是第二种方法:

栈的简单实现:

template 
class Stack
{
public:
	Stack()//构造函数
		:_a(NULL)
		,_top(0)
		,_capacity(0)
	{}
	~Stack()
	{
		if(_a)
		{
			delete[] _a;
			_a = NULL;
		}
	}
	Stack(Stack& s)
	{
		size_t i = 0;
		_top = s._top;
		_capacity = s._top;
		_a = new T[_top];
		for(i=0;i<_top;i++)
		{
			_a[i] = s._a[i];
		}
	}
	Stack& operator=(Stack& s)
	{
		if(this != &s)
		{
			size_t i = 0;
			delete[] _a;
			_top = s._top;
			_capacity = s._capacity;
			_a = new T[_top];
			for(i=0;i<_top;i++)
			{
				_a[i] = s._a[i];
			}
		}
		return *this;
	}
public:
	void CheckCapacity()//检容
	{
		if(_top == _capacity)
		{
			_capacity = _capacity*2+3;
		    T* tmp = new T[_capacity];
			size_t i = 0;
			for(i=0;i<_top;i++)
			{
				tmp[i] = _a[i];
			}
			delete[] _a;
			_a = tmp;
		}
	}
public:
	void Push(const T& x)//插入
	{
		CheckCapacity();
		_a[_top++] = x;
	}
	void Pop()//栈顶删除
	{
		_top--;
	}
	T& Top()//返回栈顶元素
	{
		return _a[_top-1];
	}
	bool Empty()//栈是否为空
	{
		return _top == 0;
	}
	size_t Size()//元素个数
	{
		return _top;
	}
private:
	T* _a;
	size_t _top;
	size_t _capacity;
};

返回最小值操作:

template 
class StackMin
{
public:
	StackMin()
		:_size(0)
	{}
public:
	void M_Push(const T& d)
	{
		if(s1.Empty() && s2.Empty())
		{
			s1.Push(d);
			s2.Push(d);
		}
		else
		{
			if(s2.Top() < d)
			{
				s1.Push(d);
			}
			else
			{
				s1.Push(d);
				s2.Push(d);
			}
		}
		++_size;
	}
	void M_Pop()
	{
		if(s1.Top() == s2.Top())
		{
			s1.Pop();
			s2.Pop();
		}
		else
		{
			s1.Pop();
		}
		--_size;
	}
	T& MinMem()
	{
		return s2.Top();
	}
	size_t M_Size()
	{
		return _size;
	}
protected:
	Stack s1;//栈1
	Stack s2;//栈2
	size_t _size;//栈中元素的个数
};

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


本文题目:栈&队列的那些应用---常见面试题-创新互联
URL链接:http://dzwzjz.com/article/digspd.html
在线咨询
服务热线
服务热线:028-86922220
TOP