Queue

Queue

اسلاید 1: Queue

اسلاید 2: Queue OverviewQueue ADTBasic operations of queueEnqueuing, dequeuing etc.Implementation of queueArrayLinked list

اسلاید 3: Queue ADTصف مانند پشته، يك ليست است. ولي در صف، درج از يك طرف و حذف از طرف ديگر انجام مي‌شود.دسترسي به عناصر صف به صورت First In, First Out (FIFO) است.مثل مشترياني كه در صف يك فروشگاه مي‌ايستند، اولين مشتري كه وارد مي‌شود، اولين مشتري است كه سرويس مي‌گيرد.

اسلاید 4: The Queue ADTعمليات اصلي :Enqueue (AddQ) : درج يك عنصر به انتهاي ليستDequeue (RemoveQ) : حذف يك عنصر از جلوي ليستFirst-in First-out (FIFO) list

اسلاید 5: Enqueue and DequeuePrimary queue operations: Enqueue and DequeueA queue has a front and a rear. EnqueueInsert an element at the rear of the queueDequeueRemove an element from the front of the queueInsert (Enqueue)Remove (Dequeue)rearfront

اسلاید 6: پياده‌سازي صف با آرايهالگوريتم‌هاي متفاوتي براي پياده‌سازي enqueue و dequeue وجود دارد.وقتي عنصري به صف اضافه مي‌شود، شماره front تغيير نمي‌كند و شماره rear افزايش مي‌يابد.frontrearEnqueue(3)3frontrearEnqueue(6)36frontrearEnqueue(9)369

اسلاید 7: وقتي عنصري از صف حذف مي‌شود، عنصر موجود در سر صف حذف مي‌شود. و همه عناصر ليست به اندازه يك مكان جابجا مي‌شوند. (ناكارآمد)Dequeue()frontrear69Dequeue()Dequeue()frontrear9rear = -1 frontپياده‌سازي صف با آرايه

اسلاید 8: روش بهتروقتي عنصري درج مي‌شود، rear افزايش مي‌يابد.وقتي عنصري حذف مي‌شود، front افزايش مي‌يابد و به سمت انتهاي صف حركت مي‌كند.(بنابراين عناصر ليست جابجا نمي‌شوند)XXXXOOOOO (rear) OXXXXOOOO (after 1 dequeue, and 1 enqueue)OOXXXXXOO (after another dequeue, and 2 enqueues)OOOOXXXXX (after 2 more dequeues, and 2 enqueues)(front)مشكل اينجاست كه شماره rear را نمي‌توان افزايش داد، يعني نمي‌توان در صف عنصري درج كرد با اينكه صف پر نيست.پياده‌سازي صف با آرايه

اسلاید 9: وقتي rear به انتهاي آرايه اشاره مي‌كند، براي درج عنصر جديد به ابتداي آرايه مي‌رويم.OOOOO7963  4OOOO7963 (after Enqueue(4))After Enqueue(4), the rear index moves from 8 to 0.پياده‌سازي صف با آرايه حلقوي

اسلاید 10:

اسلاید 11: Empty or Full?Empty queueback= front - 1Full queue?the same!SolutionsUse a boolean variable to say explicitly whether the queue is empty or notMake the array of size n+1 and only allow n elements to be storedUse a counter of the number of elements in the queue

اسلاید 12: Queue Implementation of Linked Listclass Queue {public:Queue(int size = 10);// constructor~Queue() { delete [] values; }// destructorbool IsEmpty(void);bool IsFull(void);bool Enqueue(double x);bool Dequeue(double & x);void DisplayQueue(void);private:int front;// front indexint rear;// rear indexint counter;// number of elementsint maxSize;// size of array queuedouble* values;// element array};

اسلاید 13: Queue ClassAttributes of Queuefront/rear: front/rear indexcounter: number of elements in the queuemaxSize: capacity of the queuevalues: point to an array which stores elements of the queueOperations of QueueIsEmpty: return true if queue is empty, return false otherwiseIsFull: return true if queue is full, return false otherwiseEnqueue: add an element to the rear of queueDequeue: delete the element at the front of queueDisplayQueue: print all the data

اسلاید 14: Create QueueQueue(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 arrayrear 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;}

اسلاید 15: IsEmpty & IsFullاز آنجائيكه تعداد عناصر صف در متغير counter نگهداري مي‌شود، تشخيص خالي بودن يا پر بودن صف بسيار ساده است.bool Queue::IsEmpty() {if (counter)return false;elsereturn true;}bool Queue::IsFull() {if (counter < maxSize)return false;elsereturn true;}

اسلاید 16: Enqueuebool 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 itemvalues[rear]= x;// update countercounter++;return true;}}

اسلاید 17: Dequeuebool Queue::Dequeue(double & x) {if (IsEmpty()) {cout << Error: the queue is empty. << endl;return false;}else {// retrieve the front itemx= values[front];// move front front= (front + 1) % maxSize;// update countercounter--;return true;}}

اسلاید 18: Printing the elementsvoid Queue::DisplayQueue() {cout << front -->;for (int i = 0; i < counter; i++) {if (i == 0) cout << t;elsecout << tt; cout << values[(front + i) % maxSize];if (i != counter - 1)cout << endl;elsecout << t<-- rear << endl;}}

اسلاید 19: Using Queueint 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;}

اسلاید 20: پياده‌سازي صف با استفاده از ليست پيونديclass Queue {public:Queue() {// constructorfront = rear = NULL;counter= 0;}~Queue() {// destructordouble 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 nodeNode* rear;// pointer to last nodeint counter;// number of elements};

اسلاید 21: Enqueuevoid Queue::Enqueue(double x) {Node* newNode=new Node;newNode->data=x;newNode->next=NULL;if (IsEmpty()) {front=newNode;rear=newNode;}else {rear->next=newNode;rear=newNode;}counter++;}8rearrearnewNode558

اسلاید 22: Dequeuebool 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--;}}8front5583front

اسلاید 23: Printing all the elementsvoid Queue::DisplayQueue() {cout << front -->;Node* currNode=front;for (int i = 0; i < counter; i++) {if (i == 0) cout << t;elsecout << tt; cout << currNode->data;if (i != counter - 1)cout << endl;elsecout << t<-- rear << endl;currNode=currNode->next;}}

اسلاید 24: ResultQueue implemented using linked list will be never fullbased on arraybased on linked list