Rumah > Artikel > pembangunan bahagian belakang > Aplikasi, Kelebihan dan Kekurangan Deque
Deque atau baris gilir dua hujung ialah baris gilir data koleksi linear berjujukan yang menyediakan fungsi yang serupa dengan baris gilir dua hujung. Dalam struktur data ini, kaedah tidak mengikut peraturan masuk dahulu keluar (FIFO) untuk pemprosesan data. Struktur data ini juga dipanggil deque kerana elemen dimasukkan pada penghujung baris gilir dan dikeluarkan dari hadapan. Dengan deque, kami hanya boleh menambah dan mengalih keluar data dari kedua-dua hujung. Kerumitan masa operasi deque ialah O(1). Ada dua jenis deque -
Input adalah terhad
Had input satu hujung.
Membenarkan pemadaman data dari kedua-dua hujung.
Output terhad
Had keluaran satu hujung.
Membenarkan memasukkan data ke kedua-dua hujungnya.
Arahan berikut membantu pengekod melakukan pelbagai operasi menggunakan pengumpulan set data pada deque -
push_back() - Masukkan elemen dari belakang deque.
push_front() - Masukkan elemen dari hadapan deque.
pop_back() - Mengeluarkan elemen dari belakang deque.
pop_front() - Mengeluarkan elemen dari hadapan deque.
depan() - Mengembalikan elemen hadapan deque.
back() - Mengembalikan elemen di bahagian belakang deque.
at() - Tetapkan/kembalikan indeks yang ditentukan.
size() - Mengembalikan bilangan elemen.
empty() - Mengembalikan benar jika deque kosong.
Dalam tatasusunan bulat kita boleh menggunakan operasi deque. Jika tatasusunan penuh maka kita boleh memulakan proses dari awal. Tetapi dengan tatasusunan linear, jika tatasusunan penuh, tiada lagi data boleh dimasukkan. Kemudian kita boleh melihat "popup limpahan".
Deque mempunyai banyak aplikasi masa nyata yang tersedia.
Untuk permohonan penjadualan kerja.
Kami boleh melakukan operasi putaran mengikut arah jam dan lawan jam dalam masa O(1).
Algoritma deque juga terdapat dalam sejarah pelayar web.
Untuk membuat asal operasi dalam pengisihan.
Deque mempunyai banyak kelebihan.
Kita boleh menambah dan memadam data dari hadapan dan belakang.
Saiznya adalah dinamik.
Deque menyediakan pemasaan yang cekap untuk melaksanakan operasi.
Timbunan LIFO digunakan di sini.
Pengedaran semula tidak boleh dilakukan di sini.
Ini adalah proses selamat benang dengan penyegerakan yang betul.
Mesra cache.
Kelemahan barisan dua hujung ialah
Kadar penggunaan memori proses deque adalah tinggi.
Ia mempunyai isu penyegerakan berbilang benang.
Tidak tersedia pada semua platform.
Tidak sesuai untuk melaksanakan operasi pengisihan.
Deque mempunyai ciri yang lebih sedikit.
Langkah 1 - Pertimbangkan susunan deque saiz n.
Langkah 2 - Tetapkan dua penunjuk kepada "depan=-1" (bermaksud depan) dan "belakang=0" (bermaksud set).
Terdapat banyak sub-bahagian untuk proses ini. Kita boleh melakukan beberapa operasi dalam deque. Kami meringkaskannya di sini.
Algoritma untuk memasukkan data dari hadapan dalam deque:-
Langkah 1 - Periksa kedudukan hadapan.
Langkah 2 - Jika "depan
Langkah 3 - Jika tidak, kita perlu mengurangkan "depan" sebanyak 1.
Langkah 4 - Tambahkan elemen kunci baharu pada bahagian hadapan tatasusunan.
Algoritma untuk memasukkan data selepas deque:-
Langkah 1 - Semak sama ada tatasusunan penuh.
Langkah 2 - Jika penuh, sapukan "rear=0".
Langkah 3 - Jika tidak, tingkatkan nilai "belakang" sebanyak 1.
Langkah 4 - Tambahkan kekunci baharu pada "array[rear]" sekali lagi.
Algoritma untuk memadam data dari hadapan deque:-
Langkah 1 - Semak sama ada deque kosong.
Langkah 2 - Jika senarai kosong ("depan=-1"), ia adalah keadaan aliran bawah dan pemadaman tidak boleh dilakukan.
Langkah 3 - Jika hanya ada satu elemen dalam deque. Kemudian "depan=belakang=-1".
Langkah 4 - Jika tidak, "depan" berada di hujung, kemudian tetapkan kepada "depan=0".
Langkah 5 - Jika tidak, depan=depan+1.
Algoritma untuk memadam data dari belakang deque:-
Langkah 1 - Semak sama ada deque kosong.
Langkah 2 - Jika kosong ("depan=-1"), pemadaman tidak boleh dilakukan. Ini adalah keadaan aliran bawah.
Langkah 3 - Jika deque hanya mempunyai satu data, maka "depan=belakang=-1".
Langkah 4 - Jika tidak, ikut langkah di bawah.
Langkah 5 - Jika belakang berada di hadapan "rear=0". Pergi ke hadapan "belakang = n-1".
Langkah 6 - Jika tidak, belakang=belakang-1.
Algoritma untuk menyemak sama ada deque kosong:-
Langkah 1 - Jika depan=-1, maka deque kosong.
Algoritma untuk menyemak sama ada deque penuh:-
Langkah 1 - jika sebelum=0 dan selepas=n-1
Langkah 2 - Atau, depan=belakang+1
deque< object_type > deque_name; deque<int> deque1 = {11, 21, 31, 41, 51}; deque<int> deque2 {10, 20, 30, 40, 50};
Dalam struktur data, deque mewarisi beberapa sifat tindanan dan baris gilir. Dalam C++, deque dilaksanakan sebagai vektor vektor.
Kaedah 1 - Melaksanakan deque secara umum
Kaedah 2 - Masukkan elemen ke dalam deque
Kaedah 3 - Mengakses elemen daripada deque
Kaedah 4 - Menukar elemen deque
Dalam kod binaan C++ ini, kami mengkonfigurasi operasi deque dengan cara generik. Dalam contoh ini, kami memasukkan elemen di bahagian belakang baris gilir dan keseluruhan sistem dilakukan dengan cara ini.
<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
Dalam kod ini, kami cuba mencipta kod C++ untuk memasukkan elemen ke dalam deque. Terdapat dua cara untuk melakukan ini.
push_back() - Memasukkan elemen di hujung tatasusunan.
push_front() - Memasukkan elemen pada permulaan tatasusunan.
#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,
Kita boleh mengakses elemen dalam deque menggunakan dua kaedah.
depan() - Di bahagian hadapan kita boleh mendapatkan nilai pulangan.
back() - Mengembalikan data berikut.
at() - Mengembalikan daripada indeks yang ditentukan.
#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
Dalam kod ini, kita boleh menggunakan kaedah at() untuk menggantikan atau menukar elemen deque tertentu itu.
#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,
Melalui artikel ini, kami mengetahui tentang baris gilir dua hujung, kaedah pengendaliannya, aplikasi, kelebihan dan kekurangan, serta algoritma dan kod yang mungkin menggunakan C++.
Atas ialah kandungan terperinci Aplikasi, Kelebihan dan Kekurangan Deque. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!