Struktur Data Deque

Dalam tutorial ini, anda akan mengetahui apa itu antrian berganda (deque). Anda juga akan dapati contoh operasi yang berbeza pada deque di C, C ++, Java dan Python.

Deque atau Double Ended Queue adalah sejenis barisan di mana penyisipan dan penyingkiran elemen dapat dilakukan dari arah depan atau belakang. Oleh itu, ia tidak mengikut peraturan FIFO (First In First Out).

Perwakilan Deque

Jenis-jenis Deque

  • Input Restricted Deque
    Dalam deque ini, input dibatasi pada satu hujung tetapi membenarkan penghapusan di kedua hujungnya.
  • Output Terhad Deque
    Dalam deque ini, output dibatasi pada satu hujung tetapi membenarkan penyisipan pada kedua ujungnya.

Operasi pada Deque

Di bawah ini adalah pelaksanaan larutan pekeliling deque. Dalam susunan bulat, jika susunan penuh, kita bermula dari awal.

Tetapi dalam pelaksanaan array linear, jika array penuh, tidak ada lagi elemen yang dapat disisipkan. Dalam setiap operasi di bawah ini, jika array penuh, "mesej limpahan" dilemparkan.

Sebelum melakukan operasi berikut, langkah-langkah ini diikuti.

  1. Ambil susunan (deque) berukuran n.
  2. Tetapkan dua penunjuk pada kedudukan pertama dan tetapkan front = -1dan rear = 0.
Memulakan susunan dan penunjuk untuk deque

1. Masukkan di Bahagian Depan

Operasi ini menambah elemen di bahagian depan.

  1. Periksa kedudukan depan. Periksa kedudukan depan
  2. Sekiranya front < 1, buat semula front = n-1(indeks terakhir). Beralih ke depan hingga ke hujung
  3. Lain, turunkan depan dengan 1.
  4. Tambahkan kunci 5 baru ke dalam array(front). Masukkan elemen di Depan

2. Masukkan di Belakang

Operasi ini menambahkan elemen ke belakang.

  1. Periksa sama ada array penuh. Periksa sama ada deque penuh
  2. Sekiranya hiasan penuh, mulakan semula rear = 0.
  3. Lain, tingkatkan belakang sebanyak 1. Tingkatkan belakang
  4. Tambahkan kunci 5 baru ke dalam array(rear). Masukkan elemen di belakang

3. Padam dari Depan

Operasi menghapus elemen dari depan.

  1. Periksa sama ada deque itu kosong. Periksa sama ada deque kosong
  2. Sekiranya deque kosong (iaitu front = -1), penghapusan tidak dapat dilakukan ( keadaan underflow ).
  3. Sekiranya deque hanya mempunyai satu elemen (iaitu front = rear), tetapkan front = -1dan rear = -1.
  4. Jika tidak, depan berada di hujung (iaitu front = n - 1), tetapkan ke hadapan front = 0.
  5. Lain , front = front + 1. Menambah bahagian depan

4. Padam dari Belakang

Operasi ini menghapus elemen dari belakang.

  1. Periksa sama ada deque itu kosong. Periksa sama ada deque kosong
  2. Sekiranya deque kosong (iaitu front = -1), penghapusan tidak dapat dilakukan ( keadaan underflow ).
  3. Sekiranya deque hanya mempunyai satu elemen (iaitu front = rear), tetapkan front = -1dan rear = -1, ikuti langkah-langkah di bawah.
  4. Sekiranya belakang berada di bahagian depan (iaitu rear = 0), tetapkan ke depan rear = n - 1.
  5. Lain , rear = rear - 1. Kurangkan bahagian belakang

5. Tandakan Kosong

Operasi ini memeriksa sama ada deque itu kosong. Sekiranya front = -1, deque itu kosong.

6. Periksa Penuh

Operasi ini memeriksa sama ada deque itu penuh. Sekiranya front = 0dan rear = n - 1ATAU front = rear + 1, hiasan itu penuh.

Pelaksanaan Deque di Python, Java, C, dan C ++

Python Java C C ++ 
 # Deque implementaion in python class Deque: def __init__(self): self.items = () def isEmpty(self): return self.items == () def addRear(self, item): self.items.append(item) def addFront(self, item): self.items.insert(0, item) def removeFront(self): return self.items.pop() def removeRear(self): return self.items.pop(0) def size(self): return len(self.items) d = Deque() print(d.isEmpty()) d.addRear(8) d.addRear(5) d.addFront(7) d.addFront(10) print(d.size()) print(d.isEmpty()) d.addRear(11) print(d.removeRear()) print(d.removeFront()) d.addFront(55) d.addRear(45) print(d.items)
 // Deque implementation in Java class Deque ( static final int MAX = 100; int arr(); int front; int rear; int size; public Deque(int size) ( arr = new int(MAX); front = -1; rear = 0; this.size = size; ) boolean isFull() ( return ((front == 0 && rear == size - 1) || front == rear + 1); ) boolean isEmpty() ( return (front == -1); ) void insertfront(int key) ( if (isFull()) ( System.out.println("Overflow"); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (front == 0) front = size - 1; else front = front - 1; arr(front) = key; ) void insertrear(int key) ( if (isFull()) ( System.out.println(" Overflow "); return; ) if (front == -1) ( front = 0; rear = 0; ) else if (rear == size - 1) rear = 0; else rear = rear + 1; arr(rear) = key; ) void deletefront() ( if (isEmpty()) ( System.out.println("Queue Underflow"); return; ) // Deque has only one element if (front == rear) ( front = -1; rear = -1; ) else if (front == size - 1) front = 0; else front = front + 1; ) void deleterear() ( if (isEmpty()) ( System.out.println(" Underflow"); return; ) if (front == rear) ( front = -1; rear = -1; ) else if (rear == 0) rear = size - 1; else rear = rear - 1; ) int getFront() ( if (isEmpty()) ( System.out.println(" Underflow"); return -1; ) return arr(front); ) int getRear() ( if (isEmpty() || rear < 0) ( System.out.println(" Underflow"); return -1; ) return arr(rear); ) public static void main(String() args) ( Deque dq = new Deque(4); System.out.println("Insert element at rear end : 12 "); dq.insertrear(12); System.out.println("insert element at rear end : 14 "); dq.insertrear(14); System.out.println("get rear element : " + dq.getRear()); dq.deleterear(); System.out.println("After delete rear element new rear become : " + dq.getRear()); System.out.println("inserting element at front end"); dq.insertfront(13); System.out.println("get front element: " + dq.getFront()); dq.deletefront(); System.out.println("After delete front element new front become : " + +dq.getFront()); ) )
 // Deque implementation in C #include #define MAX 10 void addFront(int *, int, int *, int *); void addRear(int *, int, int *, int *); int delFront(int *, int *, int *); int delRear(int *, int *, int *); void display(int *); int count(int *); int main() ( int arr(MAX); int front, rear, i, n; front = rear = -1; for (i = 0; i < MAX; i++) arr(i) = 0; addRear(arr, 5, &front, &rear); addFront(arr, 12, &front, &rear); addRear(arr, 11, &front, &rear); addFront(arr, 5, &front, &rear); addRear(arr, 6, &front, &rear); addFront(arr, 8, &front, &rear); printf("Elements in a deque: "); display(arr); i = delFront(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); addRear(arr, 16, &front, &rear); addRear(arr, 7, &front, &rear); printf("Elements in a deque after addition: "); display(arr); i = delRear(arr, &front, &rear); printf("removed item: %d", i); printf("Elements in a deque after deletion: "); display(arr); n = count(arr); printf("Total number of elements in deque: %d", n); ) void addFront(int *arr, int item, int *pfront, int *prear) ( int i, k, c; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *pfront = *prear = 0; arr(*pfront) = item; return; ) if (*prear != MAX - 1) ( c = count(arr); k = *prear + 1; for (i = 1; i <= c; i++) ( arr(k) = arr(k - 1); k--; ) arr(k) = item; *pfront = k; (*prear)++; ) else ( (*pfront)--; arr(*pfront) = item; ) ) void addRear(int *arr, int item, int *pfront, int *prear) ( int i, k; if (*pfront == 0 && *prear == MAX - 1) ( printf("Deque is full."); return; ) if (*pfront == -1) ( *prear = *pfront = 0; arr(*prear) = item; return; ) if (*prear == MAX - 1) ( k = *pfront - 1; for (i = *pfront - 1; i < *prear; i++) ( k = i; if (k == MAX - 1) arr(k) = 0; else arr(k) = arr(i + 1); ) (*prear)--; (*pfront)--; ) (*prear)++; arr(*prear) = item; ) int delFront(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*pfront); arr(*pfront) = 0; if (*pfront == *prear) *pfront = *prear = -1; else (*pfront)++; return item; ) int delRear(int *arr, int *pfront, int *prear) ( int item; if (*pfront == -1) ( printf("Deque is empty."); return 0; ) item = arr(*prear); arr(*prear) = 0; (*prear)--; if (*prear == -1) *pfront = -1; return item; ) void display(int *arr) ( int i; printf(" front: "); for (i = 0; i < MAX; i++) printf(" %d", arr(i)); printf(" :rear"); ) int count(int *arr) ( int c = 0, i; for (i = 0; i < MAX; i++) ( if (arr(i) != 0) c++; ) return c; )
 // Deque implementation in C++ #include 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" << 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 " << 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" << 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" << 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" << endl; return -1; ) return arr(front); ) int Deque::getRear() ( if (isEmpty() || rear < 0) ( cout << " Underflow" << endl; return -1; ) return arr(rear); ) int main() ( Deque dq(4); cout << "insert element at rear end "; 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 "; dq.insertfront(8); cout << "front element: " << dq.getFront() << endl; dq.deletefront(); cout << "after deletion of front element new front element: " << dq.getFront() << endl; )

Kerumitan Masa

Kerumitan masa bagi semua operasi di atas adalah berterusan iaitu O(1).

Aplikasi Struktur Data Deque

  1. Dalam mengurungkan operasi perisian.
  2. Untuk menyimpan sejarah dalam penyemak imbas.
  3. Untuk melaksanakan kedua-dua timbunan dan barisan.

Artikel menarik...