队列的C语言实现

队列不同于栈，它是先进先出，即先入队列的元素提取时也要先出队列。队列可以用数组实现也可以用链表实现，挺简单的，但是很有些情况下很有用。它的实现只要维持好队首和队尾指针就好了。下面是我实现的链表队列。

queue.h

 

#ifndef __QUEUE_H
#define __QUEUE_H

#include 
#include 

struct QueueNode;
struct queue;

typedef Vertex ElementType;
typedef struct QueueNode *Node;
typedef struct queue *Queue;

struct QueueNode
{
	ElementType element;
	Node next;
};

struct queue
{
	Node first;
	Node last;
};

Queue createQueue();
int isEmpty(Queue Q);
void EnQueue(ElementType X,Queue Q);
ElementType DeQueue(Queue Q);
void deleteQueue(Queue Q);


#endif

queue.c

 

 

#include queue.h

Queue createQueue()
{
	Queue Q;
	Node node;
	node=(Node)malloc(sizeof(struct QueueNode));
	if(node==NULL)
	{
		printf(out of space
);
		exit(-1);
	}
	node->next=NULL;
	
	Q=(Queue)malloc(sizeof(struct queue));
	if(Q==NULL)
	{
		printf(out of space
);
		exit(-1);
	}
	
	Q->first=node;
	Q->last=node;

	return Q;
}

int isEmpty(Queue Q)
{
	if(Q->first==Q->last)
		return 1;
	else
		return 0;
}

void EnQueue(ElementType X,Queue Q)
{
	Node node;
	node=(Node)malloc(sizeof(struct QueueNode));
	if(node==NULL)
	{
		printf(out of space
);
		exit(-1);
	}
	node->element=X;
	node->next=NULL;
	Q->last->next=node;
	Q->last=node;
}

ElementType DeQueue(Queue Q)
{
	ElementType x;
	Node p;
	if(isEmpty(Q))
	{
		printf(queue is empty
);
		exit(-1);
	}
	p=Q->first->next;
	Q->first->next=p->next;
	x=p->element;
	if(p==Q->last)
	{
		Q->last=Q->first;
	}
	free(p);
	return x;
}

void deleteQueue(Queue Q)
{
	while(!isEmpty(Q))
	{
		DeQueue(Q);
	}
}