注册 登录
编程论坛 C语言论坛

c语言队列问题

xiaohuo66 发布于 2020-11-28 21:07, 1333 次点击
我们都了解队列,现在要求在队列中添加一种功能,即输出队列中有多少种不同的元素。

Input
多组样例,处理到文件结尾

每组样例的第一行是一个正整数n,表示有n次操作,1 <= n <= 1e5

接下来n行,每行表示一个操作,格式如下:

1 :输出队列中有多少种不同的数字

2 x :从队尾插入元素x,其中1 <= x <= 1000

3:取出队首元素,出现3操作时,保证队列非空

Output
对于每个操作1,输出答案
Sample Input
6

1

2 1

2 3

1

3

1

Sample Output

0

2

1
2 回复
#2
rjsp2020-11-29 18:26
一个 unsigned short[100000] 用当队列
一个 unsigned [1001] 用于保存每个数值的数目
#3
rjsp2020-11-30 08:47
程序代码:
#include <stdio.h>

int main( void )
{
    // 队列
    unsigned queue[100000];
    size_t queue_begin = 0;
    size_t queue_end = 0;
    // [0,1000]中每个数字的数量
    unsigned count[1001] = { 0 };
    // 有多少种不同的数字
    unsigned variety = 0;

    unsigned n;
    scanf( "%u", &n );
    while( n-- )
    {
        unsigned action;
        scanf( "%u", &action );
        switch( action )
        {
        case 1:
            printf( "%u\n", variety );
            break;
        case 2:
            {
            unsigned push;
            scanf( "%u", &push );
            queue[queue_end++] = push;
            if( count[push] == 0 )
                ++variety;
            ++count[push];
            }
            break;
        case 3:
            {
            unsigned pop = queue[queue_begin++];
            --count[pop];
            if( count[pop] == 0 )
                --variety;
            }
            break;
        }
    }
}
1