循环队列

对于线性队列，只能分​​别在前面和后面执行删除和插入操作. 考虑下图所示的队列.

上图中显示的队列已完全填充. 由于条件Rear == max-1变为true循环队列，因此不能再插入任何元素.

但是，如果删除队列最前面的2个元素循环队列，由于条件after = max -1仍然成立，您仍然不能插入任何元素.

这是线性队列的主要问题. 尽管数组中有可用空间，但是不能将更多元素插入队列. 这只是浪费内存，需要克服.

解决此问题的方法之一是循环队列. 在循环队列中，第一个索引紧随最后一个索引. 您可以考虑使用循环队列，如下图所示.

当front = -1和Rear = max-1时，循环队列将满. 循环队列的实现类似于线性队列的实现. 仅在插入和删除的情况下实现的逻辑部分与线性队列中的逻辑部分不同.

时间复杂度

操作

前

enQueue（）

deQueue（）

在队列中插入元素的情况有三种.

在循环队列中插入元素的算法

第1步 : IF (REAR+1)%MAX = FRONT
    提示 " OVERFLOW "
    转到第4步
    [End OF IF]
第2步 : IF FRONT = -1 and REAR = -1
    SET FRONT = REAR = 0
    ELSE IF REAR = MAX - 1 and FRONT ! = 0
    SET REAR = 0
    ELSE
    SET REAR = (REAR + 1) % MAX
    [END OF IF]
第3步 : SET QUEUE[REAR] = VAL
第4步 : EXIT

C语言实现代码如下-

void insert(int item, int queue[])  
{  
    if((rear+1)%maxsize == front)  
    {  
        printf("OVERFLOW");  
        return;  
    }  
    else if(front == -1 && rear == -1)  
    {  
        front = 0;  
        rear = 0;  
    }else if(rear == maxsize -1 && front != 0)   
    {  
        rear = 0;  
    }else   
    {  
        rear = (rear+1)%maxsize;  
    }  
    queue[rear] = item;  
}

要从循环队列中删除元素，必须检查以下三个条件.

算法

第1步：IF FRONT = -1
    提示 “UNDERFLOW”
    转到第4步
    [IF结束]
第2步：设置VAL = QUEUE [FRONT]
第3步：如果FRONT = REAR
    SET FRONT = REAR = -1
    其他
    IF FRONT = MAX -1
    SET FRONT = 0
    其他
    SET FRONT = FRONT + 1
    [IF结束]
  [结束]
第4步：退出

C语言的完整代码如下-

#include<stdio.h>   
#include<stdlib.h>  
#define maxsize 5  
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main()
{
    int choice;
    while (choice != 4)
    {
        printf("*************************Main Menu*****************************\n");
        printf("=================================================================\n");
        printf("1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
        printf("Enter your choice ?");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            insert();
            break;
        case 2:
            delete();
            break;
        case 3:
            display();
            break;
        case 4:
            exit(0);
            break;
        default:
            printf("Enter valid choice??\n");
        }
    }
}
void insert()
{
    int item;
    printf("Enter the element\n");
    scanf("%d", &item);
    if ((rear + 1) % maxsize == front)
    {
        printf("OVERFLOW");
        return;
    }
    else if (front == -1 && rear == -1)
    {
        front = 0;
        rear = 0;
    }
    else if (rear == maxsize - 1 && front != 0)
    {
        rear = 0;
    }
    else
    {
        rear = (rear + 1) % maxsize;
    }
    queue[rear] = item;
    printf("Value inserted ");
}
void delete()
{
    int item;
    if (front == -1 & rear == -1)
    {
        printf("UNDERFLOW\n");
        return;
    }
    else if (front == rear)
    {
        front = -1;
        rear = -1;
    }
    else if (front == maxsize - 1)
    {
        front = 0;
    }
    else
        front = front + 1;
}
void display()
{
    int i;
    if (front == -1)
        printf("Circular Queue is Empty!!!\n");
    else
    {
        i = front;
        printf("Circular Queue Elements are : \n");
        if (front <= rear) {
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        }
        else {
            while (i <= maxsize - 1)
                printf("%d %d %d\n", queue[i++], front, rear);
            i = 0;
            while (i <= rear)
                printf("%d %d %d\n", queue[i++], front, rear);
        }
    }
}

执行上述示例代码并获得以下结果-

**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter the element
1
Value inserted 
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter the element
2
Value inserted 
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter the element
3
Value inserted 
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
Circular Queue Elements are : 
1
2
3
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?2
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter the element
4
Value inserted 
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?3
Circular Queue Elements are : 
2
3
4
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?1
Enter the element
1
OVERFLOW
**********Main Menu**********
=============================
1.insert an element
2.Delete an element
3.Display the queue
4.Exit
Enter your choice ?
4

¥我想奖励错误更正/附加收藏

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-196792-1.html