现在的位置: 首页 > 综合 > 正文

队列 – C语言实现（摘自数据结构与算法分析 C语言描述）

2017年10月12日 ⁄ 综合 ⁄ 共 11716字 ⁄ 字号 小 中 大 ⁄ 评论关闭

一、概述：

像栈一样，队列（queue）也是表。然而，使用队列时插入在一端进行而删除在另一端进行。

队列的基本操作是Enqueue（入队），它是在表的末端（叫做队尾（rear）插入一个元素，还有Dequeue（出队），它是删除（或返回）在表的开头（叫做队头（front）的元素。如图1所示显示一个队列的抽象模型。


图1 队列模型

二、实现

如同栈的情形一样，对于队列而言任何表的实现都是合法的。像栈一样，对于每一种操作，链表实现和数组实现都给出快速的O（1）运行时间。

1. 队列的链表实现

文件名：queue_list.h
[cpp] view
plaincopyprint?
  1. #ifndef _QUEUE_LIST_H  
  2. #define _QUEUE_LIST_H  
  3.   
  4. #define ElementType int  
  5. struct Node;  
  6. struct QNode;  
  7. typedef struct Node *PtrToNode;  
  8. typedef PtrToNode Queue;  
  9.   
  10.   
  11. int IsEmpty( Queue Q );  
  12. Queue CreateQueue( void );  
  13. void DisposeQueue( Queue Q );  
  14. void MakeEmpty( Queue Q );  
  15. void Enqueue( ElementType X, Queue Q );  
  16. ElementType Front( Queue Q );  
  17. void Dequeue( Queue Q );  
  18. ElementType FrontAndDequeue( Queue Q );  
  19.   
  20. #endif /* _QUEUE_LIST_H */  

文件名：queue_list.c

[cpp] view
plaincopyprint?
  1. #include "queue_list.h"  
  2. #include "fatal.h"  
  3.   
  4. typedef struct QNode  
  5. {  
  6.   ElementType Element;  
  7.   struct QNode *Next;  
  8. }QNode, *QNodePtr;  
  9.   
  10. struct Node {  
  11.   QNodePtr Front;  
  12.   QNodePtr Rear;  
  13. };  
  14.   
  15. int  
  16. IsEmpty( Queue Q )  
  17. {  
  18.   return Q->Front == Q->Rear;  
  19. }  
  20.   
  21. Queue  
  22. CreateQueue( void )  
  23. {  
  24.   Queue Q;  
  25.   Q = malloc( sizeof( struct Node ) );  
  26.   Q->Front = Q->Rear = malloc( sizeof( struct QNode ) );  
  27.   if (!Q->Front)  
  28.     FatalError( "Out of space!!!");  
  29.   Q->Front->Next = NULL;  
  30.   return Q;  
  31. }  
  32.   
  33. void  
  34. MakeEmpty( Queue Q )  
  35. {  
  36.   if( Q == NULL )  
  37.     Error( "Must use CreateQueue first" );  
  38.   else  
  39.     while( !IsEmpty( Q ) )  
  40.       Dequeue( Q );  
  41. }  
  42.   
  43. void  
  44. DisposeQueue( Queue Q )  
  45. {  
  46.   while( Q->Front ) {  
  47.     Q->Rear = Q->Front->Next;  
  48.     free( Q->Front );  
  49.     Q->Front = Q->Rear;  
  50.   }  
  51.   printf( "\nDispose queue completed!!!" );  
  52. }  
  53. void  
  54. Enqueue( ElementType X, Queue Q )  
  55. {  
  56.   QNodePtr p;  
  57.   p = malloc( sizeof( QNode ) );  
  58.   if (!p)  
  59.     FatalError( "Out of space!!!" );  
  60.   p->Element = X;  
  61.   p->Next = NULL;  
  62.   Q->Rear->Next = p;  
  63.   Q->Rear = p;  
  64. }  
  65.   
  66. ElementType  
  67. Front( Queue Q )  
  68. {  
  69.   if ( !IsEmpty( Q ) )  
  70.     return Q->Front->Next->Element;  
  71.   return 0; /* Return value used to avoid warning */  
  72. }  
  73.   
  74. void  
  75. Dequeue( Queue Q )  
  76. {  
  77.   if ( !IsEmpty( Q ) )  
  78.   {  
  79.     QNodePtr p;  
  80.     p = malloc( sizeof( QNode ) );  
  81.     if (!p)  
  82.       FatalError( "Out of space!!!" );  
  83.     p = Q->Front->Next;  
  84.     Q->Front->Next = p->Next;  
  85.     if ( Q->Rear == p )  
  86.       Q->Rear = Q->Front;  
  87.     free( p );  
  88.   }  
  89. }  
  90.   
  91. ElementType  
  92. FrontAndDequeue( Queue Q )  
  93. {  
  94.   if ( !IsEmpty( Q ) )  
  95.   {  
  96.     QNodePtr p;  
  97.     p = malloc( sizeof( QNode ) );  
  98.     if (!p)  
  99.       FatalError( "Out of space!!!" );  
  100.     p = Q->Front->Next;  
  101.     ElementType temp = 0;  
  102.     temp = p->Element;  
  103.     Q->Front->Next = p->Next;  
  104.     if ( Q->Rear == p )  
  105.       Q->Rear = Q->Front;  
  106.     free( p );  
  107.     return temp;  
  108.   }  
  109.   Error( "Empty queue!!!" );  
  110.   return 0; /* Return value used to avoid warning */  
  111. }  

文件名：queue_list_main.c

[cpp] view
plaincopyprint?
  1. #include <stdio.h>  
  2. #include "queue_list.h"  
  3.   
  4. int main()  
  5. {  
  6.   int n, num, m;  
  7.   int i;  
  8.   Queue Q = CreateQueue();  
  9.   printf( "Initialization complete.\n" );  
  10.   if ( IsEmpty( Q ) )  
  11.     printf( "Queue is empty \n" );  
  12.   printf( "Please input the number of elements in the queue:" );  
  13.   scanf( "%d", &n );  
  14.   printf( "Please input %d elements put in queue:", n );  
  15.   for(i = 0; i < n; i++ )  
  16.   {  
  17.     scanf( "%d", &num );  
  18.     Enqueue( num, Q );  
  19.   }  
  20.   printf( "Front element: %d.\n", Front( Q ) );  
  21.   printf( "Elements in queue:" );  
  22.   while ( !IsEmpty( Q )) {  
  23.     printf( "%3d", FrontAndDequeue( Q ) );  
  24.   }  
  25.   DisposeQueue( Q );  
  26.   printf( "\n" );  
  27.   return 0;  
  28. }  

2. 队列的数组实现

文件名：queue_array.h
[cpp] view
plaincopyprint?
  1. #ifndef QUEUE_ARRAY_H  
  2. #define QUEUE_ARRAY_H  
  3.   
  4. #define ElementType int  
  5. struct QueueRecord;  
  6. typedef struct QueueRecord *Queue;  
  7.   
  8. int IsEmpty( Queue Q );  
  9. int IsFull( Queue Q );  
  10. Queue CreateQueue( int MaxElements );  
  11. void DisposeQueue( Queue Q );  
  12. void MakeEmpty( Queue Q );  
  13. void Enqueue( ElementType X, Queue Q );  
  14. ElementType Front( Queue Q );  
  15. void Dequeue( Queue Q );  
  16. ElementType FrontAndDequeue( Queue Q );  
  17.   
  18. #endif /* QUEUE_ARRAY_H */  

文件名：queue_array.c

[cpp] view
plaincopyprint?
  1. #include "queue_array.h"  
  2. #include "fatal.h"  
  3.   
  4. /* Place in implementation file 
  5.  * Queue implementation is a dynamically allocated array*/  
  6. #define MinQueueSize ( 5 )  
  7.   
  8. struct QueueRecord  
  9. {  
  10.   int Capacity;  
  11.   int Front;  
  12.   int Rear;  
  13.   int Size;  
  14.   ElementType *Array;  
  15. };  
  16.   
  17. int  
  18. IsEmpty( Queue Q )  
  19. {  
  20.   return Q->Size == 0;  
  21. }  
  22.   
  23. void  
  24. MakeEmpty( Queue Q )  
  25. {  
  26.   Q->Size = 0;  
  27.   Q->Front = 1;  
  28.   Q->Rear = 0;  
  29. }  
  30.   
  31. static int  
  32. Succ( int value, Queue Q )  
  33. {  
  34.   if ( ++value == Q->Capacity )  
  35.     value = 0;  
  36.   return value;  
  37. }  
  38.   
  39. void  
  40. Enqueue( ElementType X, Queue Q )  
  41. {  
  42.   if( IsFull( Q ) )  
  43.     Error( "Full queue" );  
  44.   else  
  45.   {  
  46.     Q->Size++;  
  47.     Q->Rear = Succ( Q->Rear, Q );  
  48.     Q->Array[ Q-> Rear ] = X;  
  49.   }  
  50. }  
  51.   
  52. void  
  53. Dequeue( Queue Q )  
  54. {  
  55.   if ( IsEmpty( Q ) )  
  56.     Error( "Empty queue" );  
  57.   else  
  58.   {  
  59.     Q->Size--;  
  60.     Q->Front++;  
  61.   }  
  62. }  
  63.   
  64. ElementType  
  65. FrontAndDequeue( Queue Q )  
  66. {  
  67.   ElementType temp = 0;  
  68.   if ( IsEmpty( Q ) )  
  69.     Error( "Empty queue" );  
  70.   else  
  71.   {  
  72.     Q->Size--;  
  73.     temp= Q->Array[ Q->Front ];  
  74.     Q->Front = Succ( Q->Front, Q );  
  75.   }  
  76.   return temp;  
  77. }  
  78.   
  79. ElementType  
  80. Front( Queue Q )  
  81. {  
  82.   if ( !IsEmpty( Q ) )  
  83.     return Q->Array[ Q->Front ];  
  84.   Error( "Empty queue" );  
  85.   return 0;  /* Return value used to avoid warning */  
  86. }  
  87.   
  88. int  
  89. IsFull( Queue Q )  
  90. {  
  91.   return Q->Size == Q->Capacity;  
  92. }  
  93.   
  94. Queue  
  95. CreateQueue(int MaxElements )  
  96. {  
  97.   Queue Q;  
  98.   
  99.   if ( MaxElements < MinQueueSize )  
  100.     Error( "Queue size is too small!!!" );  
  101.   Q = malloc( sizeof( struct QueueRecord ) );  
  102.   if ( Q == NULL )  
  103.     FatalError( "Out of space!!!" );  
  104.   Q->Array = malloc( sizeof( ElementType ) * MaxElements );  
  105.   if ( Q->Array == NULL )  
  106.     FatalError( "Out of Space!!!" );  
  107.   Q->Capacity = MaxElements;  
  108.   MakeEmpty( Q );  
  109.   
  110.   return Q;  
  111. }  
  112.   
  113. void  
  114. DisposeQueue( Queue Q )  
  115. {  
  116.   if ( Q != NULL )  
  117.   {  
  118.     free( Q->Array );  
  119.     free( Q );  
  120.   }  
  121. }  

文件名：queue_main.c

[cpp] view
plaincopyprint?
  1. #include <stdio.h>  
  2. #include "queue_array.h"  
  3.   
  4. int  
  5. main()  
  6. {  
  7.   int size;  
  8.   printf( "Please input queue size: " );  
  9.   scanf( "%d", &size );  
  10.   Queue Q = CreateQueue( size );  
  11.   ElementType temp;  
  12.   printf( "Please input queue elements(seperate by space): " );  
  13.   while ( !IsFull( Q ) )  
  14.   {  
  15.     scanf( "%d", &temp );  
  16.     Enqueue( temp, Q );  
  17.   }  
  18.   
  19.   printf( "Dequeue queue in turn: " );  
  20.   while ( !IsEmpty( Q ) )  
  21.   {  
  22.     printf( "%3d", FrontAndDequeue( Q ) );  
  23.   }  
  24.   printf( "\n" );  
  25.   DisposeQueue( Q );  
  26.   return 0;  
  27. }  
附录：上述代码中用到了Error、FatalError等函数，其实现如下（即fatal.h文件）：
[cpp] view
plaincopyprint?
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3.   
  4. #define Error( Str )        FatalError( Str )  
  5. #define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )  

备注：本文摘自《数据结构与算法分析 C语言描述 Mark Allen Weiss著》，代码经gcc编译测试通过。

附件下载：http://download.csdn.net/detail/shuxiao9058/4212437#queue-array.tar.gz，http://download.csdn.net/detail/shuxiao9058/4212435#queue-list.tar.gz


返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞