23. 绘声绘色编程练习

古城微笑少年丶 2022-04-02 07:40 207阅读 0赞

Description

又到了一年一度周老师讲解简单（划掉）毒瘤数据结构的时候辣！

为了让大家更好理解，今年周老师决定和大家玩一个游戏：

假设一个黑盒箱里是某个神奇的数据结构（栈、队列、优先队列之一），每次支持你两种操作：

*  —— 把元素 丢到这个黑盒里
 *  —— 从这个黑盒弹出一个元素

周老师给定一系列具有返回值的黑盒操作，请你来猜猜看，这是什么数据结构！本题可能用到的数据结构：

*  —— 栈，元素遵循先进后出原则
 *  —— 队列，元素遵循先进先出原则
 *  ——优先队列（大顶堆），每次从大顶堆取出的元素是堆集合的所有元素中最大的元素
 *  ——优先队列（小顶堆），每次从小顶堆取出的元素是堆集合的所有元素中最小的元素

![TIM_E5_9B_BE_E7_89_8720180911104851.jpg][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70][]

#include "stdio.h"
    #include<iostream>
    #include <queue>
    #include <bits/stdc++.h>
    using namespace std;
    int main() 
    {
        priority_queue<long long> a; //大顶堆
        priority_queue<long long, vector<long long>, greater<long long> > b;  //小顶堆
        stack<long long> c;//栈
        queue<long long> d;//队列
        int n;
        while(scanf("%d",&n) != EOF){
            long long op, x, xa, xb, xc, xd;
            int flaga = 1, flagb = 1, flagc = 1, flagd = 1;
            while(n--){
                scanf("%lld%lld",&op,&x);
                if(op == 1){
                    a.push(x);
                    b.push(x);
                    c.push(x);
                    d.push(x);
                }
                else{
                    if(a.empty()||b.empty()||c.empty()||d.empty()){
                        flaga = 0;
                        flagb = 0;
                        flagc = 0;
                        flagd = 0;
                        break;
                    }
                    else{
                        xa = a.top();
                        xb = b.top();
                        xc = c.top();
                        xd = d.front();
                        a.pop();
                        b.pop();
                        c.pop();
                        d.pop();
                    }
                    if(xa != x) flaga = 0;
                    if(xb != x) flagb = 0;
                    if(xc != x) flagc = 0;
                    if(xd != x) flagd = 0;
                }
            }
            if(flaga+flagb+flagc+flagd > 1)
                printf("not sure\n");
            else if(flaga+flagb+flagc+flagd == 0) printf("pool zls\n");
            else if(flaga == 1) printf("big priority queue\n");
            else if(flagb == 1) printf("small priority queue\n");
            else if(flagc == 1) printf("stack\n");
            else if(flagd == 1) printf("queue\n");
    
            while(!a.empty()){
                a.pop();
            }
            while(!b.empty()){
                b.pop();
            }
            while(!c.empty()){
                c.pop();
            }
            while(!d.empty()){
                d.pop();
            }
        }
        return 0;
    }

[TIM_E5_9B_BE_E7_89_8720180911104851.jpg]: http://online.bit.edu.cn/moodle/pluginfile.php/182509/mod_programming/intro/TIM%E5%9B%BE%E7%89%8720180911104851.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTIwNzE3NQ_size_16_color_FFFFFF_t_70]: /images/20220402/fc0330b09b52477c9c81eed25fa938fe.png