佇列操作的時間和空間複雜度分析

---

介紹

佇列是一種線性資料結構，它使用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)，因為它們只使用一個操作來執行這些方法。

所有操作的空間複雜度也相同。這是因為它們使用固定記憶體，並且不使用超出該記憶體的記憶體。