题解31 | #【模板】循环队列##【模拟】队列#

#include <iostream>
using namespace std;
struct queue{
    int q[100000];
    int head;
    int rear;
    queue(){ head = 0;rear = 0;}
};

int len;// 循环队列 可使用空间长度 区别于 普通队列
// 在循环中，当队头指针处于队尾指针后一个位置时，表示队满
void push(queue &que,int num){
    if(que.head == (que.rear + 1) % len){
        cout<<"full"<<endl;
        return ;
    }
    que.q[que.rear] = num;
    que.rear = (que.rear + 1) % len;//指针移动要取模
}

bool isEmpty(queue &que){
    return que.head == que.rear;
}

int front(queue &que){
    return que.q[que.head];
}

int pop(queue &que){
    int top = que.q[que.head];//front()
    que.head = (que.head + 1) % len;//指针移动要取模
    return top;
}

int main() {
    int n;
    cin>>len>>n;
    len++;
    queue que;

    for(int i = 0; i < n; i++){
        string op;
        cin>>op;
        if(op == "push"){
            int num;
            cin>>num;
            push(que,num);
        }// 在队列进行pop和front操作前需要先判断队列此时是否为空
        else if (isEmpty(que)) {
            cout<< "empty" <<endl;
        }
        else if (op == "pop") {
            cout<< pop(que) <<endl;
        }
        else if (op == "front") {
            cout<< front(que) <<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

第一种实现：

这种实现使用了循环队列。queue结构包含一个数组q来存储元素，以及head和rear变量来跟踪队列的前后位置。push函数在队列的后面位置插入元素，pop函数删除并返回前面位置的元素。isEmpty函数检查队列是否为空，front函数返回前面位置的元素而不删除它。

时间复杂度：

• push：O(1)
• pop：O(1)
• isEmpty：O(1)
• front：O(1)

空间复杂度：

• O(len)，其中len是队列的长度。

#include <iostream>
using namespace std;

struct queue{
    int q[1000000];
    int head;
    int rear;
    queue(){ head = 0; rear = 0; }
};

void push(queue &que, int num){
    que.q[que.rear] = num;
    que.rear++;
}

int front(queue &que){
    return que.q[que.head];
}

int pop(queue &que){
    int top = front(que);
    que.head++;
    return top;
}
bool isEmpty(queue &que){
    return que.head == que.rear;
}
int main() {
    int n;
    cin>>n;
    queue que;

    for(int i = 0; i < n; i++){
        string op;
        cin>>op;
        if(op == "push"){
            int num;
            cin>>num;
            push(que,num);
        }
        else if (isEmpty(que)) {
            cout<<"error"<<endl;
        }
        else if (op == "pop") {
            cout<<pop(que)<<endl;
        }
        else if (op == "front") {
            cout<<front(que)<<endl;
        }
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

第二种实现：

这种实现与第一种实现类似，但它不使用循环队列。queue结构仍然包含一个数组q，head和rear变量用于跟踪队列的前后位置。push函数在队列的后面位置插入元素，pop函数删除并返回前面位置的元素。isEmpty函数检查队列是否为空，front函数返回前面位置的元素而不删除它。

时间复杂度：

• push：O(1)
• pop：O(1)
• isEmpty：O(1)
• front：O(1)

空间复杂度：

• O(len)，其中len是队列的长度。