学步园

一. 先说顺序队列

/***********************************************************
顺序队列的各种操作13-4-1.cpp
1.初始化队列
2.判断队空与否
3.取队头元素
4.入队
5.出队
6.主函数测试以上功能
***********************************************************/
#include<stdio.h>
#include<stdlib.h>

#define MAX	1000
typedef struct
{
	int data[MAX];
	int front;
	int rear;
}SeQueue;

void InitQueue(SeQueue *SQ)
{
	SQ->front=SQ->rear=0;
}

int EmptyQueue(SeQueue *SQ)
{
	if(SQ->front==SQ->rear)
	{
		printf("\n队空!\n");
		return 1;
	}
	return 0;
}

int GetFront(SeQueue *SQ, int *x)
{
	if(EmptyQueue(SQ))
	{
		printf("队空!\n");
		return 0;
	}
	*x=SQ->data[(SQ->front+1)%MAX];
	return 1;
}

int EnQueue(SeQueue *SQ, int x)
{
	if(SQ->front==(SQ->rear+1)%MAX)
	{
		printf("队满!\n");
		return 0;
	}
	SQ->rear=(SQ->rear+1)%MAX;
	SQ->data[SQ->rear]=x;
	return 1;
}

int OutQueue(SeQueue *SQ, int *x)
{
	if(EmptyQueue(SQ))
	{
		printf("队空!\n");
		return 0;
	}
	SQ->front=(SQ->front+1)%MAX;
	*x=SQ->data[SQ->front];
	return 1;
}

int main()
{
	SeQueue *Q;
	Q=(SeQueue *)malloc(sizeof(SeQueue));
	int x, fx;
	int n;
	int j;
	InitQueue(Q);
	printf("输入入队元素个数n：\n");
	scanf("%d", &n);
	for(int i=1; i<=n; i++)
	{
		EnQueue(Q, i);
	}
	GetFront(Q, &fx);
	printf("队头元素:%d\n", fx);
	printf("输出队列元素：\n");
	for(j=Q->front+1;j<=Q->rear;j=(j+1)%MAX)
	{
		printf("%3d",Q->data[j]);	
	}

	for(int i=1; i<=n; i++)
	{
		OutQueue(Q, &x);
		printf("\n出队元素:%d\n", x);
	}
	system("pause");
	return 0;
}

二.再说链队列

/***********************************************************
链队列的各种操作13-4-2.cpp
1.初始化队列
2.判断队空与否
3.取队头元素
4.入队
5.出队
6.主函数测试以上功能
***********************************************************/
#include<stdio.h>
#include<stdlib.h>

typedef struct Lnode
{
	int data;
	struct Lnode *next;
}LinkList;

typedef struct
{
	LinkList *front;
	LinkList *rear;
}LinkQueue;

int InQueue(LinkQueue *LQ)
{
	LinkList *p=(LinkList*)malloc(sizeof(LinkList));
	if(p==NULL)
	{
		printf("初始化失败!\n");
		return 0;
	}
	p->next=NULL;
	LQ->front=LQ->rear=p;
	return 1;
}

int EmptyQueue(LinkQueue *LQ)
{
	if(LQ->front==LQ->rear)
	{
		printf("队列空!\n");
		return 1;
	}
	return 0;
}

int EnQueue(LinkQueue *LQ, int x)
{
	LinkList *s=(LinkList *)malloc(sizeof(LinkList));
	if(s==NULL)
	{
		printf("分配空间失败!\n");
		return 0;
	}
	s->data=x;
	s->next=NULL;
	LQ->rear->next=s;
	LQ->rear=s;
	return 1;
}

int GetFront(LinkQueue *LQ, int *x)
{
	if(EmptyQueue(LQ))
	{
		printf("队空!\n");
		return 0;
	}
	*x=LQ->front->next->data;
	return 1;
}

int OutQueue(LinkQueue *LQ, int *x)
{
	LinkList *p;
	if(EmptyQueue(LQ))
	{
		printf("队空!\n");
		return 0;
	}
	p=LQ->front->next;
	*x=p->data;
	LQ->front->next=p->next;
	if(LQ->front->next==NULL)
	{
		LQ->rear=LQ->front;
	}
	free(p);
	return 1;
}

int main()
{
	LinkQueue *Q;
	Q=(LinkQueue *)malloc(sizeof(LinkQueue));
	LinkList *p;
	int n, x, fx;
	InQueue(Q);
	printf("请输入入队元素个数n:\n");
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		EnQueue(Q, i);
	}

	GetFront(Q, &fx);
	printf("队首元素:%d\n", fx);

	printf("输出队列元素:\n");
	for(p=Q->front->next; p!=NULL; p=p->next)
	{
		printf("%3d", p->data);
	}
	for(int i=1; i<=n; i++)
	{
		OutQueue(Q, &x);
		printf("\n出队元素:%d\n", x);
	}

	system("pause");
	return 0;
}
注意：//1)链队列入队的死或坏，这个跟顺序队列入队就不一样了，顺序队列入队要先判断队满与否，因为数组有边界，但是链队列是用链表存储的，没有边界，所以不用判断队列满
//2)与顺序队列一样，出队要判断队空与否。)出队和GetFront非常像。
//3)出队的时候，front一直没有变，只不过是把front的Next给做掉了。
	//4)这个链队列出队要注意如果只剩下一个节点情况(删除完之后LQ->front->next==NULL)，这是LQ->rear是游离的，一定要将LQ->front赋给rear

运行结果截图：