队列queue
队列是一种特殊的线性表，它是在一端（队头）进行删除操作，另一端（队尾）进行插入操作，遵守先进先出的规则。。
Defination: queue is a linear data structure which operates in a first in first out or last in last out
在日常生活中，人们去银行办理业务需要排队，这就类似我们提到的队列。每一个新来办理业务的需要按照机器自动生成的编号等待办理，只有前面的人办理完毕，才能轮到排在后面的人办理业务。新来的人进入排队状态就相当于入队，前面办理完业务离开的就相当于出队。
既然队列也是线性表，当然也有两种数据存储方式：
顺序队列通常采用一维数组存储队列中的元素，另外增加两个指针分别指示数组中存放的队首元素和队尾元素。其中指向队首元素的指针称为队头指针front，指向队尾元素的指针称为队尾指针rear。
队列为空时，队头指针front和队尾指针rear都指向下标为0的存储单元，当元素a,b,c,d,e,f,g依次进入队列后，元素a~g分别存放在数组下标为0~6的存储单元中，队头指针front指向元素a，队尾指针指rear向元素g的下一位置。如图所示。
但是按照前面介绍的顺序存储方式，容易出现“假溢出”。所谓“假溢出”，就是经过多次插入和删除操作后，实际队列还有存储空间，但是又无法向队列中插入元素。
例如在图中队列删除a和b，然后依次插入h、i和j，当插入j后，就会出现队尾指针rear越出数组的下界造成“假溢出”，如图
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 | /**************************************************************** * Description: Queue * Author: Alex Li * Date: 2024-04-15 20:33:20 * LastEditTime: 2024-04-15 20:38:07 ****************************************************************/ #include <iostream> using namespace std; int arr[5]; int front=-1; int rear=-1; //IsFull(),check if Queue is IsFull bool IsFull(){ if(rear==4) return true; else return false; } //IsEmpty(), check if queue is empty bool IsEmpty(){ if(front==-1 && rear==-1)return true; else return false; } // EnterQueue(),Elements are added from rear void EnterQueue(int value){ if(IsFull()){ cout<<"Queue is FULL"; return; } else if(IsEmpty()){ rear=0; front=0; arr[rear]=value; } else{ rear++; arr[rear]=value; } } // ExitQueue(),Elements removed from front int ExitQueue(){ int x=0; if(IsEmpty()){ cout<<"Queue is empty"<<endl; return 0; }else if(front==rear){ x=arr[front]; arr[front]=0; front=-1; rear=-1; return x; } else{ x=arr[front]; for (int i = front; i <=rear; i++) { arr[i]=arr[i+1]; } arr[rear]=0; rear--; return x; } } //count(),get count of total items in queue int count(){ return (rear-front+1); } void display(){ cout<<"all value in the queue are"<<endl; for (int i = front; i <=rear; i++) { cout<<arr[i]<<" "; } cout<<endl; } int main(){ int option,value; do{ cout<<"what operation do you want to perform? select option number."<<endl; cout<<"0. exit"<<endl; cout<<"1. EnterQueue"<<endl; cout<<"2. ExitQueue"<<endl; cout<<"3. IsEmpty"<<endl; cout<<"4. IsFull"<<endl; cout<<"5. count"<<endl; cout<<"6. display"<<endl; cin>>option; switch(option){ case 0: break; case 1: cout<<"EnterQueue operation enter an item to EnterQueue is the queue"<<endl; cin>>value; EnterQueue(value); break; case 2: cout<<"ExitQueue value"<<endl; ExitQueue(); break; case 3: if(IsEmpty()) cout<<"queue is empty"<<endl; else cout<<"queue is not empty"<<endl; break; case 4: if(IsFull()) cout<<"queue is Full"<<endl; else cout<<"queue is not full"<<endl; break; case 5: cout<<"count of items in queue "; cout<<count()<<endl; break; case 6: cout<<"display function called"<<endl; display(); break; default: cout<<"enter proper option number"<<endl; break; } }while(option!=0); return 0; } |
【顺序循环队列】
当队尾指针rear或队头指针front到达存储空间的最大值时（假定队列的存储空间为QueueSize），让队尾指针或者队头指针转化为0，这样就可以将元素插入到队列的空闲存储单元中，有效的利用存储空间，消除“假溢出”。
例如在上面的例子中，插入元素j后，rear将变为0，这样就将j插入下标为0的存储单元中。这样顺序队列的存储空间就构成了一个逻辑上收尾相连的循环队列。
要把用数组表示的顺序队列构成循环队列，只需要一个简单的取余操作即可实现。例如当队尾指针rear=9（假设QueueSize=10）时，如果要将新元素入队，则先令rear=（rear+1）%10,这样rear就等于0，这样利用取余操作就实现了队列逻辑上的首尾相连，然后将元素存入队列的第0号单元。
【队空和队满】
在循环队列中，队空和队满时队头front和队尾指针rear同时都会指向同一存储单元，即front==rear，如图所示。
链式存储结构：可以不需要事先知道队列的大小，支持动态和释放空间，但是插入和删除操作比较耗时，也称链队列。
建议：当事先基本上确定队列的大小，且插入和删除操作比较频繁时，优先考虑循环队列。。
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 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 | /****************************************************************************** Queue *******************************************************************************/ #include <iostream> using namespace std; int arr[5]; int front=-1; int rear=-1; //IsFull(),check if Queue is IsFull bool IsFull(){ if((rear-front)==4) return true; else return false; } //IsEmpty(), check if queue is empty bool IsEmpty(){ if(front==-1 && rear==-1) return true; else return false; } // EnterQueue(),Elements are added from rear void EnterQueue(int value){ if(IsFull()){ cout<<"Queue is FULL"<<endl; return; } else if(IsEmpty()){ rear=0; front=0; arr[rear]=value; } else{ rear++; arr[rear%5]=value; } } // ExitQueue(),Elements removed from front int ExitQueue(){ int x=0; if(IsEmpty()){ cout<<"Queue is empty"<<endl; return 0; }else if(front==rear){ x=arr[front]; arr[front]=0; front=-1; rear=-1; return x; } else{ x=arr[front%5]; front++; return x; } } //count(),get count of total items in queue int count(){ return (rear-front+1); } void display(){ if(IsEmpty()){ cout<<"the quenue is empty;"<<endl; } else{ cout<<"all value in the queue are"<<endl; if(rear%5>=front%5) for (int i = front%5; i <=rear%5; i++) { cout<<arr[i]<<" "; } else{ for (int i =front%5; i <=4; i++) { cout<<arr[i]<<" "; } for (int i = 0; i <=rear%5; i++) { cout<<arr[i]<<" "; } } cout<<endl; } } int main(){ int option,value; for (int i = 0; i < 5; i++) { arr[i]=0; } do{ cout<<"what operation do you want to perform? select option number."<<endl; cout<<"0. exit"<<endl; cout<<"1. EnterQueue"<<endl; cout<<"2. ExitQueue"<<endl; cout<<"3. IsEmpty"<<endl; cout<<"4. IsFull"<<endl; cout<<"5. count"<<endl; cout<<"6. display"<<endl; cin>>option; switch(option){ case 0: break; case 1: cout<<"EnterQueue operation enter an item to EnterQueue is the queue"<<endl; cin>>value; EnterQueue(value); break; case 2: cout<<"ExitQueue value"<<endl; ExitQueue(); break; case 3: if(IsEmpty()) cout<<"queue is empty"<<endl; else cout<<"queue is not empty"<<endl; break; case 4: if(IsFull()) cout<<"queue is Full"<<endl; else cout<<"queue is not full"<<endl; break; case 5: cout<<"count of items in queue "; cout<<count()<<endl; break; case 6: cout<<"display function called"<<endl; display(); break; default: cout<<"enter proper option number"<<endl; break; } }while(option!=0); return 0; } |