队列的数组表示队列的数组表示|数据结构

本文概述

在队列中插入任何元素的算法
算法
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 5void 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 element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element123Value inserted *************Main Menu**************==============================================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter the element90Value inserted *************Main Menu**************===================================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?2value deleted *************Main Menu**************==============================================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?3printing values .....90*************Main Menu**************==============================================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?4

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

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

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

确定数组大小

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