實現(xiàn)一個棧，并且實現(xiàn)一個min函數(shù)用來找當(dāng)前棧中最小的元素

題目描述：實現(xiàn)一個棧，并且實現(xiàn)一個min函數(shù)用來找當(dāng)前棧中最小的元素

成都創(chuàng)新互聯(lián)專注于網(wǎng)站建設(shè)，為客戶提供成都網(wǎng)站設(shè)計、網(wǎng)站制作、網(wǎng)頁設(shè)計開發(fā)服務(wù)，多年建網(wǎng)站服務(wù)經(jīng)驗，各類網(wǎng)站都可以開發(fā)，品牌網(wǎng)站制作，公司官網(wǎng)，公司展示網(wǎng)站，網(wǎng)站設(shè)計，建網(wǎng)站費用，建網(wǎng)站多少錢，價格優(yōu)惠，收費合理。

分析：要找到棧中最小的元素，需要借助一個輔助棧，來存放當(dāng)前棧中最小的元素。

入棧的時候，第一個入棧的元素，也給輔助棧入棧，此后每次入棧的元素先與輔助棧的棧頂元素比較，如果小于或等于輔助棧的棧頂元素，則同時將該元素給輔助棧入棧。

如下圖所示：

出棧的時候，如果棧頂元素與輔助棧棧頂?shù)脑叵嗟龋瑒t同時對輔助棧進(jìn)行出棧操作

如下圖所示：

這樣就可以保證，輔助棧中的棧頂元素始終是當(dāng)前棧中最小的元素了

代碼如下：

#include<iostream>
#include<stack>
using namespace std;


template<class T>
class Stack
{
public:
	Stack()
	{}

	~Stack()
	{}

	void Push(const T& x)
	{
		_stack.push(x);

		if (_minstack.empty())  //最小棧為空時
		{
			_minstack.push(x);
		}
		else
		{
			if (x <= _minstack.top())
			{
				_minstack.push(x);
			}
		}
	}

	void Pop()
	{
		T cur = _stack.top();
		_stack.pop();
		if (cur == _minstack.top())
		{
			_minstack.pop();
		}
	}

	T GetMin()
	{
		if (!_minstack.empty())
		{
			return _minstack.top();
		}
	}

private:
	stack<T> _stack;
	stack<T> _minstack;
};

void Test1()
{
	Stack<int> s1;
	s1.Push(3);
	s1.Push(2);
	s1.Push(1);
	s1.Push(4);
	s1.Push(1);
	s1.Push(5);
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
	s1.Pop();
}

網(wǎng)頁標(biāo)題：實現(xiàn)一個棧，并且實現(xiàn)一個min函數(shù)用來找當(dāng)前棧中最小的元素
網(wǎng)頁路徑：http://muchs.cn/article44/pgdhhe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、、網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、網(wǎng)頁設(shè)計公司、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)