Sorting A Queue C++ (Data structures)
The queue is basically a FIFO (First In First Out).
| 19 | 39 | 29 | 40 | 50 |
| Front | Rear | |||
Sorting:
Sorting works on many algorithms. The sorting algorithm is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in the order.
How sorting will work:
Here is an example which is explaining the concept of sorting a Queue.
Queue:
| 19 | 39 | 29 | 40 | 50 |
| Front | Rear | |||
Start from the first two numbers, compare both of them to check which one is greater.
Here 39 is already greater than 19 so it is already sorted.
| 19 | 39 | 29 | 40 | 5 |
| Smaller | Greater
|
|||
No Swapping needed.
Now we will compare 39 and 29
| 19 | 39 | 29 | 40 | 5 |
| Greater | Smaller
|
|||
Now compare 39 and 5. 39 and 5 will be swapped here.
| 19 | 29 | 39 | 5 | 40 |
| Greater | Smaller
|
|||
The queue will be:
29 and 5 will be compared, these will be swapped because 5 is less than 29.
| 19 | 29 | 5 | 39 | 40 |
| Greater | Smaller | |||
Finally, our sorted Queue will be :
| 5 | 19 | 29 | 39 | 40 |
C++ Program of Sorting A Queue (Data structures)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
#include<iostream> using namespace std; class queue { int data[200],front,rear,size; public: queue(int x) { front=-1; rear=-1; size=x; } void enqueue(int x) { if(is_empty()) { front++; rear++; data[rear]=x; } else if(is_full()) { cout<<"Queue is full "<<endl; } else { rear=(rear+1)%size; data[rear]=x; } } int dequeue() { if(is_empty()) { return 0; } else if (front==rear) { int a=data[front]; front=rear=-1; return a; } else {int a = data[front] ; front = (front+1)%size; return a; } } int is_empty() { if(front==-1) return 1; else return 0; } int is_full() { if((rear+1)%size==front) return 1; else return 0; } void print() { int a =front; do { cout<<data[a]<<" "; a = (a+1)%size ; } while(a!=(rear+1)%size); cout<<endl; } void sort() { int a , b , i=0 , j , check; int l = size ; while(l--) { if(is_empty()) break; a = dequeue() ; if(is_empty()) break; b = dequeue() ; j = size-i-1 ; while(j--) { if(a<b) { if(front!=0) { enqueue(a); a = dequeue(); } else break ; } else { if(front!=0) { enqueue(b); b = dequeue(); } else break ; } } if(a>b) { enqueue(b); enqueue(a); } else { enqueue(a); enqueue(b); } front = 0 ; rear = size-1; i++; } } }; int main() { int a,num; cout<<"Please Enter the number of elements : " ; cin>>num; queue q(num); cout<<"Please enter element in queue "<<endl; while(num--) { cin>>a; q.enqueue(a); } cout<<"Original Queue "<<endl; q.print(); q.sort(); cout<<"Sorted Queue"<<endl; q.print(); return 0; } |
Output
