使用链表实现队列

2025年4月20日 | 阅读5分钟

由于本教程前一节讨论的缺点，对于实现队列的大规模应用，数组实现无法使用。数组实现的一种替代方法是链表实现队列。

具有 n 个元素的链式表示队列的存储需求为 o(n)，而操作的时间需求为 o(1)。

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

在链式队列中，内存中维护着两个指针，即 front 指针和 rear 指针。front 指针包含队列起始元素的地址，而 rear 指针包含队列最后一个元素的地址。

插入和删除分别在尾部和头部执行。如果 front 和 rear 都为 NULL，则表示队列为空。

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

链式队列上的操作

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

插入操作

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

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

将此新节点 ptr 插入链式队列可能存在两种情况。

在第一种情况下，我们将元素插入空队列。在这种情况下，条件 front = NULL 为真。现在，新元素将作为队列的唯一元素添加，front 和 rear 指针的 next 指针都将指向 NULL。

ptr -> data = item;
		if(front == NULL)
		{
			front = ptr;
			rear = ptr;  
			front -> next = NULL;
			rear -> next = NULL;
		}

第二种情况是队列包含多个元素。条件 front = NULL 为假。在这种情况下，我们需要更新尾部指针 rear，以便 rear 的 next 指针指向新节点 ptr。由于这是一个链式队列，因此我们还需要将 rear 指针指向新添加的节点 ptr。我们还需要将 rear 的 next 指针设置为指向 NULL。

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

这样，元素就被插入到队列中了。算法和 C 实现如下。

算法

步骤 1： 为新节点 PTR 分配空间
步骤 2： 设置 PTR -> DATA = VAL
步骤 3： 如果 FRONT = NULL
设置 FRONT = REAR = PTR
设置 FRONT -> NEXT = REAR -> NEXT = NULL
否则
设置 REAR -> NEXT = PTR
设置 REAR = PTR
设置 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 为真，在这种情况下，我们只需在控制台上显示“underflow”并退出。

否则，我们将删除 front 指针指向的元素。为此，将 front 指针指向的节点复制到 ptr 指针。现在，移动 front 指针，使其指向下一个节点，并释放 ptr 指针指向的节点。这是使用以下语句完成的。

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

算法和 C 函数如下。

算法

步骤 1： 如果 FRONT = NULL
显示“Underflow”
转到步骤 5
[IF 结束]
步骤 2： 设置 PTR = FRONT
步骤 3： 设置 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

下一个主题循环队列

我们提供所有技术（如 Java 教程、Android、Java 框架）的教程和面试问题

联系信息

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

hr@tpointtech.com

+91-9599086977

关注我们

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

使用链表实现队列

链式队列上的操作

插入操作

算法

C 函数

删除

算法

C 函数

实现链式队列所有操作的菜单驱动程序

相关帖子

循环队列

数据结构中队列的应用

优先队列

队列类型

双端队列

数据结构中的队列

使用数组实现队列

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器