数据结构第二章-栈 队列 堆
预备知识：栈和队列
#栈和队列的相关知识
STL stack标准栈的相关知识
stack标准栈的语句
.top()取出栈顶.empty()判断是否为空.push(x)将x添加至栈.pop()弹出栈顶.size()栈的存储元素个数 ![[Pasted image 20230630151525.png]]
STL queue队列的相关知识
queue的相关语句
.empty判断是否为空.front()返回队列头部元素.back()返回队列尾部元素.pop()弹出队列头部元素.push(x)将x添加至队列.size()返回队列的存储元素的个数
使用队列实现栈
#easy 设计一个栈，支持基本的栈操作，这个栈的内部存储数据的结构是队列，队列的方法只能用_标准的队列方法_225. 用队列实现栈 - 力扣（LeetCode）
思考
相当于两个队列互相倒腾
**解决思路如下**
class MyStack {
public:
MyStack() {
//临时队列，利用该队列进行原始data_queue元素
//与新元素的次序调换
}
void push(int x) {
std::queue<int> temp_queue;
temp_queue.push(x); //新元素push进入临时队列
while(!_data.empty()){//只要_data数据队列不空就循环
temp_queue.push(_data.front());//原队列内容push进入临时队列
_data.pop();
}
while(!temp_queue.empty()){//只要_temp_queue不空就循环
_data.push(temp_queue.front());//临时队列所有元素push进入数据队列
temp_queue.pop();
}
}
int pop() {
int x = _data.front();//取出栈顶元素，即队列头部元素
_data.pop();//弹出队列头部元素
return x;//返回取出的头部元素x，即栈顶元素
}
int top() {
return _data.front();//栈顶元素即为队列头部元素
}
bool empty() {
return _data.empty();
}
private:
std::queue<int>_data;//_data数据队列存储元素的顺序就是存储元素的顺序
};
用栈实现队列
[[链表，栈，队列，堆的补充内容#使用栈实现队列（方法2 双栈法）|第二个方法（更好）]] #easy 232. 用栈实现队列 - 力扣（LeetCode）
主要思路也是两边互相倒腾
解决方法如下
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
std::stack<int>temp_stack;
while(!_data.empty()){//只要_data数据不空
temp_stack.push(_data.top());//把_data里面数据放进临时栈
_data.pop();
}
temp_stack.push(x);
while(!temp_stack.empty()){//只要临时栈不空
_data.push(temp_stack.top());
temp_stack.pop();
}
}//弹出队列头部元素并返回
int pop() {
int x = _data.top();
_data.pop();//把栈顶储存至x
return x;//弹出栈顶并返回x
}
int peek() {
return _data.top();
}
bool empty() {
return _data.empty();
}
private:
std::stack<int> _data;
};
包含min函数的栈
#medium 155. 最小栈 - 力扣（LeetCode） 复杂度要求是常数级，O(1) 除了普通栈操作之外还需要有一个getMin() 方法来返回栈内最小元素 
O(1)级别的难度就意味着不能进行遍历或者排序操作（因为复杂度是0（n)级）
解决方法如下
class MinStack {
public:
MinStack() {
}
void push(int val) {
_data.push(val);//数据压入数据栈
if(_min.empty()){//如果小于，val进入最小值栈
_min.push(val);
}
else{
if(val > _min.top()){//如果大于，就更新val为最小值栈顶，在push到最小值栈顶
val = _min.top();
}
_min.push(val);//把xpush进入最小值栈
}
}
void pop() {
_data.pop();//数据栈和最小值栈同时弹出
_min.pop();
}
int top() { //top即返回数据栈顶
return _data.top();
}
int getMin() {//返回最小值栈栈顶
return _min.top();
}
private:
std::stack<int>_data;
std::stack<int>_min;
};
合法的出入栈队列
#medium 这TMD是M题？？
1363 -- Rails (poj.org) 已知1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可以在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法
输入与输出样例
Input
The input consists of blocks of lines. Each block except the last describes one train and possibly more requirements for its reorganization. In the first line of the block there is the integer N described above. In each of the next lines of the block there is a permutation of 1, 2, ..., N. The last line of the block contains just 0.
The last block consists of just one line containing 0.
Output
The output contains the lines corresponding to the lines with permutations in the input. A line of the output contains Yes if it is possible to marshal the coaches in the order required on the corresponding line of the input. Otherwise it contains No. In addition, there is one empty line after the lines corresponding to one block of the input. There is no line in the output corresponding to the last ``null'' block of the input.
Sample Input
5
1 2 3 4 5
5 4 1 2 3
0
6
6 5 4 3 2 1
0
0
Sample Output
Yes
No
Yes
以下是例子，怕你看不懂
思路
以下是合法序列
以下是不合法序列
解决方法如下
bool check_is_valid_order(std::queue<int>&order){//检查队列
std::stack<int> S;//S为模拟栈
int n = order.size();//n为序列长度 ,将1到n按顺序入栈
for(int i = 1;i<=n;i++){ //进入车站的车厢都是1到n
S.push(i);
while(!S.empty()&&order.front() == S.top()){
S.pop();
order.pop();
}
}
if(!S.empty()){ //如果S不为空，为不合法的序列
return false;
}
return true;
}
BTW,由于poj没有测试代码需要自己写，所以附上测试代码
int main(){
int n;
int train;
scanf("%d",&n); //输入元素的数量
while(n){
scanf("%d",&train);//输入的序列
while(train){//每次读取一个train就push到order里面
std::queue<int> order;
order.push(train);
for(int i =1;i<n;i++){//读入后面n-1个元素
scanf("%d",&train);
order.push(train);
}
if(check_is_valid_order(order)){//对序列进行判断
printf("Yes\n");
}
else{
printf("No\n");
}
scanf("%d",&train);//下一次序列的第一个train，同时通过这个trian来判断是否为结束判断
}
printf("\n");
scanf("%d",&n);//下一次序列的第一个n，通过这个n来判断程序是否终止
}
return 0;
}
简单的计算器
一点都不简单
#hard 224. 基本计算器 - 力扣（LeetCode） 设计一个计算器，输入一个字符串存储的数学表达式，可以计算包括（）+-四种符号的数学表达式，输入的数学表达式字符串保证是合法的，数学表达式可能存在空格字符
计算器算法到底是什么
思路大概了解了，那怎么把字符串转换成整形呢？ 思路如下，利用ASCII码相减
在题目中的实现思路——有限状态自动机 什么是状态机？ 如下：
注意由O到N状态转换的时候那个括号是"("而不是")""，图画错了
解决方法如下
有限状态机部分
class Solution {
public:
int calculate(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;
long number = 0;
int STATE = STATE_BEGIN;
int compuate_flag = 0 ;
for(int i = 0; i<s.length();i++){//扫描整个字符串
if(s[i]==' '){//如果空
continue;
}
if (s[i] == '-' && i == 0) {//判断第一个字符是不是负号
//因为如果第一个字符是负号而整个式子里面没有括号的话，会把-号视为一个操作，但没有其他数字与他相减，导致错误的返回结果
number_stack.push(0);//如果是，就在开头插入一个0用来相减。
}
switch(STATE){//有限状态自动机
case STATE_BEGIN:
if(s[i]>='0'&&s[i]<='9'){//如果是0-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{//当遇到空格，即循环到continue的时候，i指针指的位置是空格
number_stack.push(number);
if(compuate_flag == 1){//计算
compute(number_stack,operation_stack);
}
number = 0;//复位
i--;//退格
STATE = OPERATION_STATE;//切换状态
}
break;
case OPERATION_STATE://O状态的四种情况
if(s[i] == '+'||s[i]=='-'){//遇到+-可以计算并push进栈
operation_stack.push(s[i]);
compuate_flag = 1;
}
else if(s[i]=='('){//遇到（不能计算转换回N状态
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就是最后的字符，这时候让number直接入栈计算即可
number_stack.push(number);
compute(number_stack,operation_stack);
}
if(number==0&&number_stack.empty()){
return 0;
}
return number_stack.top();//返回栈顶
}
};
计算（compute)函数
void compute(std::stack<int> &number_stack,std::stack<char>&operation_stack){
if(number_stack.size() < 2){
return ; //处理特殊数据 ，比如（1234）
}
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);//push结果
}
else if(operation_stack.top() == '-'){
number_stack.push(num1-num2);
}
operation_stack.pop();
}
关于
if (s[i] == '-' && i == 0) {//判断第一个字符是不是负号
//因为如果第一个字符是负号而整个式子里面没有括号的话，会把-号视为一个操作，但没有其他数字与他相减，导致错误的返回结果
number_stack.push(0);//如果是，就在开头插入一个0用来相减。
}
语句的解释: 本来的计算器无法计算开头的-号，比如计算-2 +1 当 遇到-号之后进入OPERATION_STATE,把compuate_flag设置为1之后指向2开始计算，但是栈里面只有一个数字，会把他当成一个无效字符无法计算，到最后数字栈的是 1，2 ，操作栈是+ - 操作完一次+之后 数字栈里面就只有3 ，操作栈只有-，所以输出的结果是3，无法进行计算。
预备知识：二叉堆的属性
STL优先级队列
为什么二叉堆的名字叫优先级队列？？
greater是大于的比较类，less是小于的比较类
图里有错，优先级队列的名字是std::priority_queue 里面有_ 二叉堆的操作
.empty()判断堆是否为空 .pop()弹出堆顶元素（最大值） .push(x) 把元素插入二叉堆 .top() 返回堆顶最大值 .size()返回堆中元素个数
堆的应用 数组中第K大的数字
#easy 215. 数组中的第K个最大元素 - 力扣（LeetCode） 如果先排列然后再返回第k个位置的话返回的话实现复杂度是O($n*\log{n}$) BTW排序算法的平均时间复杂度就是O（$n*\log{n}$)
利用最小堆的思路 
时间复杂度是O($N*\log{k}$)
解决方法如下
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
std::priority_queue<int,std::vector<int>,std::greater<int>> Q;//定义最小堆
for(int i = 0;i<nums.size();i++){//遍历nums数组
if(Q.size()< k){//如果堆中元素小于k，直接push
Q.push(nums[i]);
}
else if(nums[i]>Q.top()){//如果堆顶比新元素小就弹出
Q.pop();
Q.push(nums[i]);//push进新元素（替换堆顶）
}
}
return Q.top();//返回堆顶
}
};
寻找中位数
#hard 295. 数据流的中位数 - 力扣（LeetCode） 设计一个·数据结构，动态维护一组数据，支持添加元素和返回数据的中位数 中位数定义：
- 若数据个数为奇数，中位数是该组排序后中间的数
- 若数据个数为偶数 ，中位数是该组数排序后中间两个数字之间的平均值
最直观的方法
存储结构使用数组 每次添加元素或查找中位数时候对数组排序，再计算结果。 时间复杂度：O($n^2$)或者O($n^2 *\log{n}$) 因为添加元素或查询中位数是随机的
利用堆的性质
添加元素 
如何获取中位数 
解决办法如下
class MedianFinder {
public:
MedianFinder() {
}
std::priority_queue<int,std::vector<int>,std::greater<int>> small_queue;//small_queue最小堆
std::priority_queue<int> big_queue;//big_queue最大堆
void addNum(int num) {//加数字
if(big_queue.empty()){
big_queue.push(num);
return;
}
if(big_queue.size() == small_queue.size()){//两边个数相等
if(num<big_queue.top()){
big_queue.push(num);
}
else{
small_queue.push(num);
}
}
else if(big_queue.size()>small_queue.size()){//两边个数不等
if(num>big_queue.top()){//刚好往少的堆里面加元素
small_queue.push(num);
}
else{//往大的元素里面添加元素
small_queue.push(big_queue.top());//把大堆头放进小堆
big_queue.pop();
big_queue.push(num);//把数字压入大堆
}
}
else if(big_queue.size()<small_queue.size()){//和上面类似
if(num<small_queue.top()){
big_queue.push(num);
}
else {
big_queue.push(small_queue.top());
small_queue.pop();
small_queue.push(num);
}
}
}
double findMedian() {//查找中位数
if(small_queue.size() == big_queue.size()){//两边大小相等各取一半
return(big_queue.top()+small_queue.top())/2.0;//别忘除以2.0，要是除以2就变成整除了
}
else if(small_queue.size()>big_queue.size()){//谁多取谁
return small_queue.top();
}
return big_queue.top();
}
};
下课啦！！
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 name1110
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果