队列简介： 队列（Queue）是一种数据结构，可以在队列的一端插入元素而在队列的另一端删除元素。 （ 1 ）允许删除的一端称为 队头（ Front ） 。 　　（ 2 ）允许插入的一端称为 队尾（ Rear ） 。 　　（ 3 ）当队列中没有元素时称为 空队列 。 　　（ 4 ）队列亦称作先进先出（ First In First Out ）的线性表，简称为 FIFO 表 。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许 " 加塞 " ），每次离开的成员总是队列头上的（不允许中途离队），即当前 " 最老的 " 成员离队。 多任务系统是一个典型的队列示例，在其中完成作业的调度。假设有五个程序等待执行， 它们将被放入一个队列，如果有第六个程序要执行，它将被放在队列的末尾。队列中首位的程序首先执行。   队列实现： /* （1）initQueue（Q） 　 置空队。构造一个空队列Q。 （2）isEmpty（Q） 　 判断队列是否空。若队列Q为空，则返回真值，否则返回假值。 （3）isFull(Q)   判断队列是否以满, 以满返回true, 没满则返回flase （4） addQueue（Q，x） 　 若队列Q非满，则将元素x插入Q的队尾。此操作简称 入队 。 （5） DelQueue（Q） 　 若队列Q非空，则删去Q的队头元素，并返回该元素。此操作简称 出队 。 （6） queueFront（Q） 　 若队列Q非空，则返回队头元素，但不改变队列Q的状态。 （7） queueDisplay（Q） 　 显示队列中的元素。*/ #include "iostream.h" #define maxSize 10  // 存储数据大小, 可以随便设定值 struct Queue{ int data[maxSize]; int front;  // 队首  int rear;  // 队尾}; void initQueue( Queue &Q );bool isEmpty( Queue &Q );bool isFull( Queue &Q );bool addQueue( Queue &Q, int x );bool delQueue( Queue &Q );int queueFront( Queue &Q );bool queueDisplay( Queue &Q ); int main( void ){ int i; int num; Queue Q;  initQueue( Q );  // 初始化队列  cout << "输入入队10个数" << endl; /* 入队 */ for ( i = 0; i < 10; i++ ) {  cin >> num;  if ( addQueue( Q, num ) == false )  {   cout << "队列以满!" << endl;  } }  cout << "队头: " << queueFront( Q ) << endl; // 显示队头 cout << "队列所有元素:" << endl; if ( queueDisplay( Q ) == false )    // 显示队列所有元素 {  cout << "队列为空!" << endl; }  /* 出队 */ for ( i = 0; i < 5; i++ ) {  if ( delQueue( Q ) == false )  {   cout << "队列以空" << endl;  } }  cout << endl; cout << endl; cout << "================== 出队以后 ===========================" << endl; cout << "出队后队头: " << queueFront( Q ) << endl; // 显示队头 cout << "出队后队列所有元素:" << endl; if ( queueDisplay( Q ) == false )     // 显示队列所有元素 {  cout << "队列为空!" << endl; }   cout << endl; cout << "输入入队5个数" << endl; /* 再入队 */ for ( i = 0; i < 5; i++ ) {  cin >> num;  if ( addQueue( Q, num ) == false )  {   cout << "队列以满!" << endl;  } }  cout << endl; cout << endl; cout << "================== 入队以后 ===========================" << endl; cout << "入队后队头: " << queueFront( Q ) << endl; // 显示队头 cout << "入队后队列所有元素:" << endl; if ( queueDisplay( Q ) == false )     // 显示队列所有元素 {  cout << "队列为空!" << endl; }  return 0;} /* 初始化队列 */void initQueue( Queue &Q ){ int i;  for ( i = 0; i < maxSize; i++ ) {  Q.data[i] = 0;  // 初始值都为0  Q.front = 0;  Q.rear = 0; }} /* 判断队列是否为空, 为空返回true, 不为空则返回flase */bool isEmpty( Queue &Q ){ if ( Q.front != 0 )  // 如果队头不等于0,则表示不为空 {  return false; }  return true;} /* 判断队列是否以满, 以满返回true, 没满则返回flase */bool isFull( Queue &Q ){ if ( Q.data[maxSize - 1] == 0 )  // 如果队尾等于0,则表示队列没满 {  return false; }  return true;} /* 若队列Q非满,则将元素x插入Q的队尾.此操作简称 入队 */bool addQueue( Queue &Q, int x ){ if ( isFull( Q ) == true ) // 检测队列是否以满 {  return false; }  int i;  for ( i = 0; i < maxSize; i++ ) {  if ( Q.data[i] == 0 ) // 当为0时则表示此位置没被复值,即可在此位置入队,且该值变为队尾  {   if ( i == 0 ) // 设队头   {    Q.front = x;   }    Q.data[i] = x;    Q.rear = x;  // 设队尾,每添加一个值,则该值即为队尾   return true;  } }} /* 若队列Q非空,则删去Q的队头元素,并返回该元素. 此操作简称 出队 */bool delQueue( Queue &Q ){ if ( isEmpty( Q ) == true ) // 检测队列是否为空 {  return false; }  int i;  /* 删除队头元素，并将所有队列元素提前一个位置 */ for ( i = 0; i < maxSize; i++ ) {  if ( Q.data[i] == 0 || i == maxSize - 1 ) // 判断队列中元素是否以全部提前  {   Q.data[i] = 0;   Q.front = Q.data[0]; // 设队头,每出队一个值,则原来第二个值变成队头   return true;  }   Q.data[i] = Q.data[i+1]; // 将队列元素提前 }} /* 若队列Q非空,则返回队头元素,但不改变队列Q的状态. */int queueFront( Queue &Q ){ if ( isEmpty( Q ) == true ) // 检测队列是否为空 {  return false; }  return Q.front;  // 返回队头元素 } /* 显示队列中的元素 */bool queueDisplay( Queue &Q ){ if ( isEmpty( Q ) == true ) // 检测队列是否为空 {  return false; }  int i;  for ( i = 0; i < maxSize; i++ ) {  if ( Q.data[i] == 0 ) // 判断队列中元素是否以全部显示  {   return true;  }   cout << "第" << i + 1 << "个: " << Q.data[i] << endl; } }   PS：偶是刚开始学数据结构的，由于偶写时是以结构体来实现的，写完后就懒的将结构体改成类了。。  呵呵。。

评论