03-3.2.3 队列的链式存储的实现

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> [e-mail]

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

代码实现

typedef struct LinkNode{    //链式队列结点ElemType 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 testQueue(){LinkQueue Q;   //声明一个队列InitQueue(Q);  //初始化队列
}

带头结点的队列判空

bool IsEmpty(LinkQueue Q){if(Q.front == Q.rear)return true;elsereturn false;
}

不带头结点

void InitQueue(LinkQueue &Q){//初始时，front和rear都指向NULLQ.front = NULL;Q.rear = NULL;
}

不带头结点的队列判空

bool IsEmpty(LinkQueue Q){if(Q.front == NULL)return true;elsereturn false;
}

入队

带头结点

void EnQueue(LinkQueue &Q, ElemType x){LinkNode *s= (LinkNode *) malloc (sizeof(LinkNode));s->data = x;s->next = NULL;Q.rear->next = s;   //新结点插到rear之后 Q.rear = s;         //修改表尾指针
}

出队

带头结点

bool DeQueue(LinkQueue &Q, ElemType &x){if(Q.front == Q.rear)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;
}