算法基礎（三）：隊列基礎

先上一張圖：（我這裡的隊列為一般隊列，雙向隊列、循環隊列等下一章讨論）

下面是實作源碼：

#include "stdafx.h"
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

#define TRUE  1 
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int Status;					//函數傳回值

typedef int QElemType;				//暫定元素類型為int，可以根據自己需要修改
typedef struct	QNode				//定義節點類型
{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct
{
	QueuePtr front;					//定義隊頭指針
	QueuePtr rear;					//定義隊尾指針
}LinkQueue;
/*---------------------------以下是隊列的基本操作的函數聲明以及實作--------------------------------*/
Status InitQueue(LinkQueue &Q);		//構造一個空隊列
Status DestroyQueue(LinkQueue &Q);	//銷毀隊列
Status InsertQueue(LinkQueue &Q,QElemType e);		//插入元素e為Q的隊尾元素
Status DeQueue(LinkQueue &Q);			//在隊列不為空的情況下，删除隊頭元素

//入口測試函數

int _tmain(int argc, _TCHAR* argv[])				
{	 
	LinkQueue Q;
	if(InitQueue(Q))
	{
		//初始化配置設定空間成功
		for(int i = 0;i<10; i++)	//0~9自然數入隊
		{
			InsertQueue(Q,i);
		}
		printf("\n元素入隊完畢...測試...");
		for(int i = 0;i<10;i++)		//
		{
			printf("\n出隊元素為:%d",DeQueue(Q));
		}
	}
	return 0;
}

Status InitQueue(LinkQueue &Q)
{
	Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q.front)exit(OVERFLOW);
	Q.front->next = NULL;
	return OK;
}
Status DestroyQueue(LinkQueue &Q)	//銷毀隊列
{
	while(Q.front)
	{
		Q.rear = Q.front->next;
		free(Q.front);
		Q.front = Q.rear;
	}
	return OK;
}
Status InsertQueue(LinkQueue &Q,QElemType e)		//插入元素e為Q的隊尾元素
{
	QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
	if(!p)exit(OVERFLOW);
	p->data = e;			//指派
	p->next = NULL;			
	Q.rear->next = p;		//連接配接
	Q.rear = p;				//新的隊尾
	return OK;
}

QElemType DeQueue(LinkQueue &Q )			//在隊列不為空的情況下，删除隊頭元素
{
	QElemType e;
	if(Q.front == Q.rear)
		return ERROR;		//空隊列，傳回
	QueuePtr p = Q.front->next;
	e = p->data;
	Q.front->next = p->next;
	if(Q.rear == p)
		Q.rear = Q.front;	//删得都隻剩一個了，隊首隊尾是同一個節點
	free(p);
	return e;
}