队列的链表实现

本文概述

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

由于本教程前面部分讨论的缺点, 数组实现不能用于实现队列的大型应用程序。数组实现的替代方法之一是队列的链表实现。

具有n个元素的队列的链接表示形式的存储需求为o（n）, 而操作的时间需求为o（1）。

在链接队列中, 队列的每个节点都包括两个部分, 即数据部分和链接部分。队列中的每个元素都指向其在内存中的下一个元素。

在链接的队列中, 在存储器中保持两个指针, 即前指针和后指针。前指针包含队列开始元素的地址, 而后指针包含队列最后元素的地址。

插入和删除分别在后端和前端执行。如果前后都为NULL, 则表示队列为空。

下图显示了队列的链接表示。

链接队列上的操作

可以在链接队列上实现两个基本操作。这些操作是插入和删除。

插入操作

插入操作通过在队列末尾添加一个元素来追加队列。新元素将是队列的最后一个元素。

首先, 使用以下语句为新节点ptr分配内存。

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

将这个新节点ptr插入链接队列中可能有两种情况。

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

ptr -> data = 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 = 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 = 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 = 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 element
2.Delete an element
3.Display the queue
4.Exit

Enter your choice ?1

Enter value?
123

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

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

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

Enter your choice ?1

Enter value?
90

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

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

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

Enter your choice ?3

printing values .....

123

90

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

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

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

Enter your choice ?2

***********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