日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學(xué)無先后，達(dá)者為師

網(wǎng)站首頁 編程語言 正文

C++?超詳細(xì)講解stack與queue的使用_C 語言

作者：ymz123_ ? 更新時間： 2022-05-28 編程語言

stack

介紹和使用

stack文檔介紹

stack是一種容器適配器，專門用在具有后進(jìn)先出操作的上下文環(huán)境中，其刪除只能從容器的一端進(jìn)行元素的插入與提取操作。

stack是作為容器適配器被實現(xiàn)的，容器適配器即是對特定類封裝作為其底層的容器，并提供一組特定的成員函數(shù)來訪問其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。

stack的底層容器可以是任何標(biāo)準(zhǔn)的容器類模板或者一些其他特定的容器類，這些容器類應(yīng)該支持以下操作：

  • empty：判空操作
  • back：獲取尾部元素操作
  • push_back：尾部插入元素操作
  • pop_back：尾部刪除元素操作

標(biāo)準(zhǔn)容器vector、deque、list均符合這些需求，默認(rèn)情況下，如果沒有為stack指定特定的底層容器，默認(rèn)情況下使用deque。

模擬實現(xiàn)

從棧的接口可以看出，棧實際是一種特殊的vector，直接使用vector即可模擬實現(xiàn)stack

#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>
using namespace std;

namespace s {
	//stack是一個Container適配(封裝轉(zhuǎn)換)出來的
	template<class T,class Container = std::deque<T>>
	class stack {
	public:
		stack() {

		}

		void pop()
		{
			_con.pop_back();
		}

		void push(const T& x)
		{
			_con.push_back(x);
		}

		const T& top()
		{
			return _con.back();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

	void test_stack1()
	{
		s::stack<int,vector<int>> st;
		//s::stack<int, list<int>> st;
		//s::stack<int> st;
		st.push(1);
		st.push(2);
		st.push(3);
		st.push(4);

		while (!st.empty())
		{
			cout << st.top();
			st.pop();
		}
		cout << endl;
	}
}

stack的使用例題

最小棧

題目描述：設(shè)計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。push(x) —— 將元素 x 推入棧中。pop() —— 刪除棧頂?shù)脑亍op() —— 獲取棧頂元素。getMin() —— 檢索棧中的最小元素。

解題思路：定義兩個成員變量（棧），當(dāng)插入數(shù)據(jù)時，_st正常插入，如果要插入的數(shù)據(jù)比_st的棧頂元素小時，就把該數(shù)據(jù)也插入_minst。出數(shù)據(jù)時，取出_st棧頂元素，如果該數(shù)據(jù)和_minst棧頂數(shù)據(jù)相等，就把_minst的棧頂元素也取出，這樣_minst的棧頂元素就始終是棧中存在元素的最小值。

class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val<=_minst.top())
        {
            _minst.push(val);
        }
    }
    
    void pop() {
        if(_st.top()==_minst.top())
        {
            _minst.pop();
        }
        _st.pop();
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }

    stack<int> _st;
    stack<int> _minst;
};

棧的彈出壓入序列

題目描述：輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序，請判斷第二個序列是否可能為該棧的彈出順序。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

解題思路：定義一個棧，把pushV中的數(shù)據(jù)依次放入棧中。如果遇到放入的pushV中的數(shù)據(jù)和popV中數(shù)據(jù)相等，那么把st棧頂元素取出。最后st如果為空，則符合要求。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if(pushV.size()==0)
            return true;
        stack<int> st;
        int pushi=0,popi=0;
        while(pushi<pushV.size()){
            st.push(pushV[pushi]);
            //如果pushV[pushi]和popV[popi]匹配上了
            while(!st.empty() && st.top()==popV[popi]){
                st.pop();
                ++popi;
            }
            ++pushi;
        }
        if(st.empty())
            return true;
        return false;
    }
};

逆波蘭表達(dá)式求值

題目描述：根據(jù) 逆波蘭表示法，求表達(dá)式的值。有效的算符包括 +、-、*、/ 。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達(dá)式。說明：整數(shù)除法只保留整數(shù)部分。給定逆波蘭表達(dá)式總是有效的。換句話說，表達(dá)式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

解題思路：遍歷，如果是字符串中是數(shù)字，將字符數(shù)字轉(zhuǎn)化為數(shù)字后放入棧中，如果遇到運算符，取出兩個棧頂元素，先取出的棧頂元素作為運算符右邊的數(shù)字，后取出的作為運算符左邊的數(shù)字，按照字符串中的運算符做運算，得到的數(shù)字再放入棧中，再遍歷數(shù)組放入數(shù)字，以此類推。

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int left=0,right=0;
        for(const auto& str:tokens)
        {
            if(str=="+" ||str=="-"||str=="*"||str=="/")
            {
                right=st.top();
                st.pop();
                left=st.top();
                st.pop();
                switch(str[0])
                {
                case '+':
                    st.push(left+right);
                    break;
                case '-':
                    st.push(left-right);
                    break;
                case '*':
                    st.push(left*right);
                    break;
                case '/':
                    st.push(left/right);
                    break;
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

queue

queue的文檔介紹

和棧一樣，隊列是一種容器適配器。該底層容器至少支持以下操作：

empty：檢測隊列是否為空

size：返回隊列中有效元素的個數(shù)

front：返回隊頭元素的引用

back：返回隊尾元素的引用

push_back：在隊列尾部入隊列

pop_front：在隊列頭部出隊列

標(biāo)準(zhǔn)容器類deque和list滿足了這些要求。默認(rèn)情況下，如果沒有為queue實例化指定容器類，則使用標(biāo)準(zhǔn)容器deque。vector類的頭刪效率太低，不能頭刪，所以不適配。

模擬實現(xiàn)

因為queue的接口中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以借助list來模擬實現(xiàn)queue

#pragma once
#include <vector>
#include <list>
#include <deque>
#include <iostream>
using namespace std;

namespace q {

	template<class T,class Container=std::deque<T>>
	class queue {
	public:
		queue() {

		}

		void pop()
		{
			_con.pop_front();
		}

		void push(const T& x)
		{
			_con.push_back(x);
		}

		const T& back()
		{
			return _con.back();
		}

		const T& front()
		{
			return _con.front();
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

	void test_queue1()
	{
		//q::queue<int,list<int>> q1;
		//q::queue<int, vector<int>> q1;//vector頭刪效率低，不適配，報錯

		q::queue<int> q1;
		q1.push(1);
		q1.push(2);
		q1.push(3);
		q1.push(4);

		while (!q1.empty())
		{
			cout << q1.front();
			q1.pop();
		}
		cout << endl;

	}
}

容器適配器

適配器是一種設(shè)計模式(設(shè)計模式是一套被反復(fù)使用的、多數(shù)人知曉的、經(jīng)過分類編目的、代碼設(shè)計經(jīng)驗的總結(jié))，該種模式是將一個類的接口轉(zhuǎn)換成客戶希望的另外一個接口。

雖然stack和queue中也可以存放元素，但在STL中并沒有將其劃分在容器的行列，而是將其稱為容器適配器，這是因為stack和隊列只是對其他容器的接口進(jìn)行了包裝，STL中stack和queue默認(rèn)使用deque

deque簡介

deque(雙端隊列)：是一種雙開口的"連續(xù)"空間的數(shù)據(jù)結(jié)構(gòu)，即可以在頭尾兩端進(jìn)行插入刪除操作，且時間復(fù)雜度為O(1)。

deque不是真正完全連續(xù)的空間，而是由一段段連續(xù)的小空間拼接而成，類似于一個動態(tài)的二維數(shù)組。

deque底層是一段假想的連續(xù)空間，實際上是分段連續(xù)的，它借助迭代器來維護(hù)其假想連續(xù)的結(jié)構(gòu)，因此deque的迭代器設(shè)計也比較復(fù)雜。

vector的缺點是當(dāng)空間不夠時要擴(kuò)容，會存在一定的空間浪費，頭插或中間插入需要挪動數(shù)據(jù)，效率低。優(yōu)點是可以隨機(jī)訪問，cpu高速緩存命中率很高。list的缺點是無法隨機(jī)訪問，cpu高速緩存命中率低(地址不連續(xù))。優(yōu)點是可按需申請釋放空間，任意位置的插入刪除數(shù)據(jù)時間復(fù)雜度為O(1)，效率高。而deque折中了vector和list，從使用的角度，避開了它們的缺點，可以支持隨機(jī)訪問，頭尾插入效率也較高，擴(kuò)容時不需要挪動大量數(shù)據(jù)，效率較vector高。但deque不夠極致，隨機(jī)訪問效率不如vector，任意位置插入刪除不如list，且中間插入刪除數(shù)據(jù)也很麻煩，效率不高，需要挪動整體數(shù)據(jù)，或是挪動目標(biāo)buff數(shù)組，并記錄每個buff數(shù)組的大小。在遍歷時，deque的迭代器需要頻繁檢測是否移動到某段小空間的邊界，效率低下。所以deque比較適合頭插尾插多的情況，比如作為stack和queue的底層數(shù)據(jù)結(jié)構(gòu)。stack和queue不需要遍歷（所以沒有迭代器），只需要在固定的兩端進(jìn)行操作。stack中元素增長時，如果需要擴(kuò)容，deque的效率比vector高；queue同理，且內(nèi)存使用率高。

priority_queue優(yōu)先級隊列

priority_queue文檔介紹

優(yōu)先隊列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個元素總是它所包含的元素中最大的。

類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素（優(yōu)先隊列中位于頂部的元素）。

優(yōu)先隊列被實現(xiàn)為容器適配器，即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的尾部彈出，其成為優(yōu)先隊列的頂部。

底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計的容器類。容器應(yīng)該可以通過隨機(jī)訪問迭代器訪問，并支持以下操作：

  • empty()：檢測容器是否為空
  • size()：返回容器中有效元素個數(shù)
  • front()：返回容器中第一個元素的引用
  • push_back()：在容器尾部插入元素
  • pop_back()：刪除容器尾部元素

標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。

需要支持隨機(jī)訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時自動調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。

priority_queue的使用

優(yōu)先級隊列默認(rèn)使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了對算法將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆。注意：默認(rèn)情況下priority_queue是大堆。

在OJ中的使用：

數(shù)組中的第k個最大元素

題目描述：給定整數(shù)數(shù)組 nums 和整數(shù) k，請返回數(shù)組中第 k 個最大的元素。

請注意，你需要找的是數(shù)組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end());
        //默認(rèn)大堆，取出前k-1個元素后的第k個堆頂元素就是第k大的元素
        while(--k)
        {
            pq.pop();
        }
        
        return pq.top();
    }
};

priority_queue的模擬實現(xiàn)

#pragma once
#include <vector>
#include <list>
#include <iostream>
using namespace std;

namespace priority
{
	template<class T>
	class Less
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};

	//模板參數(shù)--類型
	//函數(shù)參數(shù)--對象

	//less 大堆
	template<class T,class Container=::vector<T>,class Compare=Less<typename Container::value_type>>
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			//插入數(shù)據(jù)
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			//建堆
			for (int i = (_con.size() - 1 - 1) / 2;i >= 0;i--)
			{
				AdjustDown(i);
			}
		}

		void AdjustDown(size_t parent)
		{
			Compare com;
			int child = parent * 2+1;
			while (child <_con.size())
			{
				if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
				{
					child++;
				}
				//_con[parent] < _con[child]
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void AdjustUp(size_t child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent] , _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}

		const T& top() const
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

	void test_priority_queue()
	{
		list<int> lt = { 1,2,3,4,5, };
		priority_queue<int, vector<int>, Greater<int>> pq(lt.begin(), lt.end());

		pq.push(10);
		pq.push(20);
		pq.push(30);
		pq.push(40);
		pq.push(50);
		pq.push(60);

		cout << pq.top() << endl;
		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}

通過仿函數(shù)控制比較方式

如果在priority_queue中放自定義類型的數(shù)據(jù)，我們需要在自定義類型中重載>或<。如以下情形，類型T是Date*，如果不重載<或>，比較的就是地址大小。

//仿函數(shù)的變異玩法--通過仿函數(shù)控制比較方式
class Date
{
public:
	Date(int year=1900,int month=1,int day=1)
		:_year(year)
		,_month(month)
		,_day(day)
	{}

	bool operator < (const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}

	friend ostream& operator<<(ostream& _cout, const Date& d);
	friend class PDateLess;

private:
	int _year;
	int _month;
	int _day;
};

ostream& operator<<(ostream& _cout, const Date& d)
{
	_cout << d._year << "-" << d._month << "-" << d._day << endl;
	return _cout;
}

class PDateLess
{
public:
	bool operator()(const Date* p1, const Date* p2)
	{
		return *p1 < *p2;
	}
};

int main()
{
	priority_queue<Date*, vector<Date*>, PDateLess> pq;
	pq.push(new Date(2023, 11, 24));
	pq.push(new Date(2021, 10, 24));
	pq.push(new Date(2023, 11, 14));
	pq.push(new Date(2022, 1, 24));

	cout << (*pq.top()) << endl;
	pq.pop();

	return 0;

}

原文鏈接：https://blog.csdn.net/mmz123_/article/details/121505391

欄目分類
最近更新