12编程实现队列的入队、出队、测长、打印

/*017编程实现队列的入队、出队、测长、打印*/
#include <stdio.h>
#include <malloc.h>

/*队列的实现可以用链表或数组，本例用单链表来实现队列*/
typedef struct _Node
{
    int data;
struct _Node *next;    /*指向链表下一个指针*/
}node;

typedef struct _Queue
{
    /*node表示队列中的每个节点元素，My Queue表示队列*/
node *front;           /*队头*/
node *rear;            /*队尾*/
}MyQueue;

/*在进行编程之前，首先要构造一个空的队列*/
MyQueue *CreateMyQueue()
{
    MyQueue *q = (MyQueue *)malloc(sizeof(MyQueue));    /*新建一个队列*/
q->front = NULL;                                    /*把队首指针置空*/
q->rear = NULL;                                     /*把队尾指针置空*/
    return q;
}

/*入队，从队尾一端插入节点*/
MyQueue *enqueue(MyQueue *q , int data)
{
    node *newP = NULL;
newP = (node *)malloc(sizeof(node));                /*新建节点*/
newP->data = data;                                  /*复制节点数据*/
newP->next = NULL;

if(q->rear == NULL)
{
        /*若队列为空，新节点既是队首又是队尾*/
  q->front = q->rear = newP;
}
    else
    {
        /*队列不为空，新节点放到队尾，队尾指针指向新节点*/
  q->rear->next = newP;
  q->rear = newP;
}
return q;
}

/*出队，从队头一端删除节点*/
MyQueue *dequeue(MyQueue *q)
{
    node *pnode = NULL;
pnode = q->front;                     /*指向队头*/
if(pnode == NULL)
{
        printf("Empty queue!\n");
}
else
{
        q->front = q->front->next;        /*新队头*/
  if(q->front == NULL)              /*若删除后队列为空时，对rear置空*/
  {
            q->rear = NULL;
  }
  free(pnode);                      /*删除原队头节点*/
}/*如果要得到被删除的节点，可以不释放内存并且返回此节点*/

return q;
}

/*队列的测长*/
int GetLength(MyQueue *q)
{
    int nlen = 0;
node *pnode = q->front;               /*指向队头*/
if(pnode != NULL)                     /*队列不能为空*/
{
        nlen = 1;
}
/*注意在代码中，循环结束的条件是"pnode != q->rear"，而不应该与NULL做比较，即"pnode != NULL",
这是因为队尾有可能指向的不是一个链表的末节点*/
while(pnode != q->rear)
{
        /*遍历队列*/
  pnode = pnode->next;
  nlen++;                           /*遍历一次nlen递增1*/
}

return nlen;
}

/*队列的打印*/
void PrintMyQueue(MyQueue *q)
{
    node *pnode = q->front;
if(pnode == NULL)
{
        /*队列为空*/
  printf("Empty Queue!\n");
  return;
}

printf("data: ");
while(pnode != q->rear)               /*遍历队列*/
{
        printf("%d " , pnode->data);       /*打印节点数据*/
  pnode = pnode->next;
}
printf("%d " , pnode->data);           /*打印队尾节点数据*/
}

int main()
{
    int nlen = 0;
MyQueue *hp = CreateMyQueue();        /*建立队列*/
enqueue(hp , 1);                      /*入队1234*/
enqueue(hp , 2);
enqueue(hp , 3);
enqueue(hp , 4);
nlen = GetLength(hp);                 /*获得队列长度*/
printf("nlen = %d\n" , nlen);
PrintMyQueue(hp);                     /*打印队列数据*/
dequeue(hp);                          /*出队两次*/
dequeue(hp);
nlen = GetLength(hp);                 /*再次获得队列长度*/
printf("\nnlen = %d\n" , nlen);    
PrintMyQueue(hp);                     /*再次打印队列数据*/
printf("\n");
return 0;
}