天天看點
傳回

資料結構：隊列的基本操作

隊列是一種先進先出（First in First Out）的線性表，簡稱FIFO。與棧不同，棧是一種後進先出（先進後出）的線性表。在隊列中，允許插入的一端稱為隊尾，允許删除的一端稱為隊頭。假設隊列是q=（a1,a2,…,an），那麼a1就是隊頭元素，而an是隊尾元素。這樣我們就可以删除時，總是從a1開始，而插入時，列在最後。這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最後來的當然在隊伍的最後。隊列分為順序隊列和循環隊列。順序隊列我們可以利用數組或者連結清單實作。這裡，我們選擇用連結清單實作順序隊列。

鍊隊列

鍊隊列的入隊和出隊
資料結構：隊列的基本操作
鍊隊列的入隊操作 
Status EnQueue(LinkQueue *Q,QElemType e)
{
	QNode *p;
	p=(QNode *)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
	return OK;
}
鍊隊列的出隊操作 
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QNode *p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;
	*e=p->data;
	Q->front->next=p->next;
	if(Q->rear==p)///防止出現野指針
		Q->rear=Q->front;
	free(p);
	return OK;
}
鍊隊列的基本操作代碼(C語言版) 
#include "stdio.h"
#include "stdlib.h"

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

typedef int QElemType;
typedef int Status;

typedef struct QNode
{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

Status InitQueue(LinkQueue *Q)
{
	
	Q->front=(QueuePtr)malloc(sizeof(QNode));///給頭尾指針配置設定記憶體，讓隊列中的頭尾指針指向同一個記憶體
	Q->rear=Q->front;
	if(!Q->front) exit(OVERFLOW);
	Q->front->next=NULL;
	return OK;
}
Status EnQueue(LinkQueue *Q,QElemType e)
{
	QNode *p;
	p=(QNode *)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q->rear->next=p;
	Q->rear=p;
	return OK;
}

void ShowQueueElement(LinkQueue Q)
{
	QNode *p;
	p=Q.front->next;
	while(p!=NULL)
	{
		printf("%d  ",p->data);
		p=p->next;
	}
	printf("\n");
}

int QueueLength(LinkQueue Q)
{
	int count=0;
	QNode *p;
	p=Q.front->next;
	while(p!=NULL)
	{
		count++;
		p=p->next;
	}
	return count;
}

Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QNode *p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;
	*e=p->data;
	Q->front->next=p->next;
	if(Q->rear==p)
		Q->rear=Q->front;
	free(p);
	return OK;
}

Status GetHead(LinkQueue Q,QElemType *e)
{
	QNode *p;
	p=Q.front;
	if(Q.front==Q.rear)
		return ERROR;
	*e=p->next->data;
	return OK;
}

Status ClearQueue(LinkQueue *Q)
{
	QNode *p,*q;
	p=Q->front->next;
	Q->front->next=NULL;
	while(p)
	{
		q=p->next;
		free(p);
		p=q;
	}
	Q->front=Q->rear;
	return OK;
}

Status QueueEmpty(LinkQueue *Q)
{
	if(Q->front->next==NULL)
		return TRUE;
	else
		return FALSE;
}

Status DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
 		Q->rear=Q->front->next;///隊尾指針始終指向隊頭指針的下一個元素
		free(Q->front);
		Q->front=Q->rear;///調整隊頭指針
	}
	return OK;
}

void main()
{
	LinkQueue Q;
	int choice=1;
	if(InitQueue(&Q)==OK)
		printf("OK\n");
	else
		printf("error!\n");
	while(choice!=0)
	{
		system("cls");
		printf("1.InitQueue         2.EnQueue        3.ShowQueueElement\n");
		printf("4.DeQueue           5.GetHead        6.QueueLength    7.ClearQueue \n");
		printf("8.QueueEmpty        9.DestroyQueue     0.exit\n");
		printf("please input your choice:\n");
		scanf("%d",&choice);
		switch(choice)
		{
		case 1:
			{
				if(InitQueue(&Q)==OK)
					printf("OK\n");
				break;
			}
		case 2:
			{
				int n,i;
				QElemType num;
				printf("請輸入要入隊的總數：\n");
				scanf("%d",&n);
				for(i=0;i<n;i++)
				{
					scanf("%d",&num);
					if(EnQueue(&Q,num)==OK)
					printf("%d成功入隊\n",num);
				}
				break;
			}
		case 3:
			{
				printf("您輸入的數為：\n");
				ShowQueueElement(Q);
				break;
			}
		case 4:
			{
				QElemType e;
				int index,i,num;
				printf("請輸入您想出隊幾個數：\n");
				scanf("%d",&num);
				index=QueueLength(Q);
				if(num>index)
					printf("越界了!\n");
				else
				{
					for(i=0;i<num;i++)
					{
						if(DeQueue(&Q,&e)==OK)
						printf("第%d次出隊的元素為：%d\n",i+1,e);
					}
				}
				break;
			}
		case 5:
			{
				QElemType e;
				if(GetHead(Q,&e)==OK)
					printf("the head number is %d\n",e);
				break;
			}
		case 6:
			{
				int length;
				length=QueueLength(Q);
				printf("The queue's length is %d\n",length);
				break;
			}
		case 7:
			{
				if(ClearQueue(&Q)==OK)
					printf("成功清空隊列!\n");
				else
					printf("清空隊列失敗!\n");
				break;
			}
		case 8:
			{
				if(QueueEmpty(&Q)==TRUE)
					printf("隊列為空!\n");
				else
					printf("隊列不為空!\n");
				break;
			}
		case 9:
			{
				if(DestroyQueue(&Q)==OK)
					printf("隊列已銷毀!\n");
				else
					printf("隊列銷毀失敗!\n");
				break;
			}
		}
		system("pause");
	}
}

循環隊列

循環隊列就是将隊列存儲空間的最後一個位置繞到第一個位置，形成邏輯上的環狀空間，供隊列循環使用。在循環隊列結構中，當存儲空間的最後一個位置已被使用而再要進入隊運算時，隻需要存儲空間的第一個位置空閑，便可将元素加入到第一個位置，即将存儲空間的第一個位置作為隊尾。循環隊列可以更簡單防止僞溢出的發生，但隊列大小是固定的。

在循環隊列中，當隊列為空時，有front=rear，而當所有隊列空間全占滿時，也有front=rear。為了差別這兩種情況，規定循環隊列最多隻能有MaxSize-1個隊列元素，當循環隊列中隻剩下一個空存儲單元時，隊列就已經滿了。是以，隊列判空的條件是front=rear，而隊列判滿的條件是front=（rear+1)%MaxSize。

循環隊列的入隊和出隊
資料結構：隊列的基本操作
循環隊列的入隊操作 
Status EnQueue(SqQueue *Q,QElemType e)
{
	if((Q->rear+1)%MAXQSIZE==Q->front)
		return ERROR;
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXQSIZE;
	return OK;
}
循環隊列的出隊操作 
Status DeQueue(SqQueue *Q,QElemType *e)
{
	if(Q->front==Q->rear)
		return ERROR;
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%MAXQSIZE;
	return OK;
}
循環隊列的基本操作代碼(C語言版) 
#include "stdio.h"
#include "stdlib.h"

#define MAXQSIZE 100

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;

typedef struct 
{
	QElemType *base;
	int front;
	int rear;
}SqQueue;

Status InitQueue(SqQueue *Q)
{
	Q->base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));
	if(!Q->base) 
		exit(OVERFLOW);
	Q->front=0;
	Q->rear=0;
	return OK;
}

Status EnQueue(SqQueue *Q,QElemType e)
{
	if((Q->rear+1)%MAXQSIZE==Q->front)
		return ERROR;
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%MAXQSIZE;
	return OK;
}

void ShowQueueElement(SqQueue Q)
{
	int i=0;
	for(i=0;i<(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;i++)
		printf("%d ",Q.base[i]);
		printf("\n");
}

int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

Status DeQueue(SqQueue *Q,QElemType *e)
{
	if(Q->front==Q->rear)
		return ERROR;
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%MAXQSIZE;
	return OK;
}

Status IsFull(SqQueue *Q)
{
	return Q->front==(Q->rear+1)%MAXQSIZE?TRUE:FALSE;
}

Status IsEmpty(SqQueue *Q)
{
	return Q->front==Q->rear?TRUE:FALSE;
}

Status ClearQueue(SqQueue *Q)
{
	Q->front=0;
	Q->rear=0;
	return OK;
}

Status GetHead(SqQueue Q,QElemType *e)
{
	if(Q.front==Q.rear)
		return ERROR;
	*e=Q.base[Q.front];
	return OK;
}

Status DestroyQueue(SqQueue *Q)
{
	if(Q->base)
		free(Q->base);
	Q->base=NULL;
	Q->front=0;
	Q->rear=0;
	return OK;
}
void main()
{
	SqQueue Q;
	QElemType e;
	int choice=1,i;
	if(InitQueue(&Q)==OK)
		printf("OK\n");
	else
		printf("ERROR!\n");
	while(choice!=0)
	{
		system("cls");
		printf("1.InitQueue    2.EnQueue       3.ShowQueueElement \n");
		printf("4.QueueLength   5.DeQueue       6.GetHead  \n");
		printf("7.IsFull        8.IsEmpty       9.ClearQueue \n");
		printf("10.DestroyQueue     0.exit\n");
		printf("please input your choice:\n");
		scanf("%d",&choice);
		switch(choice)
		{
		case 1:
			{
				if(InitQueue(&Q)==OK)
					printf("成功建立一個隊列！\n");
				break;
			}
		case 2:
			{
				int n;
				printf("請輸入要入隊的總數：\n");
				scanf("%d",&n);
				for(i=0;i<n;i++)
				{
					printf("請輸入第%d個入隊的元素：\n",i+1);
					scanf("%d",&e);
					if(EnQueue(&Q,e)==OK)
						printf("%d入隊成功！\n",e);
					else
						printf("隊列已滿！\n");
				}
				break;
			}
		case 3:
			{
				printf("隊列中的元素為：\n");
				ShowQueueElement(Q);
				break;
			}
		case 4:
			{
				int index;
				index=QueueLength(Q);
				printf("隊列的長度為：%d\n",index);
				break;
			}
		case 5:
			{
				int num,index,i;
				printf("請輸入您想出隊幾個數：\n");
				scanf("%d",&num);
				index=QueueLength(Q);
				if(num>index)
					printf("越界了!\n");
				else
				{
					for(i=0;i<num;i++)
					{
						if(DeQueue(&Q,&e)==OK)
							printf("第%d次删除的隊頭元素為：%d\n",i+1,e);
						else
							printf("隊列為空!\n");
					}
				}
				break;
			}
		case 6:
		{
			if(GetHead(Q,&e)==OK)
				printf("隊頭元素為：%d\n",e);
			else
				printf("隊列為空！\n");
			break;
		}
		case 7:
			{
				if(IsFull(&Q)==TRUE)
					printf("隊列已滿！\n");
				else
					printf("隊列未滿！\n");
				break;
			}
		case 8:
			{
				if(IsEmpty(&Q)==TRUE)
					printf("空隊列！\n");
				else
					printf("不是空隊列！\n");
				break;
			}
		case 9:
			{
				if(ClearQueue(&Q)==OK)
					printf("清空隊列成功！\n");
				else
					printf("清空隊列失敗！\n");
				break;
			}

		case 10:
			{
				if(DestroyQueue(&Q)==OK)
					printf("銷毀隊列成功！\n");
				else
					printf("銷毀隊列失敗！\n");
				break;
			}
		}
		system("pause");
	}
}
知識點總結
上一篇: java講解_Java程式員的日常 —— static的用法講解實踐
下一篇: 隊列的基本操作_隊列

繼續閱讀