队列的数组表示

本文概述

• 在队列中插入任何元素的算法
• 算法
• C功能
• 从队列中删除元素的算法
• 算法
• C功能
• 菜单驱动程序, 使用数组实现队列
• 数组实现的缺点

我们可以使用线性数组轻松表示队列。在每个队列中都有两个变量, 即前和后。前后变量指向在队列中执行插入和删除操作的位置。最初, front和queue的值为-1, 表示一个空队列。下图显示了包含5个元素以及前后值的队列的数组表示形式。

上图显示了构成英语单词“ HELLO”的字符队列。由于直到现在还没有在队列中执行删除操作, 因此front的值保持为-1。但是, 每次在队列中执行插入操作时, 后方的值将增加一。将元素插入上图所示的队列后, 该队列将如下所示。 Rear的值将变为5, 而front的值保持不变。

删除元素后, front的值将从-1增加到0。但是, 队列看起来像以下。

在队列中插入任何元素的算法

通过比较后方与最大值-1来检查队列是否已满。如果是, 则返回溢出错误。

如果要将该项目作为列表中的第一个元素插入, 则在这种情况下, 将front和tail的值设置为0, 然后将元素插入后端。

否则, 请继续增加Rear的值, 并将每个元素逐一插入, 以Rear为索引。

算法

• 步骤1：如果REAR = MAX-1写溢出转到步骤[IF结束]
• 步骤2：如果FRONT = -1和REAR = -1, 则SET FRONT = REAR = 0 ELSE SET REAR = REAR + 1 [IF结束]
• 步骤3：设置QUEUE [REAR] = NUM
• 步骤4：退出

C功能

void insert (int queue[], int max, int front, int rear, int item) 
{
	if (rear + 1 == max)
	{
		printf("overflow");
	}
	else
	{
		if(front == -1 && rear == -1)
		{
			front = 0;
			rear = 0;
		}
		else
		{
			rear = rear + 1; 
		}
		queue[rear]=item;
	}
}

从队列中删除元素的算法

如果front的值是-1或front的值大于Rear, 则写一个下溢消息并退出。

否则, 请继续增加front的值, 并每次返回存储在队列前端的项目。

算法

• 第1步：如果FRONT = -1或FRONT> REAR写入下流否则SET VAL = QUEUE [FRONT] SET FRONT = FRONT + 1 [IF结束]
• 步骤2：退出

C功能

int delete (int queue[], int max, int front, int rear)
{
	int y; 
	if (front == -1 || front > rear) 
 
	{
		printf("underflow");
	}
	else 
	{
		y = queue[front];
		if(front == rear)
		{
			front = rear = -1;
			else 
			front = front + 1; 
		
		}
		return y;
	}
}

菜单驱动程序, 使用数组实现队列

#include<stdio.h> 
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
	int choice; 
	while(choice != 4) 
	{	
		printf("\n*************************Main Menu*****************************\n");
		printf("\n=================================================================\n");
		printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
		printf("\nEnter your choice ?");
		scanf("%d", &choice);
		switch(choice)
		{
			case 1:
			insert();
			break;
			case 2:
			delete();
			break;
			case 3:
			display();
			break;
			case 4:
			exit(0);
			break;
			default: 
			printf("\nEnter valid choice??\n");
		}
	}
}
void insert()
{
	int item;
	printf("\nEnter the element\n");
	scanf("\n%d", &item);	
	if(rear == maxsize-1)
	{
		printf("\nOVERFLOW\n");
		return;
	}
	if(front == -1 && rear == -1)
	{
		front = 0;
		rear = 0;
	}
	else 
	{
		rear = rear+1;
	}
	queue[rear] = item;
	printf("\nValue inserted ");
	
}
void delete()
{
	int item; 
	if (front == -1 || front > rear)
	{
		printf("\nUNDERFLOW\n");
		return;
			
	}
	else
	{
		item = queue[front];
		if(front == rear)
		{
			front = -1;
			rear = -1 ;
		}
		else 
		{
			front = front + 1;
		}
		printf("\nvalue deleted ");
	}
	
	
}
	
void display()
{
	int i;
	if(rear == -1)
	{
		printf("\nEmpty queue\n");
	}
	else
	{	printf("\nprinting values .....\n");
		for(i=front;i<=rear;i++)
		{
			printf("\n%d\n", queue[i]);
		}	
	}
}

输出：

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
123

Value inserted 

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter the element
90

Value inserted 

*************Main Menu**************

===================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?2

value deleted 

*************Main Menu**************
==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?3

printing values .....

90

*************Main Menu**************

==============================================

1.insert an element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?4

数组实现的缺点

尽管创建队列的技术很容易, 但是使用此技术实现队列存在一些缺点。

• 内存浪费：用于存储队列元素的数组空间永远不能再用于存储该队列的元素, 因为这些元素只能插入前端, 并且front的值可能很高, 以至于, 之前的所有空间都无法填补。

上图显示了如何在队列的数组表示中浪费内存空间。在上图中, 显示了具有3个元素的大小为10的队列。 front变量的值为5, 因此, 我们无法在front位置之前将值重新插入到已删除元素的位置。数组的大量空间被浪费了, 将来无法使用（用于此队列）。

• 确定数组大小

数组实现最常见的问题是需要提前声明的数组大小。由于可以根据问题在运行时扩展队列, 因此, 数组大小的扩展是一个耗时的过程, 并且由于发生了许多重新分配, 因此几乎不可能在运行时执行。由于这个原因, 我们可以声明足够大的数组, 以便我们可以存储尽可能多的队列元素, 但是此声明的主要问题是, 绝大部分数组插槽（几乎一半）都无法重用。它将再次导致内存浪费。