【数据结构与算法学习笔记三】队列

1、概念与理解

队列在实际生活中是经常遇到的,比如上班高峰期地铁站限流。回归到本质,队列其实也是一种运算受限制的线性表,它的特点是,只可以在对头删除元素,在队尾插入元素,所以这是一种先进先出的数据结构。它和栈不一样,栈是只有一端可以执行插入删除的操作,因此定义栈的运算的时候,只要一个标记能够标志顶点元素就可以。但是在队列中,它是有两端的,并且两端各执行不一样的操作,所以定义一个数据结构来表达队列相对比较复杂一点。

2、队列的数据结构定义

队列是一种受限制的线性表,因此也拥有线性表的特点。根据存储方式的不同,队列可以分为顺序队列和链式队列,根据不同的存储方式,定义的结构也不同。

2.1 、顺序队列的数据结构定义

既然是顺序队列,那么必然包含一个数组成员。前面提到队列含有两端,并且各端对应的操作不相同,因此很有必要使用两个标记来标志这两端。一般我们把执行删除操作的一端称为对头,执行插入操作的一端称为队尾。下面的数据结构均用C语言语法定义,随后会使用实际例子实现基本运算。
typedef struct queue
{
dataType data[MAXSIZE];
int front,rear;
}LQueue
对于顺序队列我们还需要考虑一个问题,假如我们现在有一个容量为5的名称是a的队列,一开始给队列中a[0]-a[4]赋值0,1,2,3,4。然后移除对头的元素0,1。此时,队列还剩2,3,4,空余两个位置。此时如果我们在队尾插入元素,会发现,队列已经满了。但是明明有两个空余的位置对吧?我们可以将队列想象成首位连接的一个圆圈,我们称为循环队列。在确定插入的元素应该处于哪个位置的时候,使用(rear+1)%5求出模,就是新插入的元素应该处于的位置。
好了,上面的一个问题解决了。现在考虑一下,队列什么时候是空?即对头等于队尾的时候,这里是front==rear表示队列为空。再考虑一下,队列什么时候为满,没错也是front==rear。好了,当front==rear的时候,究竟是空表还是满表呢。思路如下:
假如现在进行插入操作(n代表队列的容量):
rear=(rear+1)%n,front不变。
假如现在进行删除操作:
front=(front+1)%n,rea不变。
发现了没有,其实如果我们执行的是插入操作遇到rear==front的情况,说明对满。执行删除操作的时候则是对空。

2.2、链式队列的数据结构定义

链式队列和顺序队列的不同之处在于,它的数组长度是动态增长,所以它并没有对满的忧虑。首先需要一个节点,表示每个队列元素的结构,其次我们还需要一个数据结构来定义指向对头和队尾的节点。如下:
typedef struct node
{
dataType data;
struct node *next;
}PNode

typedef struct queue
{
PNode *read,*front;
}PQueue

其中node是队列的节点,queue表示整个队列,含有对头和队尾元素。

3、队列的基本运算

①、初始化队列:init_queue
②、判断对空:isEmpty_queue
③、对头元素出队:delete_element
④、队尾添加元素:insert_element
⑤、读取队头元素:get_element
上述只是基于队列的基本运算,实际应用中应该根据队列的特点以及需求共同定义运算。

4、C语言实现链式队列的基本运算

/*
实现链式队列的基本运算
*/

#include <stdio.h>
#include <stdlib.h>

/*
声明链式队列的节点元素
*/
typedef struct node
{
int data;//存放数据
struct node *next;//连接下一节点
}Node;

/*
由于队列需要知道队头和队尾元素,所以声明一个队列的基本结构
*/

typedef struct queue
{
Node *front;//指向对头元素
Node *rear;//指向队尾元素
}Queue;

/*
声明基本运算
*/

Queue* init_queue();//初始化队列
int isEmpty_queue(Queue *pQueue);//判断对空
void insert_element(Queue *pQueue, int data);//向队尾插入元素
void delete_element(Queue *pQueue);//移除对头元素
int get_element(Queue* pQueue);//获取对头元素

int main(void)
{
Queue *queue = init_queue();
for (int i = 1; i <= 5; i++)
{
insert_element(queue, i);
}
printf(“队头元素:%d\n”, get_element(queue));
delete_element(queue);
printf(“删除1之后队头元素:%d\n”, get_element(queue));

system(“pause”);
return 0;
}

/*
初始化队列
*/
Queue* init_queue()
{
Queue *pQueue = (Queue *)malloc(sizeof(Queue));
//先定义一个表头,然后让队列都指向它,这样就把队列和队列的元素连接起来了。
Node *pHeader = (Node *)malloc(sizeof(Node));
pHeader->data =-1;
pHeader->next = NULL;
//将对头和队尾都指向表头元素。
pQueue->front = pHeader;
pQueue->rear = pHeader;
return pQueue;
}

/*
判断对空
*/
int isEmpty_queue(Queue *pQueue)
{
//因为链式表是动态增长的,长度是没有限制的,所以当对头等于队尾,一定是空队列。
if (pQueue->front == pQueue->rear)
return 1;
return 0;
}

/*
在队尾插入元素
*/
void insert_element(Queue *pQueue, int data)
{
Node *pNode = (Node *)malloc(sizeof(Node));
pNode->data = data;
pNode->next = NULL;
//先获取当前的队尾元素
Node *pRear = pQueue->rear;
//此队尾元素是即将插入队尾元素的下一个元素
pRear->next = pNode;
//将当前结点设为队尾元素
pQueue->rear = pNode;
}

/*
移除队头元素
对头用于指向头节点
*/
void delete_element(Queue *pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{
printf(“对空/n”);
}
else
{
//获取当前队列的头节点
Node *pHeader = pQueue->front;
//获取当前队列的头节点的下一节点元素,即队头
Node *pFront = pHeader->next;
//获取对头的下一节点,作为新的对头
Node *pNewFront = pFront->next;

pHeader->next=pNewFront;//将新的对头元素赋值给头节点。
free(pFront);

//如果队列只有一个元素,则删除之后,队尾指针则指向了不确定的值,所以应该重新将队尾指向头节点
if (pNewFront == NULL)//说明是空的队列
{
pQueue->rear = pHeader;
}
}
}

/*
获取队头元素的值
*/
int get_element(Queue* pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{
return -1;
}
Node *pFront = pQueue->front->next;
return pFront->data;
}

注释已经说明的很清楚了。我们很容易犯得一个错误的思维定势是,总是认为next是从队尾指向队头的方向。在队列中,其实是队头指向队尾的方向。
运行效果:

发表评论

电子邮件地址不会被公开。 必填项已用*标注