链表实现的队列

2019独角兽企业重金招聘Python工程师标准>>>

/*
 * queue2.c
 *
 *  Created on: Dec 17, 2012
 *      Author: fsxchen
 *      链表实现的队列
 */


#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"

typedef struct QNode           //节点的结构体
{
	int date;               //存放数据
	struct QNode *next;      //链表指向下一个节点
}QNode, *QueuePtr;

typedef struct
{
	QueuePtr front, rear;     //队列的首尾指针
}LinkQueue;

/*初始化*/
void InitQueue(LinkQueue *q, QueuePtr pHead)
{
	pHead->next = NULL;
	q->front = pHead;
	q->rear = pHead;
}
/*入对操作*/
void EnQueue(LinkQueue *q)
{
	int val;
	QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
	if(!s)
	{
		printf("分配存储出错！");
		exit(-1);
	}
	printf("请输入您要输入的值");
	scanf("%d", &val);
	s->date = val;
	s->next = NULL;
	q->rear->next = s;
	q->rear = s;
}

int DeQueue(LinkQueue *q)
{
	int n;
	QueuePtr p;
	if(q->front == q->rear)
	{
		printf("the queue is NULL!");
		return 0;
	}
	n = q->front->date;
	p = q->front->next;                      //注意保存，后面free要用
	q->front = q->front->next->next;
	if(p == q->rear)
		q->rear = q->front;
	free(p);
	return n;
}

int main()
{
	LinkQueue s;
	QueuePtr pHead = (QueuePtr)malloc(sizeof(QNode));
	InitQueue(&s, pHead);
	EnQueue(&s);
	return 0;
}

当队列为空的时候，头尾指针都指向头节点
关于数组和链表，前者在查找上面很有优势，而后者在添加删除上面性能更好！

转载于:https://my.oschina.net/fsxchen/blog/108878