【王道数据结构】【chapter3队列】【P86t4】【统考真题】

2019年统考

请设计一个队列，要求满足：①初始队列为空；②入队时，允许增加队列占用空间；③出队元素所占的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为O(1)，请回答：

1)该队列是应该选择链式存储结构，还是应该选择顺序存储结构

2)画出队列的初始状态，并给出判断队空和队满的条件

3)画出第一个元素入队后的队列状态

4)给出入队操作和出队操作的基本过程

#include <iostream>

typedef struct node{
    int data;
    struct node* next;
}node,*list;

list Buynewnode(int x)
{
    list tmp=(list) malloc(sizeof (node));
    tmp->next= nullptr;
    tmp->data=x;
    return tmp;
}
class circle_list{
    list p1,p2;
    list head=new node;
public:
    circle_list()
    {
        p1=head,p2=head;
        head->next=head;
    }
    void push(int x)
    {
        if(p2->next==p1){//如果队列已经填满了
            p2=p2->next= Buynewnode(x);
            p2->next=p1;
        }else{
            p2=p2->next;
            p2->data= x;
        }
    }

    int pop()
    {
        if(p1==p2){//如果队列已经是空的
            printf("the queue is empty!\n");
            return -1;
        }else{
            int tmp=p1->next->data;
            p1=p1->next;
            return tmp;
        }
    }

    void print(){
        list tmp=p1->next;
        printf("the number is:");
        while(tmp!=p2->next)
        {
            printf("%3d",tmp->data);
            tmp=tmp->next;
        }
        puts("");
    }
};

void test(circle_list cl)
{
    //入队30个元素
    for(int i=0;i<30;i++)
        cl.push(i+1);
    cl.print();

    //出出队12个元素
    printf("pop:");
    for(int i=0;i<12;i++)
        printf("%3d",cl.pop());
    puts("");
    cl.print();

    //再入队30个元素
    for(int i=0;i<30;i++)
        cl.push(i+1);
    cl.print();

    //出队48个元素
    printf("pop:");
    for(int i=0;i<48;i++)
        printf("%3d",cl.pop());
    puts("");
    cl.print();

    cl.pop();//报错
}
int main() {
    circle_list cl=circle_list();
    test(cl);
    return 0;
}