Dersdarek Kûrahî li ser Deque an Dora Du-dawî di C++ de. Tutorial rave dike Deque çi ye, Operasyonên Bingehîn, C ++ & amp; Pêkanîna Java û Serlêdan:
Dara ducarî an jî bi tenê jê re "Deque" tê gotin guhertoyek giştî ya Queue ye.
Cûdahiya di navbera Queue û Deque de ev e ku ew li pey FIFO nayê. (Pirst In, First Out) nêzîkatiya. Taybetmendiya duyemîn a Deque ev e ku em dikarin hêmanan ji dawiya pêş an jî ji paşîn têxin û jê bikin.
Dabeşkirina rêza dualî
Deque dikare bi vî rengî were dabeş kirin:
Deqê bi têketin-sînordarkirî: Di têketin-sînorkirî de, jêbirin dikare ji herdu dawiyan jî were kirin, lê têxistin tenê li dawiya paşîn dikare were kirin. dorê.
Derketin-sînordarkirî Deque: Di rêza sînorkirî ya derketinê de, têxistin ji herdu dawiyan jî dikare were kirin lê jêbirin tenê li yek dawiya yanî dawiya pêşiyê tê kirin.
Herweha em dikarin steq û dorê bi karanîna deque bicîh bikin.
Operasyonên Deque yên Bingehîn
Li jêr operasiyonên bingehîn hene ku dikarin li ser deque bêne kirin.
- pêşiyê têxe: Tiştek li pêşiya deqê têxe an lê zêde bike.
- insertLast: Tiştek têxe an lê zêde bike paşiya deqê.
- JêbibeFront: Tiştê ji pêşiya rêzê jêbibe an jê rake.
- paşîn jê bibe: Jêbibe an jê rake babete ji paşdorê.
- getFront: Tişta pêşiyê di deqê de vedigerîne.
- getLast: Tişta dawî ya di dorê de vedigire. 10> isEmpty: Kontrol dike ka deq vala ye.
- isTije: Kontrol dike ka deq tije ye.
Wêneyê Deque
Dekek vala wiha tê nîşandan:
Piştre, em hêmana 1 li pêş têxin.
Niha, em hêmana 3 li paş têxin.
Piştre, em hêmana 5 li pêş lê zêde dikin û dema ku zêde dibin xalên pêşiyê lê zêde dikin. 4.
Piştre, em hêmanên 7 li paş û 9 li pêş dixe. Deque dê wekî li jêr xuya bibe.
Piştre, bila em hêmanek ji pêşiyê rakin.
Bi vî rengî, em dibînin ku gava hêman li pêş têne danîn, pozîsyona pêş kêm dibe dema ku hêmanek tê rakirin ew zêde dibe. Ji bo dawiya paşîn, pozîsyon ji bo têketinê zêde dibe û ji bo rakirinê kêm dibe .
Pêkanîna Deque
C++ Deque Implementation
Em dikarin deqek bicîh bikin di C++ de array û her weha navnîşek girêdayî bikar tîne. Ji xeynî vê, Pirtûkxaneya Şablonên Standard (STL) xwedan çînek "deque" ye ku hemî fonksiyonên ji bo vê avahiya daneyê pêk tîne.
Pêkanîna array ya deqê li jêr hatiye dayîn. Ji ber ku ew rêzek du-dawî ye me ji bo rêzikên dorhêl bikar aniyebicihanîn.
#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; }
Derketin:
Element 1 li paşê paş bixin
hêmana 3 li paşve bixin
hêmana paş deque 3
Piştî deleterear, rear =
vekirina hêmana 5-ê li dawiya pêşîn
hêmana pêşîn ya deque 5
Piştî jinavbirina, berê =
Pêkanîna Java Deque
Navbera deque di Java de, "java.util.Deque" ji navrûya "java.util.Queue" hatîye wergirtin. Deque dikare wekî dorê (Destpêkê, Yekem Derketî) an stûnek (Dawîn In, Yekem Derketî) were bikar anîn. Van pêkanînan ji navnîşa girêdayî zûtir dixebitin.
Li jêr hiyerarşiya navbeynkariya Deque ya li Java-yê tê dayîn.
Pêdivî ye ku em çend xalan di derbarê navbeynkariya Deque ya Java-yê de bi bîr bînin:
- Pêkanandin ne ewle ye ji ber ku hevdemkirina derveyî tune.
- Deque nayê piştgirîya hevdemî ji hêla gelek têlan ve.
- Deque-yên ku bi karanîna rêzan têne bicîh kirin destûr nadin ku hêmanên NULL bikar bînin.
- Rêzkirin li gorî hewcedariyê têne destûr kirin ku mezin bibin, bi kapasîteya bêsînor û piştgirîya rêzê ya ji nû ve mezinbûnê du taybetmendiyên herî girîng in.
Li jêr awayên cihêreng ên ku ji hêla navrûya Deque ve têne piştgirî kirin hene:
| Na. | Rêbaz | Danasîn |
|---|---|---|
| 1 | lêzêdekirin(hêman) | Elementekê li dûvikê zêde dike. |
| 2 | addFirst(element) | Elementekê liserî/pêş. |
| 3 | addLast(element) | Elementek li dûv/paş zêde dike. |
| 4 | pêşniyar(element) | Elementekê li dûvikê zêde dike; nirxek boolean vedigerîne da ku nîşan bide ku têxistin serketî bû. |
| 5 | offerFirst(element) | Elementekê li serî zêde dike; nirxek boolean vedigerîne da ku nîşan bide ku têxistin serketî bû. |
| 6 | offerLast(element) | Elementek li dûvikê zêde dike; nirxek boolean vedigerîne da ku nîşan bide ku têxistin serketî bû. |
| 7 | iterator() | Iteratorek ji bo deqê vedigerîne. |
| 8 | decendingIterator() | Iteratorek ku rêza berevajî ya vê deqê heye vedigerîne. |
| 9 | push(element) | Elementekê li serê deqê zêde dike. |
| 10 | pop(element) | Elementekê ji serê deqê derdixe û vedigerîne. |
| 11 | removeFirst() | Elementa li serê deqê. |
| 12 | removeLast() | Elementa li dûvê deqê jê dike. |
| 13 | poll() | Elementa yekem a deqê distîne û radike (ji hêla serokê deqê ve tê temsîl kirin); Eger deq vala be NULL vedigerîne. |
| 14 | pollFirst() | Elementa yekem a vê deqê distîne û jê dike; heke ev deq be, null vedigerînevala. |
| 15 | pollLast() | Elementa dawî ya vê deqê digire û jê dike; Heke ev deq vala be, null vedigerîne. |
| 16 | peek() | Serê(hêmana yekem a deqê) ya rêza ku tê temsîlkirin vedigerîne. bi vê deqê; Eger ev deq vala be null vedigerîne. Têbînî: Ev kar hêmanê jê nake. |
| 17 | peekFirst() | Elementa yekem a vê deqê vedigire; Eger ev deq vala be null vedigerîne. Têbînî: Ev kar hêmanê jê nake. |
| 18 | peekLast() | Elementa paşîn a vê deqê distîne, an jî heke ev deq vala ye, null vedigerîne. Têbînî: Ev kar hêmanê jê nake. |
Pêkanîna Java ya jêrîn operasyonên cihêreng ên ku li jor hatine nîqaş kirin nîşan dide.
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); } } Derketin:
Deque : [11, 7, 3, 1, 5, 9, 13]
Standard Iterator
11 7 3 1 5 9 13
Reverse Iterator
13 9 5 1 3 7 1
Peek 11
Piştî nêrînê: [11, 7, 3, 1, 5, 9, 13]
Pop 11
Piştî pop: [7, 3, 1, 5, 9,>
Di bernameya jorîn de, me navrûya Deque ya Java-yê bikar aniye û me deqek ji hêmanên yekjimar diyar kiriye. Piştre me li ser vê deqê gelek operasyon kirin û encamên van operasyonan derketintê nîşandan.
Serlêdan
Deque dikare di hin sepanên jêrîn de were bikar anîn.
#1) Algorîtmaya plansazkirinê: Algorîtmayek plansazkirinê, "Algorîtmaya plansazkirina A-dizî" ji bo pêvajoyên cihêreng ên di pergala pirpêvajoyê de plansazkirina peywirê pêk tîne. Ev pêkanîn deque bi kar tîne û pêvajoker hêmana yekem ji dequeyê ji bo îcrayê distîne.
#2) Lîsteya Çalakiyan Veke: Di sepanên nermalavê de, gelek kirinên me hene. Yek jê "betalkirin" e. Dema ku me gelek caran çalakiya betalkirinê pêk anî, ev hemî kiryar di navnîşek de têne tomar kirin. Ev lîste wekî deqek tê parastin, da ku em bi hêsanî ji her dawiya navnîşan lê zêde bikin/rakin.
#3) Piştî Demek Demek Navnîşan Rakin: Serlêdan nûvekirin têketinên di navnîşa xwe de mîna sepanên ku navnîşên stokan dinivîsin, hwd. Van sepanan piştî demekê navnîşan jê dikin û navnîşên nû jî têxin nav xwe. Ev bi bikaranîna deqê pêk tê.
Encam
Deque rêzek du-dawî ye ku dihêle ku em hêmanan ji her du dawiyan ango pêş û paşîn, yên dorê lê zêde bikin/rakin. Deque dikare bi karanîna rêzan an navnîşên girêdayî were bicîh kirin. Lêbelê, çînek me ya Pirtûkxaneya Şablonên Standard (STL) jî heye ku karên cihêreng ên Deque-ê pêk tîne.
Li Java-yê navgînek Deque-ya me heye ku ji navrûya rêzê hatî mîras kirin da ku Deque bicîh bîne. Ji xeynî operasyonên standard ên bingehîn ên Deque, ev navbeynkar cûrbecûr piştgirî dikeoperasyonên din ên ku dikarin li ser Deque bêne kirin.
Deque bi gelemperî ji bo sepanên ku hewceyê lê zêdekirin/rakirina hêmanan ji her du dawiyan hewce dike tê bikar anîn. Di heman demê de bi piranî di plansazkirina pêvajoyên pergalên pir-prosesor de jî tê bikar anîn.
Rêzeya Perwerdehiya Tevahiya C++ Binihêrin