数据结构与算法 / 第2周 栈与队列 作业题

1.cpp

#include <iostream>

using namespace std;


struct PocketCard {
    char x;
    int y;
};


struct Node {
    PocketCard *current;
    Node *next;

};

class Queue {

private:
    Node *first;
    Node *last;

public:
    Queue() {
        first = NULL;
        last = NULL;
    }

    void enqueue(PocketCard *item) {
        Node *temp = new Node();
        temp->current = item;

        if (isEmpty()) {
            first = temp;
            last = temp;
        }

        else {
            first->next = temp;
            first = temp;
        }
    }

    PocketCard *dequeue() {
        if (isEmpty()) throw new exception;
        if (first == last) {
            PocketCard *temp = first->current;
            first = NULL;
            last = NULL;
            return temp;
        }

        PocketCard *temp = last->current;
        last = last->next;
        return temp;
    }


    bool isEmpty() {
        return first == NULL;
    }


    ~Queue() {
        Node *start = last;
        while (start != first) {
            Node *old = start;
            start = start->next;
            delete old;
        }
        delete first;
    }

    void printQueue(){
        if(!isEmpty()){
            Node* temp = last;
            while(temp != first){
                cout << temp->current->x <<temp->current->y<<" ";
                temp = temp->next;
            }
            cout << temp->current->x << temp->current->y;
        }
    }

};

void printPocketCard(PocketCard* pc){
    cout << pc->x << pc->y <<" ";
}

int main() {

    int number;
    cin >> number;

    int i = 0;

    char buffer[3];


    Queue* queues = new Queue[10];


    for(; i < number; i ++){

        cin >> buffer;
        PocketCard* pc = new PocketCard();
        pc->x = buffer[0];
        pc->y = buffer[1] - 48;

        queues[pc->y].enqueue(pc);
    }

    // Print step one
    Queue* otherQueues = new Queue[4];
    for(i = 1; i <= 9; i ++){
        cout << "Queue"<<i<<":";
        queues[i].printQueue();
        cout <<endl;

        while (!queues[i].isEmpty()){
            PocketCard* item = queues[i].dequeue();
            if (item->x == 'A')
                otherQueues[0].enqueue(item);
            else if (item->x == 'B')
                otherQueues[1].enqueue(item);
            else if (item->x == 'C')
                otherQueues[2].enqueue(item);
            else if (item->x == 'D')
                otherQueues[3].enqueue(item);
        }

    }

    cout <<"QueueA:";
    otherQueues[0].printQueue();
    cout <<endl;

    cout <<"QueueB:";
    otherQueues[1].printQueue();
    cout <<endl;

    cout <<"QueueC:";
    otherQueues[2].printQueue();
    cout <<endl;

    cout <<"QueueD:";
    otherQueues[3].printQueue();
    cout <<endl;


    for(i = 0; i < 4; i ++){
        while (!otherQueues[i].isEmpty()){
            PocketCard* item = otherQueues[i].dequeue();
            cout << item->x << item->y <<" ";
        }
    }


    delete[] queues;
    delete[] otherQueues;

}

2.cpp

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


struct Node{
    int value;
    Node* next;
};

class Stack{

private:
    Node* first;

public:
    Stack(){
        first = NULL;
    }

    void push(int val){
        Node* item = new Node();
        item->value = val;

        Node* old = first;
        first = item;
        first->next = old;
    }

    int pop(){

        if(isEmpty()){
            clearElements();
            return NULL;
        }
        else{
            Node* old = first;
            first = first->next;

            int result = old->value;
            delete old;

            return result;
        }

    }

    bool isEmpty(){return first == NULL;}


    ~Stack(){
        while(!isEmpty()){
            Node* old = first;
            first = first->next;
            delete old;
        }
    }


    void printStack(){
        reversePrintNode(first);
        cout <<endl;
    }


    void reversePrintNode(Node* pivot){
        if(pivot!= NULL){
            reversePrintNode(pivot->next);
            cout << pivot->value<<" ";
        }
    }

    void clearElements(){
        while(!isEmpty()){
            Node* old = first;
            first = first->next;
            delete old;
        }
    }

};


int main(){
    int i, j;
    int m;
    cin >> m;
    for(i = 0; i < m; i++)
    {
        int n, num;
        char op[16];
        bool flag = false;
        cin >> n;
        Stack s;

        for(j = 0; j < n; j++) {
            cin >> op;
            if(strcmp(op, "pop") == 0) {
                if(s.isEmpty()) flag = true;
                else s.pop();

            }
            else {
                cin >> num;
                s.push(num);
            }
        }


        if(flag) cout <<"error"<<endl;
        else if(s.isEmpty()) continue;
        else s.printStack();
    }
    return 0;
}

3.cpp

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


struct Node{
    int value;
    Node* next;
};

class Stack{

private:
    Node* first;

public:
    Stack(){
        first = NULL;
    }

    void push(int val){
        Node* item = new Node();
        item->value = val;

        Node* old = first;
        first = item;
        first->next = old;
    }

    int pop(){

        if(isEmpty()){
            clearElements();
            return NULL;
        }
        else{
            Node* old = first;
            first = first->next;

            int result = old->value;
            delete old;

            return result;
        }

    }

    bool isEmpty(){return first == NULL;}


    ~Stack(){
        while(!isEmpty()){
            Node* old = first;
            first = first->next;
            delete old;
        }
    }


    void printStack(){
        reversePrintNode(first);
        cout <<endl;
    }


    void reversePrintNode(Node* pivot){
        if(pivot!= NULL){
            reversePrintNode(pivot->next);
            cout << pivot->value<<" ";
        }
    }

    void clearElements(){
        while(!isEmpty()){
            Node* old = first;
            first = first->next;
            delete old;
        }
    }

};

class Queue{

private:
    Node* first;
    Node* last;

public:
    Queue(){first = NULL; last = NULL;}

    bool isEmpty(){return first == NULL;}

    void push(int item){
        Node* temp = new Node();
        temp->value = item;

        if(isEmpty()){
            first = last = temp;
        }
        else{
            last->next = temp;
            last = temp;
        }
    }

    int pop(){
        if(isEmpty()) throw new exception();
        int result = first->value;

        first = first->next;
        if(first == NULL) last = NULL;
        return result;
    }

};


int main(){
    int i, j;
    int m;
    cin >> m;



    for(i = 0; i < m; i++){

        bool decided = false;
        bool queueFlag = true;
        int n, num;
        int operation;
        cin >> n;

        Stack s;
        Queue q;

        for(j = 0; j < n; j++) {
            cin >> operation;

            if(operation == 1) {
                cin >> num;
                s.push(num);
                q.push(num);
            }
            else {

                cin >> num;
                if (decided) continue;

                int one = s.pop();
                int two = q.pop();

                if(one == num && one == two) continue;
                else if(one == num){
                    decided = true;
                    queueFlag = false;
                }
                else if(two = num) decided = true;
            }
        }

        if(queueFlag) cout << "Queue"<<endl;
        else cout <<"Stack"<<endl;

    }

    return 0;
}

4.cpp

#include <iostream>
#import <stack>

using namespace std;


int mycmp(char a, char b) {
    if (b == '(')
        return 1;//左括号直接入栈
    else if ((b == '*' || b == '/') && (a == '+' || a == '-' || a == '('))
        return 1;//*、/优先级高于+、-、(，入栈
    else if ((b == '+' || b == '-') && (a == '('))
        return 1;//+、-优先级高于(，入栈
    else
        return 0;
}

/*中缀表达式转后缀表达式
 中缀表达式之间无分割
 后缀表达式操作数、操作符之间用空格分割，便于区分不同操作数*/
void infix_to_suffix(char *infix, char *suffix) {
    int i, k, j = 0, top = 0;
    char stack[1000];//存储运算符的栈

    for (i = 0; infix[i] != '\0'; i++) {
        if (infix[i] >= '0' && infix[i] <= '9') {
            suffix[j++] = infix[i];//操作数则直接输出
        } else {
            if (i != 0 && infix[i - 1] >= '0' && infix[i - 1] <= '9') {
                suffix[j++] = ' ';//操作数后补充空格分割
            }
            if (infix[i] == ')') {
                //遇到右括号则一直弹出直到左括号，但左括号不输出
                while (stack[top - 1] != '(') {
                    suffix[j++] = stack[--top];
                    suffix[j++] = ' ';
                }
                top--;
            } else if (top == 0 || mycmp(stack[top - 1], infix[i])) {
                //栈为空或当前操作符的优先级高于栈顶操作符，当前操作符入栈
                stack[top++] = infix[i];
            } else {
                //当前操作符优先级等于或低于栈顶操作符则弹出栈顶
                while (!mycmp(stack[top - 1], infix[i])) {
                    suffix[j++] = stack[--top];
                    suffix[j++] = ' ';
                    if (top == 0)
                        break;
                }
                stack[top++] = infix[i];//当前操作符入栈
            }
        }
    }
    //补充空格分割
    if (suffix[j - 1] != ' ') {
        suffix[j++] = ' ';
    }
    //如果操作符栈不为空，弹出所有操作符
    while (top != 0) {
        suffix[j++] = stack[--top];
        suffix[j++] = ' ';
    }
    suffix[j] = '\0';
}


int getValue(char *suffix) {

    int i, j;
    char op;
    int stack[1000];
    int top = 0, value = 0;

    for (i = 0; suffix[i] != '\0'; i++) {
        if (suffix[i] >= '0' && suffix[i] <= '9')
            value = value * 10 + suffix[i] - '0';
        else if (suffix[i] == ' ') {
            stack[top++] = value;
            value = 0;
        }
        else {
            switch (suffix[i]) {
                case '+':
                    value = stack[top - 2] + stack[top - 1];
                    break;
                case '-':
                    value = stack[top - 2] - stack[top - 1];
                    break;
                case '*':
                    value = stack[top - 2] * stack[top - 1];
                    break;
                case '/':
                    value = stack[top - 2] / stack[top - 1];
                    break;
                default:
                    break;
            }
            top -= 2;
        }
    }

    return stack[0];
}

int main(){

    int cases;
    cin >> cases;

    for(int i = 0; i < cases; i ++){
        char buffer[600];
        cin >> buffer;

        char suffix[1000];
        infix_to_suffix(buffer, suffix);

        int val = getValue(suffix);
        cout << val <<endl;
    }

    return 0;
}