c - 通过数组实现线性队列

Question

我通过数组实现制作了一个线性队列数据结构。

在线性队列数据结构中，元素从前面插入，从后面删除。
一般来说，当后面的元素位于数组的最后一个索引时，即使前面有地方可以容纳更多元素，我们也会显示溢出消息。

为此，我提出了一种解决方案，每次执行删除操作时，我都会通过循环操作将每个元素移动一个位置。

但是当我在互联网上搜索线性队列的数组实现时，甚至没有一个解决方案实现这种方法。即使在 geeksforgeeks 中他们也没有使用过这种方法。由于这种方法的应用显而易见，为什么没有任何标准解决方案应用它。

它会增加程序的时间复杂度吗？

#include<stdio.h>
#include<stdlib.h>
//the MAX is defined for array size
#define MAX 5
int q[MAX];
//here r indicates the index of last element in queue
int r=-1;
//function to insert element in queue
void insert();
//function to delete an element from queue
int delet();
//function to delete all the elements from the queue
void traverse();
int main()
{
    int choice;
    int value;
    printf("in 1\n");
    while(1)
    {
        printf("1. To insert an element to queue\n");
        printf("2. To delete an element from queue\n");
        printf("3. To delete all the elements from queue\n");
        printf("4. To Exit\n");
        printf("enter choice\n");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:insert();
                   break;
            case 2:value=delet();
                   value==-1?printf("queue is empty\n"):printf("the  
                   deleted element is %d\n",value);
                   break;
            case 3:traverse();
                   break;
            case 4:exit(0);
            default:printf("Enter a valid choice\n");
         }
    }
}
void insert()
{
    int item;
    //this is the condition for overflow
    if(r==MAX-1)
        printf("queue is full\n");
    else
    {
        printf("Enter item other than -1\n");
        scanf("%d",&item);
        r=r+1;
        q[r]=item;
    }
}
int delet()
{
    int temp,i;
    if(r==-1)
        return -1;
    else
    {
        temp = q[0];
        for(i=0;i<r;i++)
            q[i]=q[i+1];
        r=r-1;
        return temp;
    }
}
void traverse()
{
    int i;
    for(i=0;i<=r;i++)
        printf("%d\n",q[i]);
}

Answer 1

您的方法的问题在于需要进行大量处理才能将所有内容上移一位。在您的 delet 函数中，您有以下代码:

{
    temp = q[0];
    for(i=0;i<r;i++)
        q[i]=q[i+1];
    r=r-1;
    return temp;
}

现在，假设队列中有 100 万个项目。当您从队列中删除一个项目时，您必须将 999,999 个项目向上移动一位。从计算机角度来说，这将需要很长时间。

就算法复杂度而言，从循环队列中删除是一个 O(1) 操作:无论队列中有多少项，它都需要相同的时间。您的删除方法是一个 O(n) 操作:删除项目所需的时间与队列中项目的数量成正比。

从功能上来说，您的实现没有任何问题。但从性能的角度来看，你的实现会比循环队列慢得多。对于小型测试程序，您不会注意到这一点，但是当您开始向队列添加数千或数百万个内容时，您的代码可能会慢得令人无法接受:比循环队列慢数千倍。