栈-队列

AcWing 828. 模拟栈

模板题：

实现一个栈，栈初始为空，支持四种操作：

1. push x – 向栈顶插入一个数 x；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 MM 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

1≤M≤1000001≤M≤100000,
1≤x≤1091≤x≤109
所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

模拟栈的实现：

• 栈的特性：先进后出，后出先进；
• push x ：栈顶所在索引往后移动一格，然后放入x。add[++t] = x；
• pop : top 往前移动一格。-- t；
• empty ：top 大于等于 0 栈非空，小于 0 栈空。top == -1 ? “YES” : “NO”；
• query ： 返回栈顶元素。st[top]；

AC代码

#include<iostream>
using namespace std;
const int D=100015;
int add[D],t;  //add[D]相当于一个栈，t就是一个"滑轮"：实现增删操作；
int main(){
    int n; //初始化
    cin >> n;
    string s;
    int m;
    while(n--){
        cin >> s;
        //这里实现把数值压入栈中:“++t"开辟一个空间，把值赋上
        if(s=="push"){
            cin >> m;
            add[++t]=m;
        //
        }else if(s=="pop"){
            --t;           //这里同理：直接删除这个空间；
        }else if(s=="query"){
            cout << add[t] << endl; //直接输出(一系列的操作，滑轮停到那就输出啥)
        }else if(s=="empty"){
            if(t>0){                
                cout << "NO" << endl;//有值就不为'No'，无输出'YES';
            }else{
                cout << "YES" << endl;
            }
        }
    }
}

AcWing 829. 模拟队列

模板题：

实现一个队列，队列初始为空，支持四种操作：

1. push x – 向队尾插入一个数 x；
2. pop – 从队头弹出一个数；
3. empty – 判断队列是否为空；
4. query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式

第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

1≤M≤1000001≤M≤100000,
1≤x≤1091≤x≤109,
所有操作保证合法。

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

解题思路：

队列：队尾入队，对头出队；先进先出，后进后出；

图解 ：

先定义数组 e[n] 保存数据；定义一个 hh 代表队头，e[hh]就代表对头元素，e[hh+1]是第二个出队的元素；

在定义一个 tt 代表队尾，e[tt]就是队尾元素，e[tt+1]是第二个队尾插入的元素；

这个就跟单链表思想是一致的，刚开始让要插入的元素指向“-1”，进行删除的时候，指向这个节点的后一个节点就好了；

咱们举个例子：队列中的元素 2 3 4 5 我现在要删除 “ 2 ” 咱们是不是只需要记录 “2” 对头的后一个元素就好了，就在下一次的 query 操作输出e[hh]就好了，hh 就只要负责 ++ 移到后一个数；

咱们要做的只是模拟，并不是向真正的数据结构一样，实现删除操作，咱们只需要做好模拟的事，不需要考虑它数值移到哪去了

AC代码

#include<iostream>
using namespace std;
const int N=100015;
//这里的tt也可以定义0,那尾插就是tt++,hh<tt了(看个人习惯)
int e[N],hh,tt=-1;//hh对头，tt队尾
int main(){
    int n;
    cin >> n;
    string s;
    int m;
    while(n--){
        cin >> s;
        if(s=="push"){
            cin >> m;
            e[++tt]=m;
        }else if(s=="pop"){
            hh++;
        }else if(s=="query"){
            cout << e[hh] << endl;
        }else if(s=="empty"){
            if(hh<=tt){
                cout << "NO" << endl;
            }else cout << "YES" << endl;
        }
    }
}    

栈：表达式求值

实现栈思想例题：

给定一个表达式，其中运算符仅包含 +,-,*,/（加 减 乘 整除），可能包含括号，请你求出表达式的最终值。

注意：

• 数据保证给定的表达式合法。
• 题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
• 题目保证表达式中所有数字均为正整数。
• 题目保证表达式在中间计算过程以及结果中，均不超过 231−1231−1。
• 题目中的整除是指向 00 取整，也就是说对于大于 00 的结果向下取整，例如 5/3=15/3=1，对于小于 00 的结果向上取整，例如 5/(1−4)=−15/(1−4)=−1。
• C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 105105。

输入样例：

(2+2)*(1+1)

输出样例：

8

栈引导：

• 现在给出一列算式 ：

算式：1+1+1*5*6   //理解这一步：我们应该先算乘法嘛？这里也可以看出，即使先算乘法，也不会影响 “1+1” 要执      =32                                                                           行这一步

• 那知道这个特殊情况：上图解 ：
  
  

解析：（1）如果栈顶是+，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；

     （2）如果栈顶是+，即将入栈的是*，栈顶优先级低，直接入栈；

     （3）如果栈顶是*，即将入栈的是+，栈顶优先级高，需要先计算，再入栈；

     （4）如果栈顶是*，即将入栈的是*，栈顶优先级高，需要先计算，再入栈；

• i=j-1;问题

例子：2*10-10000+24-(5*3)+(3*2)   //在i=j-1之前的循环中，遍历‘10’就让，已经是甩开i了；
     就是说：i下标2指向数值‘1’的时候，j已经遍历完了‘10’，如果直接让j=i的话，就会跳过一些数值，
     实际情况自己模拟一下就知道了

AC代码

#include<iostream>
#include<algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
const int N=100010;

//栈的特性:后进先出
stack<int> value;     //定义一个栈容器：用来存储int型数值
stack<char> symbol;   //定义一个栈容器：用来存储char型字符

//unordered_map：使用哈希表来实现。它通过哈希函数将键映射到表中的位置，
//从而快速访问、插入和删除元素。由于哈希表的特性，unordered_map 不保证元素按照任何特定的顺序存储。
unordered_map<char, int> p{{'+',1},{'-',1},{'*',2},{'/',2}};

void add(){
   //第二个入栈元素赋值
   int a=value.top();
   value.pop();

   //第一个入栈元素
   int b=value.top();
   value.pop();

   //提取符号操作
   char op=symbol.top();
   symbol.pop();

   //进行一个计算操作
   int ans=0;
   if(op=='+') ans=b+a;
   //为什么是b-a？ 这里就要明白栈的特性了
   if(op=='-') ans=b-a;
   if(op=='*') ans=b*a;
   if(op=='/') ans=b/a;

   //完成操作再次压入栈中，进行下一步运算
   value.push(ans); 
}

int main(){
   string s;
   cin >> s;
   int len=s.size();
   for(int i=0;i<len;i++){
      //isdigit:C 库函数 int isdigit(int c) 检查所传的字符是否是十进制数字字符。
      if(isdigit(s[i])){
         int x=0,j=i;
         //这里使用循环就是看看数值字符型是几位数，毕竟10都占两位，所以要循环
         while(j<len && isdigit(s[j])){ 
            x=x*10+s[j]-'0';
            j++;
         }
         value.push(x);
         i=j-1;                       
      }else if(s[i]=='('){
         symbol.push(s[i]);
      }else if(s[i]==')'){
         while(symbol.top()!='('){
            add();
         }
         symbol.pop();
      }else {
         if(!symbol.empty() && p[symbol.top()]>=p[s[i]]){ //判断栈顶元素优先级大于新运算符
            add();
         }
         symbol.push(s[i]);
      }
   }
   //判断运算栈是否为空，不为继续运算
   while(!symbol.empty()) add();
   cout << value.top();
}