- Double Ended Queue Classification
- Basic Deque Operations
- Deque Illustration
- Deque Implementation
- Mga Application
- Konklusyon
Isang Malalim na Tutorial sa Deque o Double-ended Queue sa C++. Ipinapaliwanag ng Tutorial ang Ano ang Deque, Basic Operations, C++ & Pagpapatupad at Mga Aplikasyon ng Java:
Ang double ended queue o tinatawag na "Deque" ay isang pangkalahatang bersyon ng Queue.
Ang pagkakaiba sa pagitan ng Queue at Deque ay hindi ito sumusunod sa FIFO (First In, First Out) approach. Ang pangalawang tampok ng Deque ay maaari tayong magpasok at mag-alis ng mga elemento mula sa alinman sa harap o likurang dulo.
Double Ended Queue Classification
Maaari ang Deque uriin tulad ng sumusunod:
Input-restricted Deque: Sa input-restricted, ang pagtanggal ay maaaring gawin mula sa magkabilang dulo ngunit ang pagpasok ay maaari lamang gawin sa hulihan ng queue.
Output-restricted Deque: Sa output-restricted queue, ang pagpasok ay maaaring gawin mula sa magkabilang dulo ngunit ang pagtanggal ay ginagawa lamang sa isang dulo i.e. ang front end ng queue.
Maaari rin kaming magpatupad ng mga stack at queues gamit ang deque.
Basic Deque Operations
Ang mga sumusunod ay ang mga pangunahing operasyon na maaaring isagawa sa deque.
- ipasok ang harap: Ipasok o idagdag ang isang item sa harap ng deque.
- insertLast: Ipasok o magdagdag ng item sa ang hulihan ng deque.
- deleteFront: I-delete o alisin ang item sa harap ng queue.
- delete ang huling: I-delete o alisin ang item mula sa likuran ngqueue.
- getFront: Kinukuha ang front item sa deque.
- getLast: Kinukuha ang huling item sa queue.
- isEmpty: Tinitingnan kung walang laman ang deque.
- isFull: Tinitingnan kung puno na ang deque.
Deque Illustration
Ang isang walang laman na deque ay kinakatawan tulad ng sumusunod:
Susunod, ilalagay namin ang elemento 1 sa harap.
Ngayon, ipinapasok namin ang elemento 3 sa likuran.
Susunod, idaragdag namin ang elemento 5 sa harap at kapag dinagdagan ang mga punto sa harap sa 4.
Pagkatapos, ipinapasok namin ang mga elemento 7 sa likuran at 9 sa harap. Ang deque ay magiging hitsura tulad ng ipinapakita sa ibaba.
Susunod, alisin natin ang isang elemento sa harap.
Kaya, nakikita natin na kapag ang mga elemento ay ipinasok sa harap, ang posisyon sa harap ay nababawasan habang ito ay nadaragdagan kapag ang isang elemento ay tinanggal. Para sa hulihan, ang posisyon ay dinadagdagan para sa pagpasok at binabawasan para sa pag-alis .
Deque Implementation
C++ Deque Implementation
Maaari kaming magpatupad ng deque sa C++ gamit ang mga arrays pati na rin ang isang naka-link na listahan. Bukod dito, ang Standard Template Library (STL) ay may klase na "deque" na nagpapatupad ng lahat ng function para sa istruktura ng data na ito.
Ang array na pagpapatupad ng deque ay ibinigay sa ibaba. Dahil isa itong double-ended queue, ginamit namin ang mga circular arrayspagpapatupad.
#includeusing namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array[MAX_size]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull() return ((front == 0 && rear == size-1) // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout "Overflow!!\n" endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array[front] = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout " Overflow!!\n " endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array[rear] = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout "Queue Underflow!!\n" endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout " Underflow!!\n" endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout " Underflow!!\n" endl; return -1 ; } return array[front]; } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear 0) { cout " Underflow!!\n" endl; return -1 ; } return array[rear]; } //main program int main() { Deque dq(5); cout "Insert element 1 at rear end \n"; dq.insertrear(1); cout "insert element 3 at rear end \n"; dq.insertrear(3); cout "rear element of deque " " " dq.getRear() endl; dq.deleterear(); cout "After deleterear, rear = " dq.getRear() endl; cout "inserting element 5 at front end \n"; dq.insertfront(5); cout "front element of deque " " " dq.getFront() endl; dq.deletefront(); cout "After deletefront, front = " dq.getFront() endl; return 0; }
Output:
Ipasok ang elemento 1 sa hulihan ng deque 3
Pagkatapos deleterear, rear =
paglalagay ng element 5 sa front end
front element of deque 5
Pagkatapos deletefront, front =
Pagpapatupad ng Java Deque
Ang deque interface sa Java, ang “java.util.Deque” ay nagmula sa interface ng “java.util.Queue”. Maaaring gamitin ang Deque bilang isang pila (First In, First Out) o isang stack (Last In, First Out). Ang mga pagpapatupad na ito ay gumagana nang mas mabilis kaysa sa naka-link na listahan.
Ibinigay sa ibaba ang hierarchy para sa Deque interface sa Java.
Kailangan nating tandaan ang ilang punto tungkol sa interface ng Deque sa Java:
- Ang pagpapatupad ay hindi thread-safe dahil walang panlabas na pag-synchronize.
- Ang Deque ay hindi suportahan ang concurrency ng maraming thread.
- Ang ipinatupad ni Deque gamit ang mga array ay hindi pinapayagan ang paggamit ng mga NULL na elemento.
- Pinapayagan ang mga array na lumago ayon sa mga kinakailangan, na may kapasidad na walang restriction at resizable array support bilang dalawang pinakamahalagang tampok.
Ang mga sumusunod ay ang iba't ibang pamamaraan na sinusuportahan ng interface ng Deque:
Hindi. | Paraan | Paglalarawan |
---|---|---|
1 | add(element) | Nagdaragdag ng elemento sa buntot. |
2 | addFirst(element) | Nagdaragdag ng elemento saulo/harap. |
3 | addLast(element) | Nagdaragdag ng elemento sa buntot/likod. |
4 | alok(elemento) | Nagdaragdag ng elemento sa buntot; nagbabalik ng boolean value upang isaad kung matagumpay ang pagpapasok. |
5 | offerFirst(element) | Nagdaragdag ng elemento sa head; nagbabalik ng boolean value upang isaad kung matagumpay ang pagpapasok. |
6 | offerLast(element) | Nagdaragdag ng elemento sa buntot; nagbabalik ng boolean value upang isaad kung matagumpay ang pagpapasok. |
7 | iterator() | Nagbabalik ng iterator para sa deque. |
8 | descendingIterator() | Ibinabalik ang isang iterator na may reverse order para sa deque na ito. |
9 | push(element) | Nagdaragdag ng elemento sa head ng deque. |
10 | pop(element) | Nag-aalis ng elemento mula sa ulo ng deque at ibinabalik ito. |
11 | removeFirst() | Aalisin ang elemento sa ang ulo ng deque. |
12 | removeLast() | Aalisin ang elemento sa buntot ng deque. |
13 | poll() | Kinukuha at inaalis ang unang elemento ng deque(kinakatawan ng pinuno ng deque); ibinabalik ang NULL kung walang laman ang deque. |
14 | pollFirst() | Kinukuha at inaalis ang unang elemento ng deque na ito; nagbabalik ng null kung ang deque na ito aywalang laman. |
15 | pollLast() | Kinukuha at inaalis ang huling elemento ng deque na ito; nagbabalik ng null kung walang laman ang deque na ito. |
16 | peek() | Kinukuha ang head(unang elemento ng deque) ng queue na kinakatawan sa pamamagitan ng deque na ito; nagbabalik ng null kung walang laman ang deque na ito. Tandaan: Hindi inaalis ng operasyong ito ang elemento. |
17 | peekFirst() | Kinukuha ang unang elemento ng deque na ito; nagbabalik ng null kung walang laman ang deque na ito. Tandaan: Hindi inaalis ng operasyong ito ang elemento. |
18 | peekLast() | Kinukuha ang huling elemento ng deque na ito, o ibinabalik ang null kung walang laman ang deque na ito. Tandaan: Hindi inaalis ng operasyong ito ang elemento. |
Ang sumusunod na pagpapatupad ng Java ay nagpapakita ng iba't ibang mga operasyong tinalakay sa itaas.
import java.util.*; class Main { public static void main(String[] args) { Dequedeque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println("The deque : " + deque + "\n"); // Iterate through the queue elements. System.out.println("Standard Iterator"); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(" " + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("After peek: " + deque); // Pop returns the head, and removes it from // the deque System.out.println("\nPop " + deque.pop()); System.out.println("After pop: " + deque); // We can check if a specific element exists // in the deque System.out.println("\nContains element 3?: " + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println("Deque after removing " + "first and last elements: " + deque); } }
Output:
Ang deque : [11, 7, 3, 1, 5, 9, 13]
Karaniwang Iterator
11 7 3 1 5 9 13
Baligtad Iterator
13 9 5 1 3 7 1
Silip 11
Pagkatapos sumilip: [11, 7, 3, 1, 5, 9, 13]
Pop 11
Pagkatapos pag-pop: [7, 3, 1, 5, 9, 13]
Naglalaman ng elemento 3?: totoo
Deque pagkatapos tanggalin ang una at huling elemento: [3, 1, 5, 9]
Sa programa sa itaas, ginamit namin ang Deque interface ng Java at tinukoy namin ang isang deque ng mga elemento ng integer. Pagkatapos ay nagsagawa kami ng iba't ibang mga operasyon sa deque na ito at output ang mga resulta ng mga operasyong ito ayipinapakita.
Mga Application
Maaaring gamitin ang Deque sa ilan sa mga sumusunod na application.
#1) Algorithm ng Pag-iiskedyul: Ang isang algorithm sa pag-iiskedyul, ang "A-steal scheduling algorithm" ay nagpapatupad ng pag-iiskedyul ng gawain para sa iba't ibang mga processor sa multiprocessor system. Gumagamit ang pagpapatupad na ito ng deque at nakukuha ng processor ang unang elemento mula sa deque para sa pagpapatupad.
#2) I-undo ang Listahan ng Mga Aktibidad: Sa mga software application, marami kaming mga aksyon. Ang isa ay "i-undo". Kapag nagsagawa kami ng pag-undo ng pagkilos nang maraming beses, ang lahat ng mga pagkilos na ito ay iniimbak sa isang listahan. Ang listahang ito ay pinananatili bilang isang deque upang madali kaming magdagdag/mag-alis ng mga entry mula sa anumang dulo.
#3) Alisin Ang Mga Entry Pagkalipas ng Ilang Oras: Pag-refresh ng mga app mga entry sa kanilang listahan tulad ng mga app na naglilista ng mga stock na entry, atbp. Ang mga app na ito ay nag-aalis ng mga entry pagkaraan ng ilang oras at naglalagay din ng mga bagong entry. Ginagawa ito gamit ang isang deque.
Konklusyon
Ang Deque ay isang double-ended queue na nagbibigay-daan sa amin na magdagdag/mag-alis ng mga elemento mula sa magkabilang dulo i.e. harap at likuran, ng pila. Maaaring ipatupad ang Deque gamit ang mga array o naka-link na listahan. Gayunpaman, mayroon din kaming klase ng Standard Template Library (STL) na nagpapatupad ng iba't ibang operasyon ng Deque.
Sa Java, mayroon kaming Deque interface na minana mula sa queue interface para ipatupad ang Deque. Bukod sa mga pangunahing karaniwang pagpapatakbo ng Deque, sinusuportahan ng interface na ito ang iba't ibangiba pang mga operasyon na maaaring isagawa sa Deque.
Ang Deque ay karaniwang ginagamit para sa mga application na nangangailangan ng pagdaragdag/pag-alis ng mga elemento mula sa magkabilang dulo. Madalas din itong ginagamit sa pag-iiskedyul ng mga processor sa mga multi-processor system.
Tingnan Ang Kumpletong Serye ng Pagsasanay sa C++