NOJ数据结构009——循环队列

迷南。 2022-11-16 13:43 147阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]![在这里插入图片描述][20210407130152771.png]  
本题考查循环队列的应用。  
循环队列是队列的一种顺序表示和实现方法。可节省大量空间。  
本题中要求使用域变量rear（即队尾）和length（即队长）编写程序。这样做可规避一般循环队列的小缺陷，即不用预留一个空间来判断是否队满。

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct {
        
        int *data;
        int rear;
        int length;
        int n;
    }QueueNode;
    
    QueueNode seq;
    
    int IsEmpty(QueueNode *q);          //队列判空
    int IsFull(QueueNode *q);           //队列判满
    void Push(QueueNode *q, int item);  //入队
    void Pull(QueueNode *q, int* out);  //出队
    void PrintQueue(QueueNode *q);      //输出队列元素及队首
    
    QueueNode CreateQueue(int m);
    
    int main()
    {
        
        int m;
        scanf("%d", &m);
        seq = CreateQueue(m);
        while(1) {
        
            int tmp;
            scanf("%d", &tmp);
            Push(&seq, tmp);
            char c;
            c = getchar();
            if (c == '\n') {
        
                break;
            }
        }
        char str[5];
        scanf("%s", str);
        int out, out_tmp;
        scanf("%d", &out);
        Pull(&seq, &out_tmp);
        while(out != out_tmp) {
        
            Pull(&seq, &out_tmp);
        }
        PrintQueue(&seq);
        return 0;
    }
    
    QueueNode CreateQueue(int m)
    {
        
        QueueNode *q;
        q = (QueueNode*) malloc (sizeof(QueueNode));
        q->data = (int*) malloc (sizeof(int)*m);
        q->rear = 0;
        q->length = 0;
        q->n = m;
        return *q;
    }
    
    int IsEmpty(QueueNode *q)
    {
              //队列判空
        if(q->length == 0) {
        
            return 1;
        }
        else return 0;
    }
    
    int IsFull(QueueNode *q)
    {
              //队列判满
        if(q->length == q->n) {
        
            return 1;
        }
        else return 0;
    }
    
    void Push(QueueNode *q, int item)
    {
               //入队
        if(IsEmpty(q)) {
        
            q->length++;
            q->data[q->rear] = item;
            return;
        }
        if(IsFull(q)) {
        
            return;
        }
        else {
        
            q->length++;
            q->rear = (q->rear + 1) % q->n;
            q->data[q->rear] = item;
        }
    }
    
    void Pull(QueueNode *q, int* out)
    {
             //出队
        if(IsEmpty(q)) {
        
            return;
        }
        int tmp;
        tmp = (q->rear + q->n  - q->length + 1) % q->n;//队首所在
        *out = q->data[tmp];
        q->length--;
    }
    
    void PrintQueue(QueueNode *q)
    {
            //输出队列元素及队首
        if(IsEmpty(q)) {
        
            return;
        }
        int tmp;
        tmp = (q->rear + q->n - q->length + 1) % q->n;
        while (tmp != q->rear) {
        
            printf("%d ", q->data[tmp]);
            tmp = (tmp + 1) % q->n;
        }
        printf("%d ", q->data[tmp]);
        tmp = (q->rear + q->n - q->length + 1) % q->n;
        printf("\n%d ", q->data[tmp]);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210407130142693.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ==,size_16,color_FFFFFF,t_70
[20210407130152771.png]: /images/20221022/39cb57ee64c14fdfba3808a119381832.png