队列操作的时间和空间复杂性分析

简介

队列是一种线性数据结构，使用先进先出的方法来插入和删除其元素。它可以通过使用数组和链表来实现。在本教程中，我们将分析基于数组的队列在不同操作中的时间和空间复杂性。

使用数组实现队列

队列的原理是它的先进先出（FIFO）方法，它指出首先进入队列的元素将首先从队列中被删除。它的元素被插入到后端。队列中的元素从前端删除。现实生活中的队列例子是售票窗口前的一个队列。

我们可以用数组和链接列表来实现队列。在一个基于数组的队列中，队列的大小最初是被定义的。

队列的重要功能是

enQueue() – 它用于在队列中插入数据。
deQueue() – 它用于从队列中删除数据。
isEmpty() – 它将检查队列是否为空。它返回一个布尔值。
peek() – 返回队列的高峰值。

时间复杂度 - 它是用于执行的时间量。

空间复杂度 - 它是内存利用率。

例1

分析C/C++中不同队列操作的时间和空间复杂度

#include <iostream>
using namespace std;
#define capacity 10

class Queue  {
public:
   int queue[capacity];
   int front;
   int rear;

   Queue() {
      front = -1;
      rear = -1;
   }

   void enqueue(int val1) {
      if (front == -1) {
         front++;
      }

      if (rear == capacity - 1) {
         cout << "Queue is overflow!!!  
";
         return;
      }

      queue[++rear] = val1;
      cout << " Successful insertion of " << val1 <<"  
";
   }
};

int main() {
   Queue aq;

   //using enQueue() to insert 5 and 7 in the queue
   aq.enqueue(5);
   aq.enqueue(7);

   return 0;
}

输出

Successful insertion of 5
Successful insertion of 7

分析复杂性

时间复杂度。使用数组的enQueue()操作的时间复杂性为O(1)。

空间复杂度：它是恒定的，没有使用额外的空间。它是O(1)

例2

在C/C++中使用deQueue()操作寻找队列操作的时间和空间复杂性分析

#include <iostream>
using namespace std;
#define capacity 10

class Queue {
public:
   int queue[capacity];
   int last;
   int first;

   Queue() {
      last = -1;
      first = -1;
   }

   void enqueue(int val1) {
      if (last == -1) {
         last++;
      }

      if (first == capacity - 1) {
         cout << "Queue overflow!!!  
";
         return;
      }

      queue[++first] = val1;
   }

   void dequeue() {
      if (last == -1 || last > first)  {
         cout << "Queue is empty!!!  
";
         return;
      }

      cout << "Element deleted from queue is  : " << queue[last++] << "  
";
   }
};
int main() {
    Queue aq;
 //Inserting Queue elements
    aq.enqueue(7);
    aq.enqueue(2);

   //removing Queue element
    aq.dequeue();

    return 0;
}

输出

Element deleted from Queue is 7

分析复杂性

时间复杂度。O(1)：这是因为使用了一个单一的算术运算符。

空间复杂度。O(1)

例3

使用C/C++中队列的peek()操作寻找时间和空间复杂度分析

#include <iostream>
using namespace std;
#define capacity 10

class Queue  {
public:
   int queue[capacity];
   int last;
   int first;

   Queue() {
      last = -1;
      first = -1;
   }

   void enqueue(int v) {
      if (last == -1) {
         last++;
      }

      if (first == capacity - 1) {
         cout << "Queue is overflowed!!!  
";
         return;
      }

      queue[++first] = v;
   }

   void peek() {
      if (last == -1 || last > first)  {
         cout << "Queue is empty !  
";
         return;
      }

      cout << "Front Element of the Queue is : " << queue[last] << "  
";
   }
};

int main(){
   Queue aq;


   aq.enqueue(16);
   aq.enqueue(20);

   //it will give the first element of the Queue   
   aq.peek();

   return 0;
}

输出

Front Element of the Queue is : 16

复杂性分析

时间复杂度 = O(1)

空间复杂度 = O(1)

例四

使用C/C++中的isempty()操作寻找队列操作的时间和空间复杂性分析

#include <iostream>
using namespace std;
#define capacity 10

class Queue  {
public:
   int queue[capacity];
   int head;
   int tail;

   Queue() {
      head = -1;
      tail = -1;
   }

   bool isempty() {

      if (head == -1 || head > tail)  {
         return 1;
      }

      return 0;
   }
};

int main() {
   Queue aq;

   if (aq.isempty())  {
      cout << "It is empty queue  
";
   }
   else 
      cout << "Queue has space   
";
   return 0;
}