隊列的C語言實現

隊列的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

#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);
	}
}