愿你坚持不懈,努力进步,进阶成自己理想的人

—— 2017.09, 写给3年后的自己

PAT-练习3:队列

请实现一个MyQueue类,实现出队,入队,求队列长度.

实现入队函数 void push(int x);
实现出队函数 int pop();
实现求队列长度函数 int size();
Input Specification:

每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ,接下去n行每行一个数字,表示一种操作:

1 x : 表示从队尾插入x,0<=x<=2^31-1。
2 : 表示队首元素出队。
3 : 表示求队列长度。
Output Specification:

对于操作2,若队列为空,则输出 “Invalid”,否则请输出队首元素。 对于操作3,请输出队列长度。

Sample Input:
5
3
2
1 100
3
2
Sample Output:

#include <iostream>
using namespace std;

struct Queue {
    int data;
    Queue * next;
};

class MyQueue {
private:
    int front;
    int rear;
    Queue * Q;
public:
    MyQueue() {
        this->front = 0;
        this->rear = 0;
        this->Q = NULL;
    }
    void push(int x) {
        if(this->Q==NULL) {
            this->Q = new Queue;
            this->Q->data = x;
            this->Q->next = NULL;
            this->rear++;
        } else {
            Queue *p=this->Q, *last=NULL;
            do {
                last = p;
                p = p->next;
            } while(p!=NULL);
            Queue *c=new Queue;
            c->data = x;
            c->next = NULL;
            last->next = c;
            this->rear++;
        }
    }
    int size() {
        return this->rear - this->front;
    }
    int pop() {
        if(this->size()==0) return -1;
        int data;
        data = this->Q->data;
        this->Q = this->Q->next;
        this->front++;
        return data;
    }
};

int main() {
    int n, op;
    cin >> n;
    MyQueue q;
    while(n>0) {
        cin >> op;
        switch (op) {
            case 1: {
                int x;
                cin >> x;
                q.push(x);
                break;
            }
            case 2: {
                int popElement = q.pop();
                if(popElement==-1) cout << "Invalid" << endl;
                else cout << popElement << endl;
                break;
            }
            case 3: {
                cout << q.size() << endl;
                break;
            }
        }
        n--;
    }
    
    return 0;
}