Question

队列可以用链表实现吗

Answer 1

队列也可以用顺序表和链表的结构实现，但是由于需要进行一端插入一端删除的操作，如果使用数组的结构，在顺序表头上出数据，需要移动n-1个数据，时间复杂度为O(n)，效率会比较低。因此使用链表的结构实现更优一些。

链表对头部进行操作时间复杂度为O(1)，对尾部操作则需要进行‘找尾’操作遍历链表，时间复杂度为O(n)。那么如何在队列实现中提高效率呢？下面我们介绍队列实现的结构。

队列的链表表现形式：

第一种定义方法：

struct Node{ int data; //数据域 Node *front; //头 Node *rear; //尾 Node *next; //下一个}。

第二种定义方法：

struct Node{ int data; //数据域 Node *next; //下一个};struct List{ Node *front; //尾 Node *rear; //头}。