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".

Permohonan baris gilir dua hujung

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.

Kelebihan barisan dua hujung

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

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.

Algoritma operasi baris gilir dua hujung

• 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

Sintaks deque

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.

Pemprosesan pelbagai kaedah menggunakan barisan dua hujung

• Kaedah 1 - Melaksanakan deque secara umum

• Kaedah 2 - Masukkan elemen ke dalam deque

• Kaedah 3 - Mengakses elemen daripada deque

• Kaedah 4 - Menukar elemen deque

Pelaksanaan am baris gilir dua hujung

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.

Contoh 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>

Output

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

Masukkan elemen ke dalam deque

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.

Contoh 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;
}

Output

Initial Deque As We Give: 16, 7, 
Final Deque Is Here: 1997, 16, 7, 2001,

Akses elemen daripada deque

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

Output

Front element are here: 16
Back element are here: 10
Element at index 1 present here: 7
Element at index 0 present here: 16

Tukar elemen deque

Dalam kod ini, kita boleh menggunakan kaedah at() untuk menggantikan atau menukar elemen deque tertentu itu.

Contoh 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;
}

Output

Initial Deque: 7, 16, 10, 1997, 2001, 
Updated Deque: 2022, 5, 10, 1997, 2001,

Kesimpulan

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!