队列又被称为FIFO表,即先进先出,实现队列与栈类似,存储结构有两种:顺序表和链表。
这里仅仅给出队列的顺序队列实现。
上代码:
1 #include<iostream> 2 using namespace std; 3 4 class Queue 5 { 6 private: 7 int front; 8 int rear; 9 int * arrq; 10 int msize; 11 public: 12 Queue(int size); 13 bool push(int item); 14 bool pop(); 15 void display(); 16 void clear(); 17 ~Queue(); 18 }; 19 20 Queue::Queue(int size) 21 { 22 msize = size+1; 23 front = rear = 0; 24 arrq = new int[msize]; 25 } 26 bool Queue::push(int item) 27 { 28 if((rear + 1) % msize==front) 29 { 30 cout<< "队列溢出!" << endl; 31 return 0; 32 } 33 arrq[rear] = item; 34 rear = (rear + 1) % msize; 35 return 1; 36 } 37 bool Queue::pop() 38 { 39 if(front==rear) 40 { 41 cout<< "队列为空,不能弹出" <<endl; 42 return 0; 43 } 44 front = (front + 1)%msize; 45 return 1; 46 } 47 48 void Queue::display() 49 { 50 int temp = front; 51 while(temp < rear) 52 { 53 cout<< arrq[temp] << " "; 54 temp++; 55 } 56 cout << endl; 57 } 58 59 void Queue::clear() 60 { 61 front = rear; 62 } 63 64 Queue::~Queue() 65 { 66 delete [] arrq; 67 } 68 int main() 69 { 70 Queue q1(10); 71 int ele; 72 cout<< "input the ele :" << endl; 73 for(int i=0;i<10;i++) 74 { 75 cin>> ele; 76 q1.push(ele); 77 } 78 cout<< "输出完整队列:" << endl; 79 q1.display(); 80 q1.pop(); 81 q1.pop(); 82 cout<< "两个元素出对列后在输出:" <<endl; 83 q1.display(); 84 return 0; 85 } 86 87 88
程序运行结果:
针对以上程序代码,几个问题:
1.这里用的是循环队列实现,能充分利用顺序表中的空闲内存,解决“假溢出”的问题。
2.实际利用的空间是size+1,浪费一个存储空间,不存储任何信息,是队列的尾部,由rear进行记录,作用是可以区分队列满和空的状态。