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

---

介绍

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

使用数组实现队列

队列的原理是其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)

示例4

使用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;
}

输出

It is empty Queue

复杂度分析

时间复杂度 = O(1)。它检查队列的元素，这是常数。

空间复杂度 = O(1)

结论

在本教程中，我们分析了基于数组的队列对于enQueue()、deQueue()、peek()和isEmpty()操作的时间和空间复杂度。我们发现它们都具有相同的时间复杂度O(1)，因为它们只使用一个操作来执行这些方法。

所有操作的空间复杂度也相同。这是因为它们使用固定内存，并且不使用超出该内存的内存。