【数据结构】栈、队列、堆总结

清疚 2022-05-16 04:42 198阅读 0赞

## 零、基本操作\#\# ##

/*栈的基本操作：*/
    std::stack<int> s;
    s.top();
    s.push();
    s.pop();
    s.empty();
    s.size();
    
    /*队列的基本操作：*/
    std::queue<int> q;
    q.front();
    q.push(x);
    q.back();
    q.pop();
    q.empty();
    q.size();
    /*堆的基本操作*/
    int main()
    {
    	std::priority_queue<int> big_heap;
    	std::priority_queue<int,std::vector<int>,std::greater<int> >small_heap;//创建最小堆
    	std::priority_queue<int,std::vector<int>,std::less<int> >big_heap2;//创建最大堆
    
    	if(big_heap.empty())//判断堆是否为空
    	{
    		printf("big_heap is empty!!!\n");
    	}
    
    	int test[] = {6,10,1,7,99, 4,33};
    	for(int i = 0;i< 7 ;i++)
    	{
    		big_heap.push(test[i]);//堆插入
    	}
    
    	printf("big_heap.top = %d\n",big_heap.top());//取堆顶元素
    	big_heap.push(1000);
    	printf("big_heap.top = %d\n ",big_heap.top());
    
    	for(int  i =0; i<3; i++)
    	{
    		big_heap.pop();//删除堆顶
    	}
    	printf("big_heap.top = %d \n",big_heap.top());
    	printf("big_heap.size = %d\n ",big_heap.size());//求堆中元素个数
    	return 0;
    
    }

## 一、用栈实现队列 ##

\*\*1.0题目：\*\*设计一个队列，队列支持如下操作，这些操作的算法复杂度需要的是常数级，O(1),队列的内部存储数据结构的栈，栈的方法只能包括push(),top(),pop(),size(),empty(),等标准的栈方法；  
\*\*1.1算法思想：\*\*使用一个临时栈，一个数据栈，先将所有元素入数据栈中，当数据栈不为空时，将数据栈中所有元素按顺序弹入临时栈，再将临时栈弹入数据栈即可。  
**1.2程序实现**

#include<iostream>
    #include<stack>
    using namespace std;
    class Myqueue
    {
    public:
    
    	void push(int x)
    	{
    		std::stack<int> temp;
    		while(!_data.empty())
    		{
    			temp.push(_data.top());
    			_data.pop();
    		}
    		temp.push(x);
    		while(!temp.empty())
    		{
    			_data.push(temp.top());
    			temp.pop();
    		}
    	}
    	
    	int pop()
    	{
    		int x = _data.top();
    		_data.pop();
    		return x;
    	}
    
    	int front()
    	{
    		return _data.top();
    	}
    
    	bool empty()
    	{
    		return _data.empty();
    	}
    
    	std::stack<int> _data;
    };
    
    
    
    int main()
    {
    	Myqueue Q;
    	Q.push(111);
    	Q.push(222);
    	Q.push(333);
    	Q.push(444);
    	Q.push(555);
    	Q.push(666);
    	Q.push(777);
    	Q.push(888);
    	printf("%d\n",Q.front());
    
    	Q.pop();
    	printf("%d\n",Q.front());
    
    	Q.pop();
    	Q.pop();
    	Q.pop();
    	printf("%d\n",Q.front());
    	
    	printf("%d\n",Q.empty());
    	Q.pop();
    	Q.pop();
    	Q.pop();
    	Q.pop();
    
    	printf("%d\n",Q.empty());
    
    	return 0;
    }

**1.3结果展示**  
![70][]

## 二、用队列实现栈 ##

**2.0题目**设计一个栈，支持如下操作，这些操作算法复杂度需要的时常数阶，O(1),栈的内部存储数据的结构为队列，队列的方法只能包括push()、peek()(front())、pop()、size(),empty()等标准的队列方法；  
\*\*2.1算法思想：\*\*使用一个临时队列，一个数据队列，先将要遍历的某个元素入临时队列，再将数据队列中所有元素入临时队列，当临时队列不为空时，再将临时栈弹入数据栈即可。  
**2.2程序实现**

#include<iostream>
    #include<queue>
    using namespace std;
    class Mystack
    {
    public:
    	void push(int x)
    	{
    		std::queue<int> temp;
    		temp.push(x);
    		while(!_data.empty())
    		{
    			temp.push(_data.front());
    			_data.pop();
    		}
    
    		while(!temp.empty())
    		{
    			_data.push(temp.front());
    			temp.pop();
    		}
    
    	}
    
    	int pop()
    	{
    		int x = _data.front();
    		_data.pop();
    		return x;
    	}
    
    	int top()
    	{
    		return _data.front();
    	}
    
    	bool empty()
    	{
    		return _data.empty();
    	}
    	std::queue<int> _data;
    };
    
    
    int main()
    {
    	Mystack s;
    	s.push(10);
    	s.push(20);
    	s.push(30);
    	s.push(40);
    	s.push(50);
    	s.push(60);
    	s.push(70);
    	s.push(80);
    	printf("%d\n" , s.top());
    
    	s.pop();
    	s.pop();
    	s.pop();
    	printf("%d\n" , s.top());	
    	s.pop();
    	printf("%d\n" , s.top());	
    	
    	printf("%d\n" , s.empty());	
    	s.pop();
    	s.pop();
    	s.pop();
    	s.pop();
    	printf("%d\n" , s.empty());	
    	return 0;
    }

**2.3结果展示**  
![70 1][]

## 三、包含min的栈 ##

\*\*3.1题目：\*\*设计一个栈，支持如下操作，这些操作的算法复杂度需要的是常数级，O(1)  
（1）push(x)  
（2）pop()  
（3）top()  
（4）getMin()  
\*\*3.2算法思想：\*\*设置两个栈，一个数据栈一个最小值栈，每次在往数据栈中压入元素时，将其与最小值栈的栈顶作比较，将较小的保存在最小值栈中，这样一来，最小值栈栈顶将保留所有元素中的最小值，在查找时，直接取最小值栈的栈顶即可。  
**3.3程序实现**

#include<iostream>
    #include<stack>
    using namespace std;
    
    class MinStack
    {
    public:
        MinStack() 
    	{
        }
    	 void push(int x)
    	{
        	_data.push(x);
        	if (_min.empty())
    		{
    	    	_min.push(x);
    	    }
    
    		  else 
    			  {
    				  if(x > _min.top())
    		            {
    		  	          x = _min.top();
    		              }
    			        _min.push(x);
    	             }
            	}
    
    	void pop()
    	{
    		_data.pop();
    		_min.pop();
    	}
    
    	int top()
    	{
    		return _data.top();
    	}
    
    	int getMin()
    	{
    		return _min.top();
    	}
    
    private:
    	std::stack<int>  _data;
    	std::stack<int>  _min;
    };
    
    
    int main()
    {
    	MinStack s;
    	s.push(3);
    	printf("%d\n",s.top());
    	printf("%d\n",s.getMin());
    
    	s.push(4);
    	printf("%d\n",s.top());
    	printf("%d\n",s.getMin());
    
    	s.push(-77);
        printf("%d\n",s.top());
    	printf("%d\n",s.getMin());
    	
    	s.push(100);
    	printf("%d\n",s.top());
    	printf("%d\n",s.getMin());
    
    	return 0;
    }

**3.4结果展示**  
![70 2][]

## 四、合法的出栈序列 ##

\*\*4.1题目:\*\*给出一个序列1，判断该序列1是否为某个已知序列2的出栈序列；  
\*\*4.2算法思想:\*\*将带带判断的序列存入一个队列中，将已知序列依次压入栈中，每次压入时，将其与队头元素比较，如果相等，就将队头弹出，将栈顶弹出，如果不等，就继续入站，循环以上操作。  
**4.3程序实现**

#include<iostream>
    #include<queue>
    #include<stack>
    using namespace std;
    
    bool Is_correct_order(std::queue<int> &order)
    {
    	std::stack<int> s;
    	for(int  i = 1; i<order.size();++i)
    	{
    		s.push(i);
    		while(!s.empty()&& s.top()==order.front())
    		{
    			order.pop();
    			s.pop();
    		}
    	}
    	if(!s.empty())
    	{
    		return false;
    	}
    	return true;
    }
    
    int main(){
    	int n;
    	int train;
    	scanf("%d", &n);
    	while(n){
    		scanf("%d", &train);
    		while (train){
    			std::queue<int> order;
    			order.push(train);
    			for (int i = 1; i < n; i++){
    				scanf("%d", &train);
    				order.push(train);
    			}
    			if (Is_correct_order(order)){
    				printf("Yes\n");
    			}
    			else{
    				printf("No\n");
    			}
    			scanf("%d", &train);
    		}
    		printf("\n");
    		scanf("%d", &n);
    	}
    	return 0;
    }

**4.4结果展示**  
![70 3][]

## 五、实现简单的计算器 ##

\*\*5.1题目：\*\*设计一个简单的计算器，输入一个字符串存储的数据表达式，可以计算包括“（”，“）”，“+”，“-”四种符号的数学表达式，输入的数学表达式字符串保证是合法的，输入的数学表达式中可能存在空格字符  
\*\*5.2算法思想：\*\*维护两个栈，一个存放数字字符，一个存放符号，设计一个标记，每次当遇到"+“或者”-"时，将标记设置为1，将计算结果保存在数字栈中，当遇到”（“时，则不计算，直到将表达式所有的元素都处理完。;  
**5.3程序实现**

#include<iostream>
    #include <string>
    #include <stack>
    using namespace std;
    
    class Solution 
    {
    public:
    	int calculate(std::string s)
    	{
    		static const int STATE_BEGIN = 0;
    		static const int NUMBER_STATE = 1;
    		static const int OPERATION_STATE = 2;
    		std::stack<int> number_stack;
    		std::stack<char> operation_stack;
    		int number = 0;
    		int STATE = STATE_BEGIN;
    		int compuate_flag = 0;
    
    		for (int i = 0; i < s.length(); i++)
    		{
    			if (s[i] == ' ')
    			{
    				continue;
    			}
    			switch(STATE)
    			{
    			case STATE_BEGIN:
    				if (s[i] >= '0' && s[i] <= '9')
    				{
    					STATE = NUMBER_STATE;
    				}
    				else{
    					STATE = OPERATION_STATE;
    				}
    				i--;
    				break;
    			case NUMBER_STATE:
    				if (s[i] >= '0' && s[i] <= '9')
    				{
    					number = number * 10 + s[i] - '0';
    				}
    				else{
    					number_stack.push(number);
    					if (compuate_flag == 1)
    					{
    						compute(number_stack, operation_stack);
    					}
    					number = 0;
    					i--;
    					STATE = OPERATION_STATE;
    				}
    				break;
    			case OPERATION_STATE:
    				if (s[i] == '+' || s[i] == '-')
    				{
    					operation_stack.push(s[i]);
    					compuate_flag = 1;
    				}
    				else if (s[i] == '(')
    				{
    					STATE = NUMBER_STATE;
    					compuate_flag = 0;
    				}
    				else if (s[i] >= '0' && s[i] <= '9')
    				{
    					STATE = NUMBER_STATE;			  		
    					i--;
    				}
    				else if (s[i] == ')'){
    					compute(number_stack, operation_stack);
    				}
    				break;
    			}
    		}
    		if (number != 0)
    		{
    			number_stack.push(number);
    			compute(number_stack, operation_stack);
    		}
    		if (number == 0 && number_stack.empty())
    		{
    			return 0;
    		}
    		return number_stack.top();
    	}
    private:
    	void compute(std::stack<int> &number_stack,
    		std::stack<char> &operation_stack)
    	{
    		if (number_stack.size() < 2)
    		{
    			return;
    		}
    		int num2 = number_stack.top();
    		number_stack.pop();
    		int num1 = number_stack.top();
    		number_stack.pop();
    		if (operation_stack.top() == '+')
    		{
    			number_stack.push(num1 + num2);
    		}
    		else if(operation_stack.top() == '-')
    		{
    			number_stack.push(num1 - num2);
    		}
    		operation_stack.pop();
    	}
    };
    
    int main()
    {	
    	std::string s = "1+121 - (14+(5-6) )";
    	Solution solve;
    	printf("%d\n", solve.calculate(s));
    	return 0;
    }

**5.4结果展示**  
![70 4][]

## 六、求第K大数字 ##

\*\*6.1题目：\*\*\*已知一个未排序的数组，求这个数组中第K大的数字  
**6.2算法思想**维护一个k个元素的最小堆，遍历序列中的每一个元素，使其与根节点比较，如果小于根节点，则丢弃如果大于根节点，则插入堆中，并删除根节点；直到遍历完所有元素，根节点即为第K大节点  
**6.3程序实现**

#include<iostream>
    using namespace std;
    
    class solution 
    {
    public:
    	int FindKlargest(std::vector<int>& nums,int k)
    	{
    		std::priority_queue<int,std::vector<int>,std::greater<int>> less_heap;
    		for(int  i =0; i <nums.size();i++)
    		{
    			if(less_heap.size()<k)
    			{
    				less_heap.push(nums[i]);
    			}
    			else
    				if(less_heap.top()<nums[i])
    				{
    					less_heap.pop();
    					less_heap.push(nums[i]);
    				}
    		   
    		 }
    		return less_heap.top();
    	}
    
    };
    
    
    int main()
    {
    
    	std::vector<int> nums;
    	nums.push_back(3);
    	nums.push_back(14);
    	nums.push_back(11);
    	nums.push_back(2);
    	nums.push_back(22);
    	nums.push_back(67);
    	nums.push_back(88);
    	nums.push_back(90);
    	solution solve ;
    	printf("%d\n",solve.FindKlargest(nums,2));
    	return 0;
    }

**6.4结果展示**  
![70 5][]

## 七、寻找中位数 ##

\*\*7.1题目：\*\*设计一个数据结构，该数据结构动态的维护一组数据，且支持如下操作：  
1、添加元素：将整型num添加至数据结构中；  
2、返回数据中位数，返回其维护的数据的中位数；  
中位数定义：  
1、若数据个数为奇数，中位数为该组数排序后中间的数。如：1,2,3,—》2  
2、若数据个数为偶数，中位数是该组数排序后中间的两个数字的平均值；如1,2,3,4—》2.5

**7.2算法思想**维护一个最大堆和最小堆；  
（1）最小堆的堆顶大于最大堆的堆顶  
（2）最小堆和最大堆元素个数之差不大于1；  
（3）每遍历一个元素将其与最大堆的堆顶进行比较；  
【1】最大堆，最小堆元素个数相等时，如果当前遍历的元素大于最大堆堆顶元素，则插入最小堆内  
否则插入最大堆内  
【2】最大堆，最小堆元素个数不相等时，  
最大堆元素个数大于最小堆元素：  
1）当前元素大于最大堆对顶元素，则插入最小堆内  
2）当前元素小于最大堆堆顶元素，则将最大堆堆顶插入最小堆，  
将当前元素插入最大堆  
最大堆元素个数小于最小堆元素：  
1）当前元素小于最大堆对顶元素，则插入最大堆内  
2）当前元素大于最大堆堆顶元素，则将最小堆堆顶插入最大堆，  
将当前元素插入最小堆  
**7.3程序实现**

#include<iostream>
    #include<queue>
    using namespace std;
    class MedianFinder
    {
    public:
    
    	void addNum(int num)
    	{
    		if(big_heap.empty())
    		{
    			big_heap.push(num);
    			return ;
    		}
    
    		if(big_heap.size() == small_heap.size())
    		{
    			if(num < big_heap.top())
    			{
    				big_heap.push(num);
    			}
    			else
    				small_heap.push(num);
    		}
    
    		else if(big_heap.size()>small_heap.size())
    		{
    			if(num>big_heap.top())
    				small_heap.push(num);
    			else {
    				small_heap.push(big_heap.top());
    				big_heap.pop();
    				big_heap.push(num);
    			}
    		}
    
    		else if(big_heap.size()<small_heap.size())
    		{
    			if(num <small_heap.top())//
    				big_heap.push(num);
    			else
    			{
    				big_heap.push(small_heap.top());
    				small_heap.pop();
    				small_heap.push(num);
    			}
    		}
    	}
    	double findMedian()
    	{
    		if(big_heap.size()==small_heap.size())
    		{
    			return (big_heap.top()+small_heap.top())/2;
    		}
    		else if(big_heap.size()>small_heap.size())
    		{
    			return big_heap.top();
    		}
    		else return small_heap.top();
    
    	}
    
    	std::priority_queue<int,std::vector<double>,std::greater<double>> small_heap;
    	std::priority_queue<int,std::vector<double>,std::less <double>>  big_heap;//注意
    };
    int main()
    {
    	MedianFinder M;
    	M.addNum(2);
    	M.addNum(1);
    
    	printf("%lf\n",M.findMedian());
    
    	M.addNum(4);
    	printf("%lf\n",M.findMedian());
    
    	M.addNum(3);
    	printf("%lf\n",M.findMedian());
    	return 0;
    }

**7.4结果展示**  
![70 6][]

[70]: /images/20220516/4f724e3103ad4e0998ee9caee25477ec.png
[70 1]: /images/20220516/91d8bbe9d49c41d0afd2a6e45aecb5ce.png
[70 2]: /images/20220516/94797bfc6fc7437684ba1e7ea78d5e0c.png
[70 3]: /images/20220516/f2770c72dc1d4697a45b8777d05742a3.png
[70 4]: /images/20220516/5629cb72f30a4571b60fe6aecf7f26c1.png
[70 5]: /images/20220516/7319f80ac7834bb89951a0e24811c51f.png
[70 6]: /images/20220516/0c6c9ed7ae2744208819eec35f589eac.png