應用、優勢和缺點的雙端隊列
- PHPz轉載
- 2023-09-06 18:13:06587瀏覽
Deque或雙端佇列是一種順序線性收集資料佇列，提供類似雙端佇列的功能。在此資料結構中，此方法不遵循先進先出（FIFO）規則進行資料處理。這種資料結構也稱為雙端佇列，因為元素插入到佇列的末尾並從前面刪除。對於雙端佇列，我們只能從兩端新增和刪除資料。雙端佇列操作的時間複雜度為O(1)。有兩種類型的雙端隊列 -
輸入受限
單端輸入限制。
允許從兩端刪除資料。
輸出受限
單端輸出限制。
允許兩端插入資料。
以下命令可協助編碼人員使用雙端佇列上的資料集池執行各種操作 -
push_back() - 從雙端佇列的後面插入一個元素。
push_front() - 從雙端隊列的前面插入一個元素。
pop_back() - 從雙端佇列後面刪除元素。
pop_front() - 從雙端隊列的前面刪除元素。
front() - 傳回雙端隊列前面的元素。
back() - 傳回雙端佇列後面的元素。
at() - 設定/傳回指定索引處。
size()-傳回元素的數量。
empty() - 如果雙端佇列為空，則傳回 true。
在循環數組中我們可以使用雙端隊列操作。如果數組已滿，那麼我們可以從頭開始該過程。但對於線性數組，如果數組已滿，則無法插入更多資料。然後我們可以看到一個「溢出彈出視窗」。
雙端佇列的應用
Deque 有很多即時應用程式可供使用。
用於作業排程應用程式。
在 O(1) 時間內我們可以執行順時針和逆時針旋轉操作。
雙端佇列演算法也存在於網頁瀏覽器歷史記錄中。
用於排序中的撤銷操作。
雙端佇列的優點
Deque 有很多優點。
我們可以從正面和背面新增和刪除資料。
它們的大小是動態的。
Deque 提供了執行操作的高效時序。
此處使用了 LIFO 堆疊。
此處無法重新指派。
這是一個具有適當同步的執行緒安全性程序。
快取友善。
雙端佇列的缺點
雙端佇列的缺點是
Deque進程記憶體消耗率較高。
它存在多執行緒同步問題。
無法在所有平台上實現。
不適合實作排序運算。
Deque 的功能較少。
雙端佇列操作的演算法
第 1 步 - 考慮一個大小為 n 的雙端佇列陣列。
第 2 步 - 將兩個指標設定為「front=-1」（表示 front）和「rear=0」（表示 set）。
這個過程有很多子部分。在雙端佇列中我們可以執行多個操作。我們在這裡總結了它們。
在雙端佇列中從前面插入資料的演算法：-
#第 1 步 - 檢查前面的位置。
第 2 步 - 如果“front
第 3 步 - 否則，我們需要將「front」減少 1。
第 4 步 - 將新的鍵元素新增到陣列的前面位置。
在雙端佇列後面插入資料的演算法：-
第 1 步 - 檢查陣列是否已滿。
第 2 步 - 如果已滿，則套用「rear=0」。
第 3 步 - 否則，將「rear」的值增加 1。
第 4 步 - 再次將新鍵新增至「array[rear]」。
從雙端佇列前面刪除資料的演算法：-
第 1 步 - 檢查雙端佇列是否為空。
第 2 步 - 如果清單為空（「front=-1」），則為下溢條件，無法進行刪除。
步驟 3 - 如果雙端佇列中只有一個元素。然後“front=rear=-1”。
第 4 步 - 否則，「front」位於末尾，然後設定為「front=0」。
第 5 步 - 否則，front=front 1。
從雙端佇列後面刪除資料的演算法：-
第 1 步 - 檢查雙端佇列是否為空。
步驟 2 - 如果為空（「front=-1」），則無法執行刪除。這是下溢條件。
第 3 步 - 如果雙端隊列只有一個數據，則「front=rear=-1」。
第 4 步 - 否則，請按照下列步驟操作。
步驟 5 - 如果後部位於前面「後部=0」。轉到前面“rear = n-1”。
第 6 步 - 否則，rear=rear-1。
檢查雙端佇列是否為空的演算法：-
第 1 步 - 如果 front=-1，則雙端隊列為空。
檢查雙端佇列是否已滿的演算法：-
步驟 1 - 如果前=0 且後面= n-1
第 2 步 - 或者，front=rear 1
雙端佇列的語法
deque< object_type > deque_name;
deque<int> deque1 = {11, 21, 31, 41, 51};
deque<int> deque2 {10, 20, 30, 40, 50};
在資料結構中，雙端佇列繼承了堆疊和佇列的一些屬性。在 C 中，雙端隊列被實現為向量的向量。
使用雙端佇列的各種方法的處理
方法 1 - 以一般方式實作雙端佇列
#方法 2 - 將元素插入雙端佇列
#方法 3 - 從雙端佇列存取元素
方法 4 - 更改雙端佇列的元素
#雙端佇列的一般實作
在此 C 建置程式碼中，我們以通用方式配置了雙端佇列操作。在這個例子中，我們在佇列的後端插入了一個元素，整個系統就是按照這種方式執行的。
範例 1
<iostream>#include <iostream>
using namespace std;
#define MAX 10
class Deque {
int arr[MAX];
int front;
int rear;
int size;
public:
Deque(int size) {
front = -1;
rear = 0;
this->size = size;
}
void insertfront(int key);
void insertrear(int key);
void deletefront();
void deleterear();
bool isFull();
bool isEmpty();
int getFront();
int getRear();
};
bool Deque::isFull() {
return ((front == 0 && rear == size - 1) ||
front == rear + 1);
}
bool Deque::isEmpty() {
return (front == -1);
}
void Deque::insertfront(int key) {
if (isFull()) {
cout << "Overflow\n"
<< endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (front == 0)
front = size - 1;
else
front = front - 1;
arr[front] = key;
}
void Deque ::insertrear(int key) {
if (isFull()) {
cout << " Overflow\n " << endl;
return;
}
if (front == -1) {
front = 0;
rear = 0;
}
else if (rear == size - 1)
rear = 0;
else
rear = rear + 1;
arr[rear] = key;
}
void Deque ::deletefront() {
if (isEmpty()) {
cout << "Queue Underflow\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (front == size - 1)
front = 0;
else
front = front + 1;
}
void Deque::deleterear() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return;
}
if (front == rear) {
front = -1;
rear = -1;
} else if (rear == 0)
rear = size - 1;
else
rear = rear - 1;
}
int Deque::getFront() {
if (isEmpty()) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[front];
}
int Deque::getRear() {
if (isEmpty() || rear < 0) {
cout << " Underflow\n"
<< endl;
return -1;
}
return arr[rear];
}
int main() {
Deque dq(4);
cout << "insert element at rear end \n";
dq.insertrear(5);
dq.insertrear(11);
cout << "rear element: "
<< dq.getRear() << endl;
dq.deleterear();
cout << "after deletion of the rear element, the new rear element: " << dq.getRear() << endl;
cout << "insert element at front end \n";
dq.insertfront(8);
cout << "front element: " << dq.getFront() << endl;
dq.deletefront();
cout << "after deletion of front element new front element: " << dq.getFront() << endl;
}
</iostream>
輸出
insert element at rear end rear element: 11 after deletion of the rear element, the new rear element: 5 insert element at front end front element: 8 after deletion of front element new front element: 5
將元素插入雙端佇列
在此程式碼中，我們嘗試建立 C 程式碼以將元素插入雙端佇列。有兩種方法可以執行此操作。
push_back() - 在陣列結尾插入元素。
push_front() - 在陣列的開頭插入元素。
範例 2
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {16, 7};
cout << "Initial Deque As We Give: ";
for (const int& num : nums) {
cout << num << ", ";
}
nums.push_back(2001);
nums.push_front(1997);
cout << "\nFinal Deque Is Here: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}
輸出
Initial Deque As We Give: 16, 7, Final Deque Is Here: 1997, 16, 7, 2001,
從雙端佇列存取元素
我們可以使用兩種方法來存取雙端佇列中的元素。
front() - 在前面我們可以得到回傳值。
back() - 傳回後面的資料。
at() - 從指定索引返回。
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums {16, 07, 10};
cout << "Front element are here: " << nums.front() << endl;
cout << "Back element are here: " << nums.back() << endl;
cout << "Element at index 1 present here: " << nums.at(1) << endl;
cout << "Element at index 0 present here: " << nums[0];
return 0;
}
輸出
Front element are here: 16 Back element are here: 10 Element at index 1 present here: 7 Element at index 0 present here: 16
更改雙端隊列的元素
在此程式碼中，我們可以使用 at() 方法來取代或變更該特定雙端佇列的元素。
範例 4
#include <iostream>
#include <deque>
using namespace std;
int main() {
deque<int> nums = {07,16,10,1997,2001};
cout << "Initial Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
nums.at(0) = 2022;
nums.at(1) = 10-05;
cout << "\nUpdated Deque: ";
for (const int& num : nums) {
cout << num << ", ";
}
return 0;
}
輸出
Initial Deque: 7, 16, 10, 1997, 2001, Updated Deque: 2022, 5, 10, 1997, 2001,
結論
透過這篇文章，我們了解了雙端佇列，它的操作方法、應用、優缺點以及演算法和使用C 可能的程式碼。
以上是應用、優勢和缺點的雙端隊列的詳細內容。更多資訊請關注PHP中文網其他相關文章！