Queue

صفحه 1:
Queue 

صفحه 2:
جع اعسه Queue Overview > ‏صص94‎ Oh 0 ا ‎el‏ > 1| ‏أن ومفوامجمجامو‎ Cd ‏لا‎ aa ‏ات يا‎ 

صفحه 3:
وس اس Queue ADT ee MP ‏ا ا ل ا ا ا‎ dd ‏درج ازيك طرف و حذف از طرف ديكر انجام‎ ‏مي‌شود.‎ 0۱ عناصر صف به صورت ۱<) ,0 عن۲) ۳0۵ 1 Ie SIP CSNEY per Py FL Pug] BC gree marl) Meir Tee eS Pi Cmt pire murtry| ‏سرويس مي ديرد.‎ 

صفحه 4:
The Queue ADT pple rer Woe co foley parevls g59 : Boqueve (BddQ) ‏ست‎ 000 2-2 dequeue ۹ enqueue + Pistia Pirstout ( are fist 

صفحه 5:
Enqueue and Dequeue ۱ a aC Ae as et a RO td > (ORCA as aN ‏و ام‎ ۰ ‏يا‎ (oe od © dosent oo elewedt of the rear oP the queue bel Oe cd ‏ضحي جا خام امممخا جملا جموصخا امجمجاج جه را‎ = a Qeqee) Prod rer (mre) 

صفحه 6:
پياده‌سازي صف با رده := الكوريتمهاي متفاوتي براي پياده‌سازي سس ‎i tar)‏ 7 COCR TY Tee ECO) neve tL pe tte CTD BU ‏ا ا ا‎ se oar 1 i a el 1 1 

صفحه 7:
يبيادهوسازي صف با ارایه 0 وقتي عنصري از صف حذف مي‌شود, عنصر موجود در سر صف حذف 0 و همه عناصر ليست به اندازه يك مكان جابجا ميشوند. (ناكارامد) / 1 2 7 3 a ce) coe) ‏لعن‎ 

صفحه 8:
اس ‎CS ENDL‏ با آرایه ‎9 ae ‏وقتي عنصري درج مي‌شود. ۲« افزایش مي‌يابد.‎ 8 ‏ل ا زايدنر‎ 2 nt ge tia 2 ee, ERY See en nese ee (eee ‏ری ار ات ات‎ ‎ ‏00 6 0200 ا 6 0009 سم ی ور 09۵0 را ۵ 0 00 ‏۱ ‏يعني نميتوان در صف عنصري درج كرد با اينكه صف ير 

صفحه 9:
pave | Che O ۳-۳۹۳ ۳ ‏صف با‎ is jluooly > وقتي عم به انتهاي آرايه اشاره ۳۹9 "19 > 0000012999 < FOOOOPS99 (Pier 2 ۱ Prow O ty O. 

صفحه 10:
Initial State After enqueve(1) After dequeue, Which Returns 1 1 211 1111 back front After enqueue(3) After dequeue, Which Returns 3 a and Makes the Queue Empty After dequeue, Which Returns 2 3 113111111 ۶ back_front back After dequeue, Which Retuens 4 1/3 214 front back 

صفحه 11:
Cero) Empty or Full? a aN ‏ور نا‎ a as - ‏لا ا‎ ia ‏سس ری‎ > ‏عمشاو6)‎ ‎§ Ose uo bovless vortoble to say explicitly whether the queue is ‏وم‎ ‏اص عو‎ LN oe A aes a RRS EAR Oe ea | RO ‏امه اه نت و‎ eine cane oan ad 

صفحه 12:
0550-5 Queue Implementation of Linked List class Queue { public: Queue(int size = 10); // constructor ~Queue() { delete [] values; } // destructor bool IsEmpty(void) ; bool IsFull(void); bool Enqueue(double x); bool Dequeue(double & x); void DisplayQueue(void) ; ۱۳۱ 77 front index // rear index //_number of elements ۴1۱(: 7 7025-772-7170 double* values; ۱۸۸۵۱ aN 

صفحه 13:
0555-5 Queue Class Bar a ‏تا‎ ‏صلم عمجم حصا باقع" خموع 1 ه«‎ 1" ‏عنجبب جما ها صلكجمجمات خاه «وحامكد :اع نامك‎ ‏ل لا‎ queue ‏يي لي ل ل لل لا‎ > ‏عناع00 ام جممتموو0‎ ‏ال ل يا‎ eae ee er ISFUUL: reture true iP queue is Pull, retura Pulse vikerwise SNe LULU RN a eS aa eC Dequeue: delete the elect ot the Prout oF queue LOST OLE ‏لل‎ es 

صفحه 14:
0 سلط اس Create Queue = Queue(int size = 10) 8 Olocoe o queue aru of Size. Op deat, Size = 10. | eee et eM eee deen nee ee ۲ ۲۵۵۲ ‏ما ی‎ - 1. Re a ee Queue: :Queue(int size /* = 10 */) { values = new double[size]; maxSize = 51267 Sealine = 0۳ 1- = تن ;0 = عع لتنامع 

صفحه 15:
سب اعسه IsEmpty & IsFull CA ates? ‏ا‎ نگهداري مي‌شود. تشخیص خالي بودن یا پر بودن صف بسیار ساده است. bool Queue::IsEmpty() { if (counter) return false; Cua) return true; 1 bool Queue::IsFull() { if (counter < maxSize) return false; 323 ‏كت‎ 

صفحه 16:
Enqueue bool Queue: :Enqueue(double x) { if (IsFull()) { cout << "Error: the queue is full." << endl; ۳6۲۷۲ 567 1 elsent // calculate the new rear position (circular) ۳5۳ = (rear + 1) % maxSize; ۸/۵۱3 1) values[rear] ‏عا‎ ‎// update counter counter++; ia-aa ۵۵ 

صفحه 17:
و اعسه Dequeue bool Queue: :Dequeue(double & x) { if (IsEmpty()) { cout << "Error: the queue is empty." << endl; ‏یروا اکتوا‎ : 0 // retrieve the front item me = values[front]; 022 ‏ک تك‎ front = (front + 1) % maxSize; // update counter counter--; return true; 

صفحه 18:
0555-5 Printing the elements [Front --> 1 1 2 3 ‏ات اک‎ void Queue: :DisplayQueue() { cout << "front -->"; for (int i = 0; i < counter; i++) { 1 (ik -2-60( ‏“عه 6ألرمع‎ else (fle "١غ"‎ cout << values[(front + Ay % maxSize]; if (i != counter - 1) cout << endl; else cout << "\t<-- rear" << endl; 

صفحه 19:
cece cc Cr Ue eee) Using FETs es ete ere Queue areas a 4 2 5 4 < rear eect eC) ‏غمممعا‎ -< 1 7 3 4 27 int main(void) { jee) 3 2 ‏ا‎ T= eo) 3 ۱۳ ‏ل‎ 4 for (int x = 0; x < 5; x#+) 2 ‏معا‎ Preemie cout << "Now attempting to enqueue again..." << endl; queue. Enqueue(5) ; queue .DisplayQueue(); Colt LAT Preiser ten Tarver y cout << "Retrieved element = " << value << endl; Cte een tCn CTO queue. Enqueue(7) ; : ()عناعن0لة مكذه. معنن :0 معباععم 

صفحه 20:
يياده سازي صف با استفاده از ليسنتموسه 1 ) بيوندي ‎Queue() { 020 ۲۳‏ ‎cae cea a‏ ۳ 1 ‎~Queue() { // ۲۳‏ زعن1قا عاطنامك ‎AOL ICTS‏ ا ل 7 0 if (counter) return false; et ۲6۷۳۴ ۵۵۶ 0 Cae ‏عنعنوع0 موه‎ ee ae void DisplayQueue( void) ; public: خنع 1131م Try Gaia Le AA Stee me Me eae elle 19 ‏اي ا‎ eT ‏ل‎ ‎10۴ ‏ماه ل 0 الل‎ 

صفحه 21:
Enqueue void Queue: :Enqueue(double x) { Node* newNode = new Node; newNode->data mae newNode->next = NULL; if (IsEmpty()) { ‏فرع‎ = newNode; ۱۳5۳ = newNode; 1 cts ‏عا‎ 0001 rear->next = newNode; ۵2-8 = newNode; fear 1 اه وطح رظن ‎Sorte‏ تس 1 

صفحه 22:
Dequeue bool Queue: :Dequeue(double & x) { if (IsEmpty()) { cout << “Error: the queue is empty." << endl ‏ر كاتا‎ Leto 6156 1 Bg Node* nextNode delete front; front counter--; 1 front : ee ctrl ‏لها ها‎ :033<-أممعع] زغلاعم< - ارمع nextNode; 

صفحه 23:
69 سه اعضو Printing all the elements 520-07 32539 void Queue: اس 0 الل ل ‎cout << "front -->";‏ یت | 9و = ‎Node* currNode‏ <- عمسم { ‎for (int i = 0; i < counter; i++)‏ ‎if (i == 0) cout << "\t";‏ ‎Pies) cout << "\t\t";‏ ‎cout << currNode->data; iad‏ (1 - معغملمء د! 1) +1 ‎cout << endl;‏ واه ‎cout << "\t<-- rear" << endl;‏ ‎currNode - currNode->next;‏ 

صفحه 24:
0 و اس Result ‎RCE RO tT‏ 2 نا ‎ ‎ ‎CeCe ‏متدوة منعنومة مع ومتغمموععة بما‎ eee CC ‎ ‎ ‎ ‎ ‎ ‎ ‎Pern ‏ا‎ ‎ 

Queue Queue / Slide 2 Queue Overview   Queue ADT Basic operations of queue   Enqueuing, dequeuing etc. Implementation of queue   Array Linked list Queue / Slide 3 ‏Queue ADT ‏ صف مانند پشته ،يك ليست است .ولي در صف، درج از يك طرف و حذف از طرف ديگر انجام مي‌شود. ‏ دسترسي به عناصر صف به صورت First In, First ) Out (FIFOاست. ‏ مثل مشترياني كه در صف يك فروشگاه مي‌ايستند، اولين مشتري كه وارد مي‌شود ،اولين مشتري است كه سرويس مي‌گيرد. Queue / Slide 4 The Queue ADT : عمليات اصلي درج يك عنصر به انتهاي ليست: Enqueue (AddQ) حذف يك عنصر از جلوي ليست: Dequeue (RemoveQ)  First-in First-out (FIFO) list    Queue / Slide 5 Enqueue and Dequeue    Primary queue operations: Enqueue and Dequeue A queue has a front and a rear. Enqueue   Insert an element at the rear of the queue Dequeue  Remove an element from the front of the queue Remove (Dequeue) front rear Insert (Enqueue) Queue / Slide 6 پياده‌سازي صف با آرايه الگوريتم‌هاي متفاوتي براي پياده‌سازي enqueue و dequeueوجود دارد. وقتي عنصري به صف اضافه مي‌شود ،شماره front تغيير نمي‌كند و شماره rearافزايش مي‌يابد. ‏rear 9 ‏rear ‏rear 6 3 ‏front )Enqueue(9 6 3 3 ‏front ‏front )Enqueue(6 )Enqueue(3 Queue / Slide 7 پياده‌سازي صف با آرايه وقتي عنصري از صف حذف مي‌شود، عنصر موجود در سر صف حذف مي‌شود. و همه عناصر ليست به اندازه يك مكان جابجا مي‌شوند( .ناكارآمد) ‏rear = -1 ‏front )(Dequeue ‏rear ‏rear 9 9 ‏front )(Dequeue 6 ‏front )(Dequeue Queue / Slide 8 پياده‌سازي صف با آرايه روش بهتر وقتي عنصري درج مي‌شود rear ،افزايش مي‌يابد. وقتي عنصري حذف مي‌شود front ،افزايش مي‌يابد و به سمت انتهاي صف حركت مي‌كند. (بنابراين عناصر ليست جابجا نمي‌شوند) )(rear )(after 1 dequeue, and 1 enqueue )(after another dequeue, and 2 enqueues )(after 2 more dequeues, and 2 enqueues ‏XXXXOOOOO ‏OXXXXOOOO ‏OOXXXXXOO ‏OOOOXXXXX )(front مشكل اينجاست كه شماره rearرا نمي‌توان افزايش داد، يعني نمي‌توان در صف عنصري درج كرد با اينكه صف پر Queue / Slide 9 پياده‌سازي صف با آرايه حلقوي وقتي rearبه انتهاي آرايه اشاره مي‌كند ،براي درج عنصر جديد به ابتداي آرايه مي‌رويم. ‏OOOOO7963  4OOOO7963 (after ))Enqueue(4 ‏ ‏After Enqueue(4), the rear index moves from 8 to 0. ‏ Queue / Slide 10 Queue / Slide 11 Empty or Full?  Empty queue   Full queue?   back= front - 1 the same! Solutions    Use a boolean variable to say explicitly whether the queue is empty or not Make the array of size n+1 and only allow n elements to be stored Use a counter of the number of elements in the queue Queue / Slide 12 Queue Implementation of Linked List class Queue { public: Queue(int size = 10); // constructor ~Queue() { delete [] values; } // destructor bool IsEmpty(void); bool IsFull(void); bool Enqueue(double x); bool Dequeue(double & x); void DisplayQueue(void); private: int front; // front index int rear; // rear index int counter; // number of elements int maxSize; // size of array queue double* values; // element array }; Queue / Slide 13 Queue Class  Attributes of Queue      front/rear: front/rear index counter: number of elements in the queue maxSize: capacity of the queue values: point to an array which stores elements of the queue Operations of Queue      IsEmpty: return true if queue is empty, return false otherwise IsFull: return true if queue is full, return false otherwise Enqueue: add an element to the rear of queue Dequeue: delete the element at the front of queue DisplayQueue: print all the data Queue / Slide 14 Create Queue  Queue(int size = 10)    Allocate a queue array of size. By default, size = 10. front is set to 0, pointing to the first element of the array rear is set to -1. The queue is empty initially. Queue::Queue(int size /* = 10 */) { values = new double[size]; maxSize = size; front = 0; rear = -1; counter = 0; } Queue / Slide 15 IsEmpty & IsFull counter از آنجائيكه تعداد عناصر صف در متغير تشخيص خالي بودن يا پر بودن،نگهداري مي‌شود .صف بسيار ساده است bool Queue::IsEmpty() { if (counter) return false; else return true; } bool Queue::IsFull() { if (counter < maxSize) return false; else return true; }  Queue / Slide 16 Enqueue bool Queue::Enqueue(double x) { if (IsFull()) { cout << "Error: the queue is full." << endl; return false; } else { // calculate the new rear position (circular) rear = (rear + 1) % maxSize; // insert new item values[rear] = x; // update counter counter++; return true; } } Queue / Slide 17 Dequeue bool Queue::Dequeue(double & x) { if (IsEmpty()) { cout << "Error: the queue is empty." << endl; return false; } else { // retrieve the front item x = values[front]; // move front front = (front + 1) % maxSize; // update counter counter--; return true; } } Queue / Slide 18 Printing the elements void Queue::DisplayQueue() { cout << "front -->"; for (int i = 0; i < counter; i++) { if (i == 0) cout << "\t"; else cout << "\t\t"; cout << values[(front + i) % maxSize]; if (i != counter - 1) cout << endl; else cout << "\t<-- rear" << endl; } } Queue / Slide 19 Using Queue int main(void) { Queue queue(5); cout << "Enqueue 5 items." << endl; for (int x = 0; x < 5; x++) queue.Enqueue(x); cout << "Now attempting to enqueue again..." << endl; queue.Enqueue(5); queue.DisplayQueue(); double value; queue.Dequeue(value); cout << "Retrieved element = " << value << endl; queue.DisplayQueue(); queue.Enqueue(7); queue.DisplayQueue(); return 0; } پياده‌سازي صف با استفاده از ليست پيوندي Queue / Slide 20 class Queue { public: Queue() { // constructor front = rear = NULL; counter = 0; } ~Queue() { // destructor double value; while (!IsEmpty()) Dequeue(value); } bool IsEmpty() { if (counter) return false; else return true; } void Enqueue(double x); bool Dequeue(double & x); void DisplayQueue(void); private: Node* front; // pointer to front node Node* rear; // pointer to last node int counter; // number of elements }; Queue / Slide 21 Enqueue void Queue::Enqueue(double x) { Node* newNode = new Node; newNode->data = x; newNode->next = NULL; if (IsEmpty()) { front = newNode; rear = newNode; } 8 else { rear->next = newNode; rear = newNode; } 8 5 counter++; } rear 5 rear newNode Queue / Slide 22 Dequeue bool Queue::Dequeue(double & x) { if (IsEmpty()) { cout << "Error: the queue is empty." << endl; return false; } else { x = front->data; Node* nextNode = front->next; delete front; front = nextNode; counter--; } front } 3 8 5 front 8 5 Queue / Slide 23 Printing all the elements void Queue::DisplayQueue() { cout << "front -->"; Node* currNode = front; for (int i = 0; i < counter; i++) { if (i == 0) cout << "\t"; else cout << "\t\t"; cout << currNode->data; if (i != counter - 1) cout << endl; else cout << "\t<-- rear" << endl; currNode = currNode->next; } } Queue / Slide 24 Result  Queue implemented using linked list will be never full based on array based on linked list