[C++/PTA] 队列操作

题目要求

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

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

输入格式:
每个输入包含1个测试用例。每个测试用例第一行给出一个正整数 n (n <= 10^6) ，接下去n行每行一个数字，表示一种操作：
1 x ： 表示从队尾插入x，0<=x<=2^31-1。
2 ： 表示队首元素出队。
3 ： 表示求队列长度。

输出格式:
对于操作2,若队列为空，则输出 “Invalid”,否则请输出队首元素。 对于操作3，请输出队列长度。
每个输出项最后换行。

输入样例:
5
3
2
1 100
3
2

输出样例:
0
Invalid
1
100

解题思路

代码

静态数组实现

#include <iostream>
using namespace std;

const int MAXSIZE = 100010; //定义静态数组最大长度

class MyQueue { //定义 MyQueue 类
    private:
        int data[MAXSIZE]; //定义一个静态数组 data，用来存储队列元素
        int duilie=0,ren=0; //定义两个变量，表示队列的长度和队首元素位置
    public:
        void push(int x) { //定义 push 函数，将元素 x 加入队列
            data[duilie++] = x; //在数组尾部添加元素，并将队列元素个数加 1
        }
        int pop() { //定义 pop 函数，弹出队首元素并返回该元素值
            if(duilie==ren) //如果队列为空，弹出无效，输出 "Invalid"
                cout<<"Invalid"<<endl;
            else { //否则，弹出队首元素，输出该元素值，并将队列元素个数减 1
                cout<<data[ren++]<<endl;
            }
        }
        int size() { //定义 size 函数，返回队列元素个数（即队列长度）
            cout<<duilie-ren<<endl; //输出队列元素个数
        }
};

int main(int argc, char *argv[]) {
    int i,j,k;
    cin>>i; //输入操作次数
    MyQueue a; //创建 MyQueue 对象 a

    for(j=0;j<i;j++) //进行 i 次操作
    {
        cin>>k; //输入操作类型
        switch(k)
        {
            case 1: //如果操作类型为 1，再输入要加入队列的元素值 x，并调用 push 函数将其加入队列
                int x;
                cin>>x;
                a.push(x);
                break;
            case 2: //如果操作类型为 2，调用 pop 函数弹出队首元素
                a.pop();
                break;
            case 3: //如果操作类型为 3，调用 size 函数返回队列长度
                a.size();
        }
    }
}

注意：
由于静态数组的长度是固定的，因此需要在代码中定义一个常量 MAXSIZE 来表示数组的最大长度。
同时，在 push 函数中，我们使用 data[duilie++] 来将元素加入队列，并在 pop 函数中使用 data[ren++] 来弹出队首元素。

vector容器实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> obj; //定义一个 vector 对象 obj，用来存储队列元素
int duilie=0,ren=0; //定义两个变量，表示队列的长度和队首元素位置

class MyQueue { //定义 MyQueue 类
    private:
    public:
    void push(int x) { //定义 push 函数，将元素 x 加入队列
        obj.push_back(x); //在 vector 尾部添加元素
        duilie++; //队列元素个数加 1
    }
    int pop() { //定义 pop 函数，弹出队首元素并返回该元素值
        if(duilie==0) //如果队列为空，弹出无效，输出 "Invalid"
            cout<<"Invalid"<<endl;
        if(duilie!=0) //否则，从队列中删除队首元素，并输出该元素值
        {
            cout<<obj[0]<<endl;
            vector<int>::iterator s = obj.begin(); //定义迭代器 s，将其指向 vector 的起始位置
            obj.erase(s); //在 vector 中删除起始位置的元素
            duilie--; //队列元素个数减 1
        }
    }
    int size() { //定义 size 函数，返回队列元素个数（即队列长度）
        int i;
        for(i=0;i<obj.size();i++)
        {
            ;
        }
        cout<<i<<endl; //输出元素个数 i
    }

};

int main(int argc, char *argv[]) {
    unsigned long long int i,j,k;
    cin>>i; //输入操作次数
    MyQueue a; //创建 MyQueue 对象 a

    for(j=0;j<i;j++) //进行 i 次操作
    {
        cin>>k; //输入操作类型
        switch(k)
        {
            case 1: //如果操作类型为 1，再输入要加入队列的元素值 x，并调用 push 函数将其加入队列
                int x;
                cin>>x;
                a.push(x);
                break;
            case 2: //如果操作类型为 2，调用 pop 函数弹出队首元素
                a.pop();
                break;
            case 3: //如果操作类型为 3，调用 size 函数返回队列长度
                a.size();
        }
    }
}

具体解读

定义了vector<int>类型的对象 obj，用来存储队列中的元素。

MyQueue 是一个类，包含三个成员函数：push() 用来在队尾插入一个元素；pop() 用来删除队首元素；size() 用来返回队列长度。

在 main() 函数中先输入操作次数 i，然后循环执行 i 次操作。每次操作根据输入的操作类型进行相应的处理，包括：添加元素、弹出队首元素、返回队列长度等。

在 push() 函数中，使用 push_back() 在 vector 的尾部添加元素，并将队列元素个数加 1。

在 pop() 函数中，如果队列为空，则输出 "Invalid"，否则从队首弹出一个元素，输出该元素值，并将队列元素个数减 1。在这里使用了迭代器进行 vector 的删除操作。

在 size() 函数中，使用迭代器遍历整个 vector，计算其中元素的个数并输出

总结

该题考察队列的基本概念和实现方式；

vector 容器的定义、操作和迭代器的使用；

静态数组的定义和使用，以及队列的模拟实现。

我是秋说，我们下次见。