7.1栈的应用

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    int n, x;
    string action;
    cin >> n;
    stack<int> s;
    for (int i = 0; i < n; i++) {
        cin >> action;
        if (action == "push") {
            cin >> x;
            s.push(x);
        } else {
            if (s.empty()) {
                cout << -1 << endl;
            } else {
                cout << s.top() << endl;
                s.pop();
            }
        }
    }
    return 0;
}

#include <iostream>
#include <string>
using namespace std;

string toPostfixExpr(string infixExpr) {
    string result = "";
    result += infixExpr[0];
    for (int i = 2; i < infixExpr.length(); i += 4) {
        result += " ";
        result += infixExpr[i + 2];
        result += " ";
        result += infixExpr[i];
    }
    return result;
}

int main() {
    string expr;
    getline(cin, expr);
    cout << toPostfixExpr(expr);
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;

struct Node {
    int num;
    char op;
    bool isOp;
};

map<char, int> priority;

vector<Node> toNodeVector(string expr) {
    vector<Node> nodes;
    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') {
            continue;
        }
        if (expr[i] >= '0' && expr[i] <= '9') {
            Node numNode;
            numNode.isOp = false;
            numNode.num = expr[i] - '0';
            nodes.push_back(numNode);
        } else {
            Node opNode;
            opNode.isOp = true;
            opNode.op = expr[i];
            nodes.push_back(opNode);
        }
    }
    return nodes;
}

vector<Node> toPostfixVector(vector<Node> infix) {
    vector<Node> postfix;
    stack<Node> opStack;
    for (int i = 0; i < infix.size(); i++) {
        if (infix[i].isOp) {
            while (!opStack.empty() && priority[infix[i].op] <= priority[opStack.top().op]) {
                postfix.push_back(opStack.top());
                opStack.pop();
            }
            opStack.push(infix[i]);
        } else {
            postfix.push_back(infix[i]);
        }
    }
    while (!opStack.empty()) {
        postfix.push_back(opStack.top());
        opStack.pop();
    }
    return postfix;
}

int main() {
    priority['+'] = priority['-'] = 0;
    priority['*'] = priority['/'] = 1;
    string expr;
    getline(cin, expr);
    vector<Node> infix = toNodeVector(expr);
    vector<Node> postfix = toPostfixVector(infix);
    for (int i = 0; i < postfix.size(); i++) {
        if (postfix[i].isOp) {
            cout << postfix[i].op;
        } else {
            cout << postfix[i].num;
        }
        if (i < (int)postfix.size() - 1) {
            cout << " ";
        }
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;

struct Node {
    int num;
    char op;
    bool isOp;
};

map<char, int> priority;

vector<Node> toNodeVector(string expr) {
    vector<Node> nodes;
    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') {
            continue;
        }
        if (expr[i] >= '0' && expr[i] <= '9') {
            Node numNode;
            numNode.isOp = false;
            numNode.num = expr[i] - '0';
            nodes.push_back(numNode);
        } else {
            Node opNode;
            opNode.isOp = true;
            opNode.op = expr[i];
            nodes.push_back(opNode);
        }
    }
    return nodes;
}

double eval(vector<Node> postfix) {
    stack<double> numStack;
    for (int i = 0; i < postfix.size(); i++) {
        if (!postfix[i].isOp) {
            numStack.push(postfix[i].num);
        } else {
            double num2 = numStack.top();
            numStack.pop();
            double num1 = numStack.top();
            numStack.pop();
            if (postfix[i].op == '+') {
                numStack.push(num1 + num2);
            } else if (postfix[i].op == '-') {
                numStack.push(num1 - num2);
            } if (postfix[i].op == '*') {
                numStack.push(num1 * num2);
            } if (postfix[i].op == '/') {
                numStack.push(num1 / num2);
            }
        }
    }
    return numStack.top();
}

int main() {
    priority['+'] = priority['-'] = 0;
    priority['*'] = priority['/'] = 1;
    string expr;
    getline(cin, expr);
    vector<Node> postfix = toNodeVector(expr);
    printf("%.2f", eval(postfix));
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>
using namespace std;

struct Node {
    int num;
    char op;
    bool isOp;
};

map<char, int> priority;

vector<Node> toNodeVector(string expr) {
    vector<Node> nodes;
    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') {
            continue;
        }
        if (expr[i] >= '0' && expr[i] <= '9') {
            Node numNode;
            numNode.isOp = false;
            numNode.num = expr[i] - '0';
            nodes.push_back(numNode);
        } else {
            Node opNode;
            opNode.isOp = true;
            opNode.op = expr[i];
            nodes.push_back(opNode);
        }
    }
    return nodes;
}

vector<Node> toPostfixVector(vector<Node> infix) {
    vector<Node> postfix;
    stack<Node> opStack;
    for (int i = 0; i < infix.size(); i++) {
        if (infix[i].isOp) {
            while (!opStack.empty() && priority[infix[i].op] <= priority[opStack.top().op]) {
                postfix.push_back(opStack.top());
                opStack.pop();
            }
            opStack.push(infix[i]);
        } else {
            postfix.push_back(infix[i]);
        }
    }
    while (!opStack.empty()) {
        postfix.push_back(opStack.top());
        opStack.pop();
    }
    return postfix;
}

double eval(vector<Node> postfix) {
    stack<double> numStack;
    for (int i = 0; i < postfix.size(); i++) {
        if (!postfix[i].isOp) {
            numStack.push(postfix[i].num);
        } else {
            double num2 = numStack.top();
            numStack.pop();
            double num1 = numStack.top();
            numStack.pop();
            if (postfix[i].op == '+') {
                numStack.push(num1 + num2);
            } else if (postfix[i].op == '-') {
                numStack.push(num1 - num2);
            } if (postfix[i].op == '*') {
                numStack.push(num1 * num2);
            } if (postfix[i].op == '/') {
                numStack.push(num1 / num2);
            }
        }
    }
    return numStack.top();
}

int main() {
    priority['+'] = priority['-'] = 0;
    priority['*'] = priority['/'] = 1;
    string expr;
    getline(cin, expr);
    vector<Node> infix = toNodeVector(expr);
    vector<Node> postfix = toPostfixVector(infix);
    printf("%.2f", eval(postfix));
    return 0;
}

7.2队列的应用

#include <iostream>
#include <string>
#include <queue>
using namespace std;

int main() {
    int n, k;
    cin >> n;
    string action;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        cin >> action;
        if (action == "push") {
            cin >> k;
            q.push(k);
        } else {
            if (q.empty()) {
                cout << -1 << endl;
            } else {
                cout << q.front() << endl;
                q.pop();
            }
        }
    }
    return 0;
}

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int n, x;
    scanf("%d", &n);
    queue<int> q;
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        q.push(x);
    }
    while (q.size() > 1) {
        int front1 = q.front();
        q.pop();
        int front2 = q.front();
        q.pop();
        q.push(front1 + front2);
    }
    printf("%d", q.front());
    return 0;
}

#include <cstdio>
#include <queue>
using namespace std;

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }
    while (!q.empty()) {
        for (int i = 0; i < k - 1; i++) {
            int front = q.front();
            q.pop();
            q.push(front);
        }
        printf("%d", q.front());
        q.pop();
        if (!q.empty()) {
            printf(" ");
        }
    }
    return 0;
}

7.3链表处理

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int current = first;
    while (current != -1) {
        printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int current = first;
    int num=0;
    while (current != -1) {
        //printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
        num++;
    }
    printf("%d",num);
    return 0;
}

#include <cstdio>

const int MAXN = 1024;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int num=0;
    int current = first;
    scanf("%d",&num);
    for (int i = 0; i < num; i++) {
        scanf("%d", &id);
        scanf("%d", &nodes[id].data);
        nodes[id].next=current;
        current=id;
    }
    while (current != -1) {
        printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, k, id;
    scanf("%d%d%d", &n, &first, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int current = first, last = 0;
    while (current != -1) {
        if (nodes[current].data == k) {
            if (current == first) {
                first = nodes[current].next;
            }
            nodes[last].next = nodes[current].next;
            current = nodes[last].next;
        } else {
            last = current;
            current = nodes[current].next;
        }
    }
    current = first;
    while (current != -1) {
        printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int current = first, last = -1;
    while (current != -1) {
        int next = nodes[current].next;
        nodes[current].next = last;
        last = current;
        current = next;
    }
    current = last;
    while (current != -1) {
        printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;
const int MAXV = 1000 + 1;

struct Node {
    int data, next;
} nodes[MAXN];

bool needDelete[MAXV] = {false};

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int current = first, last = -1;
    while (current != -1) {
        if (needDelete[nodes[current].data]) {
            nodes[last].next = nodes[current].next;
            current = nodes[current].next;
        } else {
            needDelete[nodes[current].data] = true;
            last = current;
            current = nodes[current].next;
        }
    }
    current = first;
    while (current != -1) {
        printf("%d %d %d\n", current, nodes[current].data, nodes[current].next);
        current = nodes[current].next;
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int fast = first, slow = first;
    while (nodes[fast].next != -1 && nodes[nodes[fast].next].next != -1) {
        slow = nodes[slow].next;
        fast = nodes[fast].next;
        fast = nodes[fast].next;
    }
    if (nodes[fast].next == -1) {
        printf("%.1f", (double)nodes[slow].data);
    } else {
        printf("%.1f", (nodes[slow].data + nodes[nodes[slow].next].data) / 2.0);
    }
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int main() {
    int n, first, k, id;
    scanf("%d%d%d", &n, &first, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int fast = first;
    while (k--) {
        fast = nodes[fast].next;
    }
    int slow = first;
    while (fast != -1) {
        slow = nodes[slow].next;
        fast = nodes[fast].next;
    }
    printf("%d %d %d", slow, nodes[slow].data, nodes[slow].next);
    return 0;
}

#include <cstdio>

const int MAXN = 100;

struct Node {
    int data, next;
} nodes[MAXN];

int reverseList(int first) {
    int current = first, last = -1;
    while (current != -1) {
        int next = nodes[current].next;
        nodes[current].next = last;
        last = current;
        current = next;
    }
    return last;
}

bool judgePalindrome(int head1, int head2) {
    while (head2 != -1) {
        if (nodes[head1].data != nodes[head2].data) {
            return false;
        }
        head1 = nodes[head1].next;
        head2 = nodes[head2].next;
    }
    return true;
}

int main() {
    int n, first, id;
    scanf("%d%d", &n, &first);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id);
        scanf("%d%d", &nodes[id].data, &nodes[id].next);
    }
    int fast = first, slow = first;
    while (nodes[fast].next != -1 && nodes[nodes[fast].next].next != -1) {
        slow = nodes[slow].next;
        fast = nodes[fast].next;
        fast = nodes[fast].next;
    }
    int headOfSecondPart = reverseList(nodes[slow].next);
    bool isPalindrome = judgePalindrome(first, headOfSecondPart);
    nodes[slow].next = reverseList(headOfSecondPart);
    printf(isPalindrome ? "Yes" : "No");
    return 0;
}