队列（数组实现）（顺序队列，循环队列）

829. 模拟队列

•   题目 
•   提交记录 
•   讨论 
•   题解 
•   视频讲解 

实现一个队列，队列初始为空，支持四种操作：

1. push x – 向队尾插入一个数 x

1. ；
2. pop – 从队头弹出一个数；
3. empty – 判断队列是否为空；
4. query – 查询队头元素。

现在要对队列进行 M

个操作，其中的每个操作 3 和操作 4

都要输出相应的结果。

输入格式

第一行包含整数 M

，表示操作次数。

接下来 M

行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

1≤M≤100000

,
1≤x≤109

,
所有操作保证合法。

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

 1)顺序链表：

/**
 * head表示队首的位置，tail表示队尾的位置

*/

#include <iostream>

using namespace std;

const int maxn = 1e5+10;
int que[maxn],head,tail;

void push(int x)
{
    que[tail++]=x;
}

void pop()
{
    ++head;
}

int front()
{
    return que[head];
}

bool empty()
{
    if(head == tail)
        return 1;
    else 
        return 0;
}

int main()
{
    int n;
    cin >> n;
    
    for(int i=0;i<n;++i)
    {
        string op;
        int x;
        cin >> op;
        if(op == "push")
        {
            cin >> x;
            push(x);
        }
        else if(op == "pop")
            pop();
        else if(op == "query")
            cout << front() << endl;
        else 
        {
            if(empty())
                puts("YES");
            else 
                puts("NO");
        }
    }
    
    return 0;
}

2）循环队列：

/**
 * head表示队首的位置，tail表示队尾的位置
 * 循环队列：tail - head 共有n种不同的情况，而队列中元素个数情况共有 0，1，2……n n+1
 * 种情况；
 * 所以无法完全用tail-head来表示队列的元素情况，但是我们可以只在队列中最多装入n-1个
 * 元素，这样就能一一对应了；
 * 
*/

#include <iostream>

using namespace std;

const int maxn = 1e3+10;
int que[maxn],head,tail;

void push(int x)    //入队  
{
    ++tail;
    tail%=maxn;
    que[tail]=x;
}

void pop()  //弹出队首元素
{
    ++head;
    head%=maxn;
}

int front() //返回队首元素的值
{
    return que[(head+1)%maxn];
}

bool empty()    //判断队列是否为空
{
    if(head == tail)
        return 1;
    else 
        return 0;
}

int main()
{
    int n;
    cin >> n;
    
    for(int i=0;i<n;++i)
    {
        string op;
        int x;
        cin >> op;
        if(op == "push")
        {
            cin >> x;
            push(x);
        }
        else if(op == "pop")
            pop();
        else if(op == "query")
            cout << front() << endl;
        else 
        {
            if(empty())
                puts("YES");
            else 
                puts("NO");
        }
    }
    
    return 0;
}

最后

以上就是沉静山水为你收集整理的队列（数组实现）（顺序队列，循环队列）的全部内容，希望文章能够帮你解决队列（数组实现）（顺序队列，循环队列）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。