1. 队列的链表实现EnQueue 在尾节点，DeQueue 在首节点。
1 #include "fatal.h" 2 3 typedef int ElementType ; 4 typedef struct QueueNode * Queue; 5 typedef struct QueueNode * Position; 6 7 #define MAXSIZE (6) 8 9 10 struct QueueNode { 11 ElementType data; 12 Position Next; 13 Position Rear; 14 Position Front; 15 int size; 16 }; 17 18 void DeleteQueue (Queue Q); 19 Queue MakeEmpty(Queue Q); 20 int IsEmpty (Queue Q); 21 int IsFull (Queue Q); 22 void EnQueue (ElementType X, Queue Q); 23 void DeQueue (Queue Q); 24 ElementType FrontAndDequeue (Queue); 25 26 27 28 int main(int argc, char *argv[]) { 29 Queue Q; 30 Q = MakeEmpty (NULL); 31 32 EnQueue (1,Q); 33 EnQueue (2,Q); 34 35 ElementType X = 12 ; 36 37 while ( !IsEmpty(Q)) { 38 printf ("%d ", Q->Front->data); 39 DeQueue (Q); 40 } 41 printf("\n"); 42 printf("Empty = %c\n",IsEmpty(Q)?'Y':'N' ); 43 44 Q = MakeEmpty (NULL); 45 EnQueue (X,Q); 46 EnQueue (21,Q); 47 EnQueue (X,Q); 48 printf("Queue is: "); 49 50 Position P = Q -> Front; 51 while (P) { 52 printf ("%d ",P->data); 53 P = P->Next; 54 } 55 printf("\n"); 56 57 printf ("Front and Rear:%d %d ",Q->Front->data,Q->Rear->data); 58 printf("\n"); 59 60 ElementType Y = FrontAndDequeue (Q); 61 printf ("Del and Front:%d %d ", Y,Q->Front->data); 62 63 printf("\n"); 64 Y = FrontAndDequeue (Q); 65 printf ("Del and Front:%d %d ", Y,Q->Front->data); 66 printf("\n"); 67 68 Y = FrontAndDequeue (Q); 69 printf ("Del and Front:%d %d\n", Y,(Q->Front == Q?0:Q->Front->data)); 70 71 DeQueue (Q); //do not Del any node 72 DeQueue (Q); 73 74 printf("size = %d\n",Q->size); 75 76 return 0; 77 78 } 79 80 81 void Delete (Queue Q) { 82 if ( Q = NULL) 83 Error ("Out of space."); 84 Position P, tmp; 85 P = Q->Next; 86 Q -> Next = NULL; 87 88 while ( P != NULL) { 89 tmp = P -> Next; 90 free (P); 91 P = tmp; 92 } 93 } 94 95 Queue MakeEmpty (Queue Q) { 96 if ( Q != NULL) 97 Delete (Q); 98 99 Q = malloc (sizeof (struct QueueNode));100 if ( Q == NULL) Error ("Out of memory.");101 Q -> Next = NULL;102 Q -> Rear = Q;103 Q -> Front = Q->Next;104 Q-> size = 0;105 return Q;106 }107 108 int IsFull (Queue Q) {109 return Q->size == MAXSIZE; 110 }111 112 int IsEmpty (Queue Q) {113 return Q->size == 0;114 }115 116 void EnQueue (ElementType X, Queue Q) {117 if ( Q == NULL ) Error ("Out of space.");118 119 Position tmp;120 tmp = malloc (sizeof (struct QueueNode));121 if (tmp == NULL) Error ("Out of space,");122 123 tmp -> data = X;124 Q -> Rear -> Next = tmp;125 Q -> Rear = tmp;126 Q -> Rear -> Next = NULL;127 Q -> Front = Q -> Next;128 Q->size++;129 130 if (Q -> size > MAXSIZE) Error ("Too large.");131 132 }133 134 void DeQueue (Queue Q) {135 if (IsEmpty(Q)) Error ("Empty Queue.");136 137 Position tmp = Q -> Front;138 Q -> Next = tmp -> Next;139 free(tmp);140 if (Q -> Front == Q->Rear) { Q->Front = Q;}141 else { Q -> Front = Q->Next; }142 Q->size--;143 }144 145 ElementType FrontAndDequeue ( Queue Q) {146 ElementType X;147 if (IsEmpty (Q)) Error ("Empty Queue.");148 149 X = Q ->Front->data;150 Position t = Q->Front;151 Q -> Next = t-> Next;152 if (Q -> Front == Q->Rear) { Q->Front = Q;}153 else { Q -> Front = Q->Next; }154 free (t);155 Q -> size--;156 157 return X;158 }