C++ 超詳細講解stack與queue的使用

2022-03-25 13:02:18

stack

介紹和使用

stack檔案介紹

stack是一種容器介面卡，專門用在具有後進先出操作的上下文環境中，其刪除只能從容器的一端進行元素的插入與提取操作。

stack是作為容器介面卡被實現的，容器介面卡即是對特定類封裝作為其底層的容器，並提供一組特定的成員函數來存取其元素，將特定類作為其底層的，元素特定容器的尾部(即棧頂)被壓入和彈出。

stack的底層容器可以是任何標準的容器類別範本或者一些其他特定的容器類，這些容器類應該支援以下操作：

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

標準容器vector、deque、list均符合這些需求，預設情況下，如果沒有為stack指定特定的底層容器，預設情況下使用deque。

模擬實現

從棧的介面可以看出，棧實際是一種特殊的vector，直接使用vector即可模擬實現stack

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

namespace s {
	//stack是一個Container適配(封裝轉換)出來的
	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的使用例題

最小棧

題目描述：設計一個支援 push ，pop ，top 操作，並能在常數時間內檢索到最小元素的棧。push(x) —— 將元素 x 推入棧中。pop() —— 刪除棧頂的元素。top() —— 獲取棧頂元素。getMin() —— 檢索棧中的最小元素。

解題思路：定義兩個成員變數（棧），當插入資料時，_st正常插入，如果要插入的資料比_st的棧頂元素小時，就把該資料也插入_minst。出資料時，取出_st棧頂元素，如果該資料和_minst棧頂資料相等，就把_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;
};

棧的彈出壓入序列

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

解題思路：定義一個棧，把pushV中的資料依次放入棧中。如果遇到放入的pushV中的資料和popV中資料相等，那麼把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;
    }
};

逆波蘭表示式求值

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

解題思路：遍歷，如果是字串中是數位，將字元數位轉化為數位後放入棧中，如果遇到運運算元，取出兩個棧頂元素，先取出的棧頂元素作為運運算元右邊的數位，後取出的作為運運算元左邊的數位，按照字串中的運運算元做運算，得到的數位再放入棧中，再遍歷陣列放入數位，以此類推。

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：返回佇列中有效元素的個數

front：返回隊頭元素的參照

back：返回隊尾元素的參照

push_back：在佇列尾部入佇列

pop_front：在佇列頭部出佇列

標準容器類deque和list滿足了這些要求。預設情況下，如果沒有為queue範例化指定容器類，則使用標準容器deque。vector類的頭刪效率太低，不能頭刪，所以不適配。

模擬實現

因為queue的介面中存在頭刪和尾插，因此使用vector來封裝效率太低，故可以藉助list來模擬實現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;

	}
}

容器介面卡

介面卡是一種設計模式(設計模式是一套被反覆使用的、多數人知曉的、經過分類編目的、程式碼設計經驗的總結)，該種模式是將一個類的介面轉換成客戶希望的另外一個介面。

雖然stack和queue中也可以存放元素，但在STL中並沒有將其劃分在容器的行列，而是將其稱為容器介面卡，這是因為stack和佇列只是對其他容器的介面進行了包裝，STL中stack和queue預設使用deque

deque簡介

deque(雙端佇列)：是一種雙開口的"連續"空間的資料結構，即可以在頭尾兩端進行插入刪除操作，且時間複雜度為O(1)。

deque不是真正完全連續的空間，而是由一段段連續的小空間拼接而成，類似於一個動態的二維陣列。

deque底層是一段假想的連續空間，實際上是分段連續的，它藉助迭代器來維護其假想連續的結構，因此deque的迭代器設計也比較複雜。

vector的缺點是當空間不夠時要擴容，會存在一定的空間浪費，頭插或中間插入需要挪動資料，效率低。優點是可以隨機存取，cpu快取記憶體命中率很高。list的缺點是無法隨機存取，cpu快取記憶體命中率低(地址不連續)。優點是可按需申請釋放空間，任意位置的插入刪除資料時間複雜度為O(1)，效率高。而deque折中了vector和list，從使用的角度，避開了它們的缺點，可以支援隨機存取，頭尾插入效率也較高，擴容時不需要挪動大量資料，效率較vector高。但deque不夠極致，隨機存取效率不如vector，任意位置插入刪除不如list，且中間插入刪除資料也很麻煩，效率不高，需要挪動整體資料，或是挪動目標buff陣列，並記錄每個buff陣列的大小。在遍歷時，deque的迭代器需要頻繁檢測是否移動到某段小空間的邊界，效率低下。所以deque比較適合頭插尾插多的情況，比如作為stack和queue的底層資料結構。stack和queue不需要遍歷（所以沒有迭代器），只需要在固定的兩端進行操作。stack中元素增長時，如果需要擴容，deque的效率比vector高；queue同理，且記憶體使用率高。

priority_queue優先順序佇列

priority_queue檔案介紹

優先佇列是一種容器介面卡，根據嚴格的弱排序標準，它的第一個元素總是它所包含的元素中最大的。

類似於堆，在堆中可以隨時插入元素，並且只能檢索最大堆元素（優先佇列中位於頂部的元素）。

優先佇列被實現為容器介面卡，即將特定容器類封裝作為其底層容器類，queue提供一組特定的成員函數來存取其元素。元素從特定容器的尾部彈出，其成為優先佇列的頂部。

底層容器可以是任何標準容器類別範本，也可以是其他特定設計的容器類。容器應該可以通過隨機存取迭代器存取，並支援以下操作：

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

標準容器類vector和deque滿足這些需求。預設情況下，如果沒有為特定的priority_queue類範例化指定容器類，則使用vector。

需要支援隨機存取迭代器，以便始終在內部保持堆結構。容器介面卡通過在需要時自動呼叫演演算法函數make_heap、push_heap和pop_heap來自動完成此操作。

priority_queue的使用

優先順序佇列預設使用vector作為其底層儲存資料的容器，在vector上又使用了對演演算法將vector中元素構造成堆的結構，因此priority_queue就是堆。注意：預設情況下priority_queue是大堆。

在OJ中的使用：

陣列中的第k個最大元素

題目描述：給定整數陣列 nums 和整數 k，請返回陣列中第 k 個最大的元素。

請注意，你需要找的是陣列排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

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

priority_queue的模擬實現

#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;
		}
	};

	//模板引數--型別
	//函數引數--物件

	//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)
		{
			//插入資料
			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;
	}
}

通過仿函數控制比較方式

如果在priority_queue中放自定義型別的資料，我們需要在自定義型別中過載>或<。如以下情形，型別T是Date*，如果不過載<或>，比較的就是地址大小。

//仿函數的變異玩法--通過仿函數控制比較方式
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;

}