习题3.25 链表和数组对队列例程实现
//链表做队列 /* assume a header */ struct Node; struct Queue; typedef struct Node * PtrToNode; typedef struct Queue * PtrToQ; struct Node{ ElementType ele; PtrToNode Next; }; struct Queue{ PtrToNode rear; PtrToNode front; }; PtrToQ CreateQ( void ) { PtrToQ Q; Q = malloc( sizeof( struct Queue ) ); Q->rear = Q->front = malloc( sizeof( struct Node ) ); Q->rear->next = NULL; } void AddQ( ElementType X, PtrToQ Q ) { PtrToNode TmpCell; Tmpcell = malloc( sizeof( struct Node ) ); TmpCell->ele = X; TmpCell->Next = NULL; Q->rear->Next = TmpCell; Q->rear = TmpCell; } Elementtype DeleteQ( PtrToQ Q ) { ElementType res; PtrToNode TmpCell; TmpCell = Q->front->Next; Q->front->Next = TmpCell->Next; res = Tmpcell->ele; free( TmpCell ); return res; }
以上使用链表做的
以下是用数组做的
//循环数组 #define MaxSize 100 struct Queue; typedef struct Queue * PtrToQ; struct Queue{ ElementType *Array; int front; int rear; }; PtrToQ CreateQ( int Size ) { PtrToQ Q; Q = malloc( sizeof( struct Queue ) ); Q->Array = malloc( sizeof( ElementType ) * Size ); Q->front = Q->rear = 0; return Q; } int IsFull( PtrToQ Q ) { return ( Q->rear + 1 ) % MaxSize == Q->front; } void AddQ( ElementType X, PtrToQ Q ) { if( !IsFull( Q ) ){ Q->rear = ( Q->rear + 1 ) % MaxSize; Q->Array[ Q->rear ] = X; } else Error("full") } int IsEmpty( PtrToQ Q ) { return Q->rear == Q->front; } ElementType DeleteQ( PtrToQ Q ) { if( !IsEmpty( Q ) ) { Q->front = ( Q->front + 1 ) % MaxSize; return Q->front->ele; } else Error(); }