队列的链式实现

一、带头结点

#include<stdio.h> #include<stdlib.h> /*链栈定义:带头结点*/ typedef struct LinkNode{ //链式队列结点 int data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列结点 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue; /*初始化*/ void InitQueue(LinkQueue &Q){ //初始时，front、rear都指向头结点 Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode)); Q.front->next = NULL; } /*入队(带头结点)*/ void EnQueue(LinkQueue &Q, int x){ LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode)); p->data = x; p->next = NULL; Q.rear->next = p; //新结点插入到rear之后 Q.rear = p; //修改表尾指针 } /*出队(带头结点)*/ bool DeQueue(LinkQueue &Q,int &x){ if(Q.rear == Q.front) return false; //空队 LinkNode *p = Q.front->next; x = p->data; //用变量x返回队头元素 Q.front->next = p->next; //修改头结点的next指针 if(Q.rear == p) //此次是最后一个结点 Q.rear = Q.front; //修改rear指针 free(p); //释放结点空间 return true; } /*获取队头元素*/ bool GetHead(LinkQueue Q,int &x){ if(Q.rear == Q.front) return false; x = Q.front->next->data; return true; } int main(){ int ret; //获取返回值 LinkQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,8); GetHead(Q,ret); printf("GetHead:%d\n",ret); DeQueue(Q,ret); GetHead(Q,ret); printf("GetHead:%d\n",ret); return 0; }

二、不带头结点

#include<stdio.h> #include<stdlib.h> /*链栈定义:不带头结点*/ typedef struct LinkNode{ //链式队列结点 int data; struct LinkNode *next; }LinkNode; typedef struct{ //链式队列结点 LinkNode *front,*rear; //队列的队头和队尾指针 }LinkQueue; /*初始化*/ void InitQueue(LinkQueue &Q){ //初始时，front、rear都指向NULL Q.front = Q.rear = NULL; } /*入队(不带头结点)*/ void EnQueue(LinkQueue &Q, int x){ LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode)); p->data = x; p->next = NULL; if(Q.front == NULL){ //在空队列中插入第一个元素 Q.front = p; //修改队头指针 Q.rear = p; } else{ Q.rear->next = p; //新结点插入到rear之后 Q.rear = p; //修改表尾指针 } } /*出队(不带头结点)*/ bool DeQueue(LinkQueue &Q,int &x){ if(Q.front == NULL) return false; //空队 LinkNode *p = Q.front; x = p->data; //用变量x返回队头元素 Q.front = p->next; //修改头结点的next指针 if(Q.rear == p){ //此次是最后一个结点出队 Q.front = NULL; //front指向NULL Q.rear = NULL; //rear指针指向NULL } free(p); //释放结点空间 return true; } /*获取队头元素*/ bool GetHead(LinkQueue Q,int &x){ if(Q.front == NULL) return false; x = Q.front->data; return true; } int main(){ int ret; //获取返回值 LinkQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,8); GetHead(Q,ret); printf("GetHead:%d\n",ret); DeQueue(Q,ret); GetHead(Q,ret); printf("GetHead:%d\n",ret); return 0; }