資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究雙端佇列（Deque）的應用、優點和缺點
雙端佇列（Deque）或雙端佇列是一種順序線性集合資料佇列，它提供類似於雙端佇列的功能。在這種資料結構中，方法不遵循先進先出（FIFO）規則來處理資料。這種資料結構也稱為雙端佇列，因為元素被插入到佇列的末尾，並從前端移除。對於雙端佇列，我們只能從兩端新增和刪除資料。雙端佇列操作的時間複雜度為 O(1)。雙端佇列有兩種型別：
輸入受限
僅在一端限制輸入。
允許從兩端刪除資料。
輸出受限
僅在一端限制輸出。
允許從兩端插入資料。
以下是一些命令，可以幫助程式設計師對雙端佇列上的資料集執行各種操作：
push_back() - 從雙端佇列的末尾插入一個元素。
push_front() - 從雙端佇列的開頭插入一個元素。
pop_back() - 從雙端佇列的末尾移除元素。
pop_front() - 從雙端佇列的開頭移除元素。
front() - 返回雙端佇列開頭處的元素。
back() - 返回雙端佇列末尾處的元素。
at() - 設定/返回指定索引處的元素。
size() - 返回元素的數量。
empty() - 如果雙端佇列為空，則返回 true。
在迴圈陣列中，我們可以使用雙端佇列操作。如果陣列已滿，則可以從開頭開始該過程。但是對於線性陣列，如果陣列已滿，則無法再插入資料。然後我們會看到一個“溢位彈出視窗”。
雙端佇列的應用
雙端佇列有許多實際應用。
用於作業排程應用程式。
我們可以在 O(1) 時間內執行順時針和逆時針旋轉操作。
雙端佇列演算法也存在於網頁瀏覽器歷史記錄中。
用於排序中的撤銷操作。
雙端佇列的優點
雙端佇列有很多優點。
我們可以從前端和後端新增和刪除資料。
它們的大小是動態的。
雙端佇列提供了執行操作的高效時間。
這裡使用 LIFO 棧。
此處無法進行重新分配。
它是一個透過適當同步實現的執行緒安全過程。
快取友好。
雙端佇列的缺點
雙端佇列的缺點是
雙端佇列過程具有更高的記憶體消耗率。
它在多執行緒中存在同步問題。
無法在所有平臺上實現。
不適合實現排序操作。
雙端佇列的功能數量較少。
雙端佇列操作的演算法
步驟 1 - 考慮一個大小為 n 的雙端佇列陣列。
步驟 2 - 設定兩個指標，"front=-1" 用於前端，"rear=0" 用於設定。
此過程中有很多子部分。在雙端佇列中，我們可以執行多個操作。我們在這裡對它們進行了總結。
在雙端佇列中從前端插入資料的演算法：
步驟 1 - 檢查前端位置。
步驟 2 - 如果 "front<1"，則將 "front=n-1" 應用於最後一個索引。
步驟 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 - 如果 rear 在前端 "rear=0"。轉到前端 "rear = n-1"。
步驟 6 - 否則，rear=rear-1。
檢查雙端佇列是否為空的演算法：
步驟 1 - 如果 front=-1，則雙端佇列為空。
檢查雙端佇列是否已滿的演算法：
步驟 1 - 如果 front=0 且 rear = 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++ 中，雙端佇列實現為向量（vector）的向量。
使用雙端佇列的各種方法
方法 1 - 以一般方式實現雙端佇列
方法 2 - 將元素插入雙端佇列
方法 3 - 從雙端佇列訪問元素
方法 4 - 更改雙端佇列的元素
以一般方式實現雙端佇列
在此 C++ 構建程式碼中，我們以一般方式配置了雙端佇列操作。在此示例中，我們在佇列的後端插入了一個元素，並且整個系統已按照該方式執行。
示例 1
#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; }
輸出
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++ 的演算法和可能的程式碼。
2K+ 瀏覽量
