队列的链表实现队列的链表实现|数据结构

本文概述

链接队列上的操作
插入操作
算法
C功能
删除中
算法
C功能
菜单驱动程序, 在链接队列上执行所有操作

由于本教程前面部分讨论的缺点, 数组实现不能用于实现队列的大型应用程序。数组实现的替代方法之一是队列的链表实现。
具有n个元素的队列的链接表示形式的存储需求为o（n）, 而操作的时间需求为o（1）。
在链接队列中, 队列的每个节点都包括两个部分, 即数据部分和链接部分。队列中的每个元素都指向其在内存中的下一个元素。
在链接的队列中, 在存储器中保持两个指针, 即前指针和后指针。前指针包含队列开始元素的地址, 而后指针包含队列最后元素的地址。
插入和删除分别在后端和前端执行。如果前后都为NULL, 则表示队列为空。
下图显示了队列的链接表示。

文章图片
链接队列上的操作可以在链接队列上实现两个基本操作。这些操作是插入和删除。
插入操作 【队列的链表实现】插入操作通过在队列末尾添加一个元素来追加队列。新元素将是队列的最后一个元素。
首先, 使用以下语句为新节点ptr分配内存。

Ptr = (struct node *) malloc (sizeof(struct node));

将这个新节点ptr插入链接队列中可能有两种情况。
在第一种情况下, 我们将元素插入一个空队列。在这种情况下, 条件front = NULL变为true。现在, 新元素将被添加为队列中的唯一元素, 并且前后指针的下一个指针都将指向NULL。

ptr -> data = http://www.srcmini.com/item; if(front == NULL){front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; }

在第二种情况下, 队列包含多个元素。条件front = NULL变为false。在这种情况下, 我们需要更新end指针后方, 以便Rear的下一个指针将指向新节点ptr。由于这是一个链接队列, 因此我们还需要使后指针指向新添加的节点ptr。我们还需要使后一个下一个指针指向NULL。

rear -> next = ptr; rear = ptr; rear-> next = NULL;

这样, 该元素将插入队列。算法和C实现如下。
算法

步骤1：为新节点PTR分配空间
步骤2：SET PTR-> DATA = http://www.srcmini.com/VAL
第3步：如果FRONT = NULL SET FRONT = REAR = PTR SET FRONT-> NEXT = REAR-> NEXT = NULL ELSE SET REAR-> NEXT = PTR SET REAR = PTR SET REAR-> NEXT = NULL [IF结束]
步骤4：结束

C功能

void insert(struct node *ptr, int item; ){ ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) {printf("\nOVERFLOW\n"); return; } else { ptr -> data = http://www.srcmini.com/item; if(front == NULL){front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; }else {rear -> next = ptr; rear = ptr; rear-> next = NULL; } }}

删除中删除操作将删除所有队列元素中首先插入的元素。首先, 我们需要检查列表是否为空。如果列表为空, 则条件front == NULL变为true, 在这种情况下, 我们只需在控制台上写下溢并退出。
否则, 我们将删除指针front指向的元素。为此, 将前指针指向的节点复制到指针ptr中。现在, 移动前指针, 指向其下一个节点, 并释放由节点ptr指向的节点。这是通过使用以下语句完成的。

ptr = front; front = front -> next; free(ptr);

算法和C函数如下。
算法

步骤1：如果FRONT = NULL, 则写“下溢”, 转到步骤5 [IF结束]
步骤2：SET PTR = FRONT
步骤3：SET FRONT = FRONT-> NEXT
步骤4：免费PTR
步骤5：结束

C功能

void delete (struct node *ptr){ if(front == NULL) {printf("\nUNDERFLOW\n"); return; } else {ptr = front; front = front -> next; free(ptr); }}

菜单驱动程序, 在链接队列上执行所有操作

#include< stdio.h> #include< stdlib.h> struct node { int data; struct node *next; }; struct node *front; struct node *rear; void insert(); void delete(); void display(); 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(){ struct node *ptr; int item; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) {printf("\nOVERFLOW\n"); return; } else { printf("\nEnter value?\n"); scanf("%d", & item); ptr -> data = http://www.srcmini.com/item; if(front == NULL){front = ptr; rear = ptr; front -> next = NULL; rear -> next = NULL; }else {rear -> next = ptr; rear = ptr; rear-> next = NULL; } }} void delete (){ struct node *ptr; if(front == NULL) {printf("\nUNDERFLOW\n"); return; } else {ptr = front; front = front -> next; free(ptr); }}void display(){ struct node *ptr; ptr = front; if(front == NULL) {printf("\nEmpty queue\n"); } else { printf("\nprinting values .....\n"); while(ptr != NULL) {printf("\n%d\n", ptr -> data); ptr = ptr -> next; } }}

输出：

***********Main Menu**********==============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter value?123***********Main Menu**********==============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?1Enter value?90***********Main Menu**********==============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?3printing values .....12390***********Main Menu**********==============================1.insert an element2.Delete an element3.Display the queue4.ExitEnter your choice ?2***********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