队列

c/c++

浏览数:233

2019-6-29

  队列是一种只允许在一端进行插入,而在另一端进行删除的线性表,它是一种操作受限制的线性表,在该表中只允许插入的一端称为队尾(rear),二另一端只允许删除的一端称为队首(front)。

一、队列的顺序存储

  队列的顺序存储结构就可以称为顺序队列,也就是利用一组地址连续的存储单元将元素依次存放在队列中。如图:

由上图可知可以先写出其数据类型

typedef struct queue
{
	ElemType elem[MAXSIZE];
	int front;
	int rear;
}queue;

  其中的MAXSIZE指明的是队列中的存储容量的大小,队列初始化时,将队尾的索引与队首的索引都相同且置为-1

void Init_queue(queue *Q)
{
	Q->front=-1;
	Q->rear=-1;
}

这个时候就可以进行一系列的操作了,如下:

#include<stdio.h>
#define MAXSIZE 10
typedef int ElemType;

typedef struct queue
{
	ElemType elem[MAXSIZE];
	int front;
	int rear;
}queue;

void Init_queue(queue *Q)
{
	Q->front=-1;
	Q->rear=-1;
}

int Empty_queue(queue Q)
{
	if(Q.front==Q.rear)
		return 1;
	else
		return 0;
}

int Full_queue(queue Q)
{
	if(Q.rear>=MAXSIZE-1)
		return 1;
	else
		return 0;
}

int QueueLength(queue Q)
{
	return Q.rear-Q.front;
}

int EnQueue(queue *Q,ElemType x)
{
	if(Full_queue(*Q)) 
		return 0;
	Q->elem[++Q->rear]=x;
	return 1;
}

int DeQueue(queue *Q,ElemType *x)
{
	if(Empty_queue(*Q))
		return 0;
	else
	{
		*x=Q->elem[++Q->front];
		return 1;
	}
}

void QueuePrint(queue Q)
{
	int i;
	printf("队列的元素为: ");
	for(i=Q.front+1;i<=Q.rear;i++)
		printf("%d ",Q.elem[i]);
	printf("\n队列的长度为:%d\n------over--------\n",QueueLength(Q));

}

void main()
{
	queue Q;
	Init_queue(&Q);
	int n,i=0;	//n是要入栈的元素的个数
	printf("请输入要入栈的元素的个数: ");
	scanf("%d",&n);
	while(n>MAXSIZE || n<1){
		printf("队列容量有限(默认为%d),%d不符合要求,请重新输入\n",MAXSIZE,n);
	}
	ElemType x;
	printf("请分别输入入栈的元素:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		EnQueue(&Q,x);
	}
	QueuePrint(Q);
	//出队操作
	for(i=1;i<n;i++)
	{
		DeQueue(&Q,&x);
		printf("第%d次出队的元素是:%d\n",i,x);
		QueuePrint(Q);
	}
}

  运行结果如图:

 二、循环队列

  在顺序队列中,当队尾指针指向了队列中的最后一个元素的位置的时候,此时若有元素入队列,就会发生“溢出”,此时假设即便有两个元素出队了,虽然有两个看位置,但是其队尾指针的位置与队首指针之间没有关系,所以还是无法腾出位置给其他元素,可以称这种现象为假溢出现象。

解决该办法有两种:

  (1)、采用平移的方法,当发生假溢出的时候将整个队列平移至存储区的首部,然后在插入元素。这样做的需要移动大量元素,因而效率是很低的。

  (2)、将顺序队列的存储区假设为一个环状的空间,如图:

程序实现如下:

#include<stdio.h>
#include<stdlib.h>
#define N 6
typedef int ElemType;

typedef struct queue
{
	ElemType *data;
	int front;
	int rear;
}queue;

void Init_queue(queue *Q)
{
	//开辟连续的存储空间作为队列的存储容量
	Q->data=(ElemType *)malloc(N*sizeof(ElemType));
	Q->front=-1;
	Q->rear=-1;
}

int Empty_queue(queue Q)
{
	if(Q.front==Q.rear)
		return 1;
	else
		return 0;
}

int Full_queue(queue Q)
{
	if((Q.rear+1)%N==Q.front)
	{
		printf("队列已满,不能再进行入队操作了啊!\n");
		return 1;
	}
	else
		return 0;
}

int Length_queue(queue Q)
{
	return (Q.rear+N-Q.front)%N;
}

int En_queue(queue *Q,ElemType x)
{
	if(Full_queue(*Q))
		return 0;
	Q->rear=(Q->rear+1)%N;
	Q->data[Q->rear]=x;
	return 1;
}

int De_queue(queue *Q,ElemType *x)
{
	if(Full_queue(*Q))
		return 0;
	Q->front=(Q->front+1)%N;
	*x=Q->data[Q->front];
}

void QueuePrint(queue Q)
{
	int i;
	printf("队列的元素为: ");
	if(Q.rear<Q.front)
		Q.rear+=N;
	for(i=Q.front+1;i<=Q.rear;i++)
		printf("%d ",Q.data[i%N]);
	printf("\n队列的长度为:%d\n------over--------\n",Length_queue(Q));
}

void main()
{
	queue Q;
	Init_queue(&Q);
	int n,i=0;	//n是要入栈的元素的个数
	printf("请输入要入栈的元素的个数: ");
	scanf("%d",&n);
	while(n>N || n<1){
		printf("队列容量有限(默认为%d),%d不符合要求,请重新输入\n",N,n);
	}
	ElemType x;
	printf("请分别输入入栈的元素:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		En_queue(&Q,x);
	}
	QueuePrint(Q);

	/*现在模拟已经输入队列四个元素,出队列两个元素后,如果是前面的顺序队列,
	则只能继续入對两个元素,若是循环队列,则可以继续入队四个元素*/
	
	//出队两个元素
	for(i=0;i<=1;i++)
	{
		De_queue(&Q,&x);
		printf("第%d次出队的元素是:%d\n",i+1,x);
		QueuePrint(Q);
	}
	//入四个元素到队列中去
	for(i=6;i<=9;i++)
		En_queue(&Q,i);
	QueuePrint(Q);

}

运行结果如图:

 三、队列的链式存储

  在一个链队列中,设定两个指针(头指针和尾指针),分别指向队列的头和尾,类比线性表,给队列链添加一个头结点,并设定头指针指向头结点。结构如图:

即队列链表的结构体如下:

typedef struct Qnode{
	ElemType data;
	struct Qnode *next;
}Qnode;
typedef struct {
	Qnode *front;
	Qnode *rear;
}

类比上面的图片可以写出如下形式的完整代码:

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct Qnode{
	ElemType data;
	struct Qnode *next;
}Qnode;
typedef struct {
	Qnode *front;
	Qnode *rear;
}LinkQueue;
void Init_queue(LinkQueue *Q)
{
	Q->front=Q->rear=(Qnode*)malloc(sizeof(Qnode));
	if(!(Q->front)){
		printf("头结点的存储空间开辟失败!\n");
		exit(0);
	}
	Q->front->next=NULL;
}

void Destory_Queue(LinkQueue *Q)
{
	while(Q->front)
	{
		Q->rear=Q->front->next;
		free(Q->front);
		Q->front=Q->rear;
	}
	printf("队列已经被销毁了!\n");
}

int Empty_queue(LinkQueue Q)
{
	if(Q.front==Q.rear)
		return 1;
	else
		return 0;
}


int QueueLength(LinkQueue Q)
{
	Qnode *p=Q.front;
	int n=0;
	while(p!=Q.rear)
	{
		n++;
		p=p->next;
	}
	return n;
}

ElemType Get_head(LinkQueue Q)
{
	if(Q.front!=Q.rear)
		return Q.front->next->data;
	else
		return 0;
}

void En_queue(LinkQueue *Q,ElemType x)
{
	Qnode *p=(Qnode*)malloc(sizeof(Qnode));
	if(!p)
	{
		printf("新节点开辟失败!\n");
		exit(0);
	}
	p->data=x;
	p->next=NULL;
	if(Q->rear==NULL)
		//头结点,起始时头结点和尾结点指向同一个元素
		Q->rear=p;
	else
	{
		Q->rear->next=p;
		Q->rear=p;
	}
}

void De_queue(LinkQueue *Q,ElemType *x)
{
	Qnode *p;
	if(Q->front!=Q->rear)
	{
		//队列非空
		p=Q->front->next;	//Q->front代表的是链表的头结点,是一个空节点
		Q->front->next=p->next;
		*x=p->data;
		if(Q->rear==p)
			Q->rear=Q->front;
		free(p);
	}

}

void Print_queue(LinkQueue Q)
{
	Qnode *p;
	printf("队列中的元素如下:\n");
	if(Q.front==NULL){
		printf("队列为空!没有元素。");
		return;
	}
	p=Q.front->next;
	while(p)
	{
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n队列的长度为:%d\n",QueueLength(Q));
}

void main()
{
	LinkQueue Q;
	Init_queue(&Q);
	int n,i;
	ElemType x,e;
	printf("请输入要入队的元素的个数:");
	scanf("%d",&n);
	printf("请分别输入要入队的元素的值:\n");
	for(i=0;i<n;i++)
	{
		scanf("%d",&x);
		En_queue(&Q,x);
	}
	Print_queue(Q);
	//元素出队
	De_queue(&Q,&x);
	Print_queue(Q);
	e=Get_head(Q);
	printf("此时出队的元素是 %d ,现在队首元素是 %d .\n",x,e);
	//销毁队列
	Destory_Queue(&Q);
}

 运行结果如图:

 

作者:一盏淡酒、醉了夕阳