数据结构第三讲栈与队列

第三讲栈与队列

理解！理解！理解！

记得看清楚 题目条件

1. 栈和队列的基本概念

2. 栈和队列的顺序存储结构

lj 理解为主，用猪头打游戏的男人，hhhh

(1) 栈：栈顶元素位置：指向最后一个元素、指向最后一个元素的下一个位置
    stk[N]
    指向最后一个元素  // top = -1
    // 添加
    stk[++top] = 1;
    // 删除
    top--;
    //栈顶
    stk[top]

    指向最后一个元素的下一个位置 // top = 0;
    // 添加
    stk[top++] = 1;
    // 删除
    top--;

    // 返回栈顶
    stk[top-1]

    // 判断是否为空
    top == 0  // top==初始值

(2) 队列：一般采用 循环队列 。
    (a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。
    (b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。
    p[N]
    // front rear

    1.front=0 第一个元素，rear=0 最后一个元素的下一个元素
    // 判空 
    front == rear
    // 队满
    front = (rear+1)%N

    // 插入 
    q[rear++] = 1;
    rear %= N

    // 弹出
    front = (front + 1 )%N;

    // 弹出队头
    q[front]

2.front 第一个元素，rear=-1 最后一个元素
// 判空 
front == (rear+1)%N;
// 队满
front = (rear+2)%N

// 插入 
q[++rear] = 1;
rear %= N

// 弹出
front = (front + 1 )%N;

// 弹出队头
q[front]

3. 栈和队列的链式存储结构

栈

头插和头删

top指向第一个元素

队列

front 第一个元素

rear 最后一个元素的下一个元素

4. 栈和队列的应用

(1) 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS

DFS // 套娃？？ 画树图来理解 计算机用栈来维护  深搜
不撞南墙不回头

表达式求值（中缀表达式转后缀表达式、括号匹配）

重要！！！！！！必考。

理解背，模板题

 AcWing 3302. 表达式求值
笔试要求：

过程，选择题经常考

往年并没考大题，今年可能。

一个栈存符号（ +-*/ 加减符号优先级）

一个栈存数字

王道书解法：

王道P91-92 11题

双栈：运算符栈和操作数栈
那么操作符优先级怎么定义呢？
优先级分为栈内优先级（in stack priority）isp 和 栈外优先级（in coming priority）icp
isp[op]表示该操作符op在栈内的优先数, icp[op]表示该操作符op在栈外的优先数,

对于isp和icp可以用一个map存储 char 到 int 的映射

ps：a+b-a*((c+d)/e-f)+g：

按照王道书写：

#include<iostream>
#include<map>
#include<stack>
using namespace std;
map<char, int> isp, icp;
const char opers[6] = {'+', '-', '*', '/', '(', ')'};
const int isps[6] = {3, 3, 5, 5, 1, 6}, icps[6] = {2, 2, 4, 4, 6, 1};
void init() {
    for(int i = 0; i < 6; ++i) isp[opers[i]] = isps[i], icp[opers[i]] = icps[i];
}

void calc(stack<char>& ops, stack<int>& nums) {
    int b = nums.top(); nums.pop();
    int a = nums.top(); nums.pop();
    char op = ops.top(); ops.pop();
    int t;
    if(op == '+') t = a + b;
    else if(op == '-') t = a - b;
    else if(op == '*') t = a * b;
    else t = a / b;
    nums.push(t);
}

int calculate(string s) {
    s = "(" + s + ")";
    stack<char> ops;
    stack<int>  nums;
    int n = s.size();
    for(int i = 0; i < n; ++i) {
        if('0' <= s[i] && s[i] <= '9') {
            int t = s[i] - '0';
            for(int j = i + 1; j < n; ++j) {
                if('0' <= s[j] && s[j] <= '9') t = t * 10 + (s[j] - '0');
                else {
                    i = j - 1;
                    nums.push(t);
                    break;
                }
            }
        } else if(s[i] == ' ') continue;
        else {
            if(ops.empty() || isp[ops.top()] < icp[s[i]]) ops.push(s[i]);
            else if(isp[ops.top()] == icp[s[i]]) ops.pop();
            else {
                calc(ops, nums);
                i--;
            }
        }
    }
    return nums.top();
}

int main() {
    init();
    string s;
    cin >> s;
    cout << calculate(s);
    return 0;
}

表达式求值，推荐

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <stack>

using namespace std;

stack<char> op;
stack<int> num;

void eval()
{
    auto b = num.top(); num.pop();
    auto a = num.top(); num.pop();
    auto c = op.top(); op.pop();

    int x;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a * b;
    else x = a / b;
    num.push(x);
}

int main()
{
    string s;
    cin >> s;

    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, x = 0;
            while (j < s.size() && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';
            num.push(x);
            i = j - 1;
        }
        else if (s[i] == '(') op.push(s[i]);
        else if (s[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while (op.size()) eval();
    cout << num.top() << endl;

    return 0;
}

中缀表达式转后缀表达式：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <stack>

using namespace std;

stack<char> op;

void eval()
{
    auto c = op.top(); op.pop();
    cout << c << ' ';
}

int main()
{
    string s;
    cin >> s;

    unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
    for (int i = 0; i < s.size(); i ++ )
    {
        if (isdigit(s[i]))
        {
            int j = i, x = 0;
            while (j < s.size() && isdigit(s[j]))
                x = x * 10 + s[j ++ ] - '0';
            cout << x << ' ';
            i = j - 1;
        }
        else if (s[i] == '(') op.push(s[i]);
        else if (s[i] == ')')
        {
            while (op.top() != '(') eval();
            op.pop();
        }
        else
        {
            while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                eval();
            op.push(s[i]);
        }
    }

    while (op.size()) eval();

    return 0;
}