真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網(wǎng)站制作重慶分公司

棧&隊(duì)列的那些應(yīng)用---常見面試題-創(chuàng)新互聯(lián)

 首先呢，偶們先來回顧一下棧和隊(duì)列的特征：

公司主營業(yè)務(wù)：網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出呼中免費(fèi)做網(wǎng)站回饋大家。

 棧呢，只能在末端上進(jìn)行操作，具有先進(jìn)后出的特點(diǎn)。

 隊(duì)列呢，只能在隊(duì)頭刪除，隊(duì)尾插入，具有先進(jìn)先出的特點(diǎn)。

 偶們應(yīng)該利用棧和隊(duì)列的特征來解決一下幾個(gè)問題：

  1.使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

  2.使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

  3.元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

  4.一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧

  5.實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（出棧）、Pop（入棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)

先來看第一個(gè)問題：

  1. 使用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

    思路：棧（先進(jìn)后出）  隊(duì)列（先進(jìn)先出）

    假設(shè)有兩個(gè)棧為是s1，s2。將s1作為基礎(chǔ)棧，而s2只是暫時(shí)維護(hù)數(shù)據(jù)棧。

  若壓入1,2,3。則輸出的也應(yīng)該是1，2,3。

  “入隊(duì)”：棧只能從棧頂出。所以現(xiàn)將s1中的數(shù)據(jù)壓入s2中（如圖）。

  “出隊(duì)”：從s2中彈出即可。

棧&隊(duì)列的那些應(yīng)用---常見面試題

代碼實(shí)現(xiàn)：

#include 
template 
class StackToQueue//棧s1為基本棧，s2維護(hù)棧
{
public:
	StackToQueue()
		:_size(0)
	{}
public:
void StackToQueuePush(const T& d)//s1入隊(duì)
{
	s1.push(d);
	++_size;
}
void StackToQueuePop()//s2出隊(duì)
{
	if(s2.empty())
	{
		while(!s1.empty())//將棧s1--->s2
	   {
		   s2.push(s1.top());
		   s1.pop();
		}
	}
	s2.pop();
	--_size;
}
void Print()
{
	while(!s1.empty())
	{
		cout< s1;//使用庫函數(shù)stack
	stack s2;
	size_t _size;//棧中元素個(gè)數(shù)
};

2.使用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧

思路：隊(duì)列（先進(jìn)先出），棧（后進(jìn)先出）

    隊(duì)列和棧插入數(shù)據(jù)時(shí)都是在末端操作。刪除數(shù)據(jù)不同，棧還是在末端操作而隊(duì)列在隊(duì)頭操作。

    假設(shè)有隊(duì)列q1，q2。

    “出?！保杭偃绗F(xiàn)有個(gè)n數(shù)據(jù)，將數(shù)據(jù)壓入q1，然后將n-1個(gè)數(shù)據(jù)彈入q2，將第n個(gè)數(shù)據(jù)彈出，此時(shí)  s1隊(duì)列為空，將q2中的前n-1個(gè)數(shù)據(jù)彈入q1，將第n個(gè)彈出。此時(shí)q2隊(duì)列為空，以此類推，知道彈出所有  數(shù)據(jù)。

代碼實(shí)現(xiàn)：

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;//隊(duì)列中元素的個(gè)數(shù)
};

3.元素出棧、入棧順序的合法性。如入棧的序列（1,2,3,4,5），出棧序列為（4,5,3,2,1）

看到此題，首先想到棧的特征是后進(jìn)先出。這就使得棧的出棧順序有多種。

舉一個(gè)簡(jiǎn)單的例子：

假如有一個(gè)入棧序列為1,2,3。出棧序列就有1,2,3、2,1,3、3,2,1、2,3,1、1,3,2共5種。

解題思路：

若要驗(yàn)證出入棧的合法性。首先呢，我們應(yīng)該有兩個(gè)數(shù)組將入棧序列和出棧序列保存起來。假設(shè)Push數(shù)組存入棧，Pop數(shù)組存出棧。從頭開始判斷數(shù)據(jù)是否相同，若相同，Push和Pop數(shù)組下標(biāo)加加。若不同，應(yīng)將數(shù)據(jù)保存起來，以便下一次比較。這就有一個(gè)問題。如何將數(shù)據(jù)保存起來呢，還要便于取出呢？這就需要一個(gè)棧將其保存。若不相同，將其壓棧。比較下一個(gè)數(shù)據(jù)，如不相同，還要將棧中的數(shù)據(jù)彈出比較，相同彈出，不同繼續(xù)壓棧。

代碼實(shí)現(xiàn)：

//借助兩個(gè)數(shù)組以及一個(gè)棧
#include 
#include 
bool IsVail(int *Push,int *Pop,int n)
{
	assert(Push);//數(shù)組元素不為NULL
	assert(Pop);
	stack s;
	int i = 0;
	int j = 0;
	for(j=0;j
4.一個(gè)數(shù)組實(shí)現(xiàn)兩個(gè)棧
解題思路：
（1）可將數(shù)組以奇數(shù)為下標(biāo)的當(dāng)為棧1，以偶數(shù)為下標(biāo)的當(dāng)為棧2。
（2）將數(shù)組一分為二，左邊為棧1，右邊為棧2。
（3）數(shù)組從左邊開始為棧1，從右邊開始為棧2。
分析：
思路（1），（2）雖然能解決問題，但是會(huì)浪費(fèi)空間。若棧1存滿，需要擴(kuò)容。而棧2可能空無元素。
思路（3）可解決此缺憾。當(dāng)棧1，棧2的棧頂相遇時(shí)，需要擴(kuò)容。
以下用靜態(tài)和動(dòng)態(tài)分別實(shí)現(xiàn)：
（1）靜態(tài)
代碼實(shí)現(xiàn)
#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)//給標(biāo)志，若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];//數(shù)組
	int _top1;//棧1的棧頂
	int _top2;//棧2的棧頂
};
（2）動(dòng)態(tài)
代碼實(shí)現(xiàn)
class ArrayToStack
{
public:
	ArrayToStack()
		:_a(NULL)
		,_top1(0)
		,_top2(0)
		,_capacity(0)
	{}
	~ArrayToStack()
	{
		if(_a)
		{
			delete[] _a;
		}
	}
public:
	void _CheckCapacity()//擴(kuò)容
	{
		if(_a == NULL)
		{
			_capacity = 3;
			_a = new T[_capacity];
			_top1 = 0;
			_top2 = _capacity-1;
		}
		else
		{
			if(_top1 == _top2)
			{
				int capacity = _capacity; //保存之前的容量，在下面復(fù)制時(shí)方便找到最后一個(gè)元素
				_capacity = 2*_capacity;
				int i = 0;
				int j = 0;
				T* tmp = new T[_capacity];
				for(i=0;i<_top1;i++)//將原來的復(fù)制到新開辟的空間上
				{
					tmp[i] = _a[i];
				}
				int k = _capacity - 1;//擴(kuò)容后的最后一位
				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.實(shí)現(xiàn)一個(gè)棧，要求實(shí)現(xiàn)Push（入棧）、Pop（出棧）、Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)
看到此題，我們都知道Push（入棧）、Pop（出棧）的時(shí)間復(fù)雜度為O（1）。而解決此題的難點(diǎn)在于Min（返回最小值的操作）的時(shí)間復(fù)雜度為O(1)。我們不可能從頭開始遍歷，這樣復(fù)雜度不可能為O（1）
解決此題的方法有如下兩種：
（1）使用一個(gè)棧
每一次入棧都?jí)簝纱?，第一次壓入原始?shù)據(jù)，第二次壓入當(dāng)前棧中最小的。在第二壓棧之前，需和上一次的比較，若小于則壓棧，否則將上一次的再次壓棧。出棧時(shí)，每次都彈出兩次。
（2）使用兩個(gè)棧
第一個(gè)棧用來保存原始數(shù)據(jù)，第二棧用保存當(dāng)前棧中最小值。第一次兩個(gè)棧中都?jí)喝耄粼俅螇喝霔?，需要和?dāng)前棧2中的元素比較，若小于等于則入棧，否則只壓入棧1。
分析：
 若要是數(shù)據(jù)量龐大，可見第一種方法使用的空間很大。
 此處實(shí)現(xiàn)的是第二種方法：
棧的簡(jiǎn)單實(shí)現(xiàn)：
template 
class Stack
{
public:
	Stack()//構(gòu)造函數(shù)
		:_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()//元素個(gè)數(shù)
	{
		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;//棧中元素的個(gè)數(shù)
};
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
            

            分享標(biāo)題：棧&隊(duì)列的那些應(yīng)用---常見面試題-創(chuàng)新互聯(lián)            

            文章URL：http://weahome.cn/article/digspd.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部