当前位置：首页 > ai >正文

顺序队列和链式队列

ai 2025/7/13 13:00:37

顺序队列和链式队列

根据上一篇博客我们可以明显的知道，基础结构加约束会对我们处理某些数据更加的方便，而上篇讲的是在一端维护，而我们这一次讲的是在两端维护也就是我们今天要讲的数据结构——队列

顺序队列

插入和删除分别在两端进行，就像我们进行排队一样，从队尾插入，从队头删除，如何插入这必须需要指针指向队头和队尾。

关于指针，我们要说明的，我们所说的指针不一定是语言中的指针，它是一种我们需要待插入的位置，可以是指针，也可以是下标。

一开始我们可以认为队整个都是空的

队头==队尾

//rear 队头
//front 队尾
rear==front;

在这里插入图片描述

现在我们将一个数插入进去

假设这一数组叫 int*data

我们入队操作就可以这样写

data[rear]=v1;
++rear;

然后根据队尾指针我们就可以知道如何出队操作

x1=data[front];
++front;

不知道你发现没有，这里入队和出队的操作，其实感觉动作差不多，结合我们上一篇栈的知识，我们可以明显的发现

栈的入栈和出栈的动作是相反的，而队列入队和出队的动作是相同的，那么我们在颠倒一下位置这不就是另一种写法了吗？

//入队
++rear;
data[rear]=v1;
//出队
++front;
x1=data[front];

如图

在这里插入图片描述

很好，这个明白了之后，我们在想想

当我们一共定义了八个空间，全都填满了，然后出队四个空间，请问我们这个空间满了吗？

看似满了，但是这种情况我们称之为顺序对列的假溢出。

其实没有满

在这里插入图片描述

你之前已经出队的空间其实完全可以废品回收再利用。

这种处理数据的方法我们可以叫循环队列

顺序队列和循环队列如图

在这里插入图片描述

队尾队头操作行为

rear=(rear+1)%maxSize;
front=(front+1)%maxSize;

我们可以使用求模的方法达到循环的目的

那我们队列是空还是满如何判断呢？

如果按照以前的方法

全都是

rear==front

那我们又应该如何区分呢？

我们可以用浪费空间法，浪费一个空间来进行对满的判断。

if((rear+1)%N!=front)
{data[rear]=v1;rear=(rear+1)%N;
}

在这里插入图片描述

当到后面时会先试探一下，如果满了就直接跳过。

既然已经解决了队列判满的问题，我们就可以按照原来的方法对队列进行判空操作

front=rear;

我们来定义一个队列的结构体

struct arrayQueue{element data[max];int front;int rear;
};

按照这个我们来实现

顺序队列实现

结构定义和结构操作的声明

#define QUEUE_SIZE 5typedef struct {Element data[QUEUE_SIZE];int front;int rear;
}ArrayQueue ;void initArrayQueue(ArrayQueue *Q);int enQueue(ArrayQueue *Q,Element e);int deQueue(ArrayQueue *Q,Element *e);

结构操作的实现

void initArrayQueue(ArrayQueue *Q) {Q->front=Q->rear=0;
}int enQueue(ArrayQueue *Q, Element e) {if ((Q->rear+1)%QUEUE_SIZE==Q->front) {fprintf(stderr,"Queue is full\n");return -1;}Q->rear=(Q->rear+1)%QUEUE_SIZE;Q->data[Q->rear]=e;return 0;
}int deQueue(ArrayQueue *Q, Element *e) {if (Q->rear==Q->front) {fprintf(stderr,"Queue is empty\n");return -1;}Q->front=(Q->front+1)%QUEUE_SIZE;*e=Q->data[Q->front];return 0;
}

测试

void text1() {ArrayQueue ate;initArrayQueue(&ate);for(int i = 0; i < 4; i++) {enQueue(&ate,i+100);}enQueue(&ate,1);printf("Dequeue ");Element m;while (deQueue(&ate,&m)!=-1) {printf("%d\t ", m);}printf("\n");
}

结果

在这里插入图片描述

说完顺序队列我们再来说一说链式队列

链式队列

对于有些情况我们是不知道数据有多少的，这时候就需要我们用链式队列去解决问题。

当我们插入一个元素我们应该在一个元素的后面去插入。

在这里插入图片描述

那有人就要问了，为啥不能像栈一样从前面开始插入？

你可以仔细看看，从前面插入的话我们出队又该如何操作呢？

自然是操作不了，所以我们还是向后操作

其实说实在的就是尾插法

rear->next=new_node;
rear=new_node;

那么删除自然也就知道了

tmp=front;
front=temp->next;
free(tmp)

链式队列的实现

结构定义和结构操作的声明

typedef struct _node {Element data;struct _node *next;}QueNode;
//队头
typedef struct {QueNode *front;QueNode *rear;int cnt;const char*name;
}LinkQueue;//初始化
LinkQueue* createLinkQueue(const char* name);
void deleteLinkQueue(LinkQueue* queue);int EnQueue(LinkQueue* queue, Element e);
int EeQueue(LinkQueue* queue, Element* e);

结构操作实现


#include "LinkQueue.h"#include <stdio.h>
#include <stdlib.h>LinkQueue * createLinkQueue(const char*name) {LinkQueue* queue = (LinkQueue*)malloc(sizeof(LinkQueue));if (queue == NULL) {printf("Memory allocation failed\n");return NULL;}queue->cnt=0;queue->name=name;queue->front=queue->rear=NULL;return queue;}void deleteLinkQueue(LinkQueue *queue) {if (queue) {QueNode*node;while (queue->front) {node = queue->front;queue->front=node->next;free(node);queue->cnt--;}printf("queue deleted %d\n",queue->cnt);free(queue);}
}//入队
int EnQueue(LinkQueue *queue, Element e) {QueNode*node = (QueNode*)malloc(sizeof(QueNode));if (node == NULL) {printf("Memory newnode failed\n");return -1;}node->data = e;node->next = NULL;if (queue->rear) {queue->rear->next = node;queue->rear = node;}else {queue->front=queue->rear = node;}queue->cnt++;return 0;
}int EeQueue(LinkQueue *queue, Element *e) {if (queue->rear == NULL) {printf("Queue is empty\n");return -1;}*e=queue->front->data;QueNode*tmp=queue->front;queue->front=tmp->next;free(tmp);queue->cnt--;if (queue->front == NULL) {queue->rear = NULL;}return 0;
}

测试

void text2() {LinkQueue*queue=createLinkQueue("ste1");if (queue==NULL) {return;}for(int i = 0; i < 4; i++) {EnQueue(queue,i+100);}Element s1;printf("%s que %dshow\n",queue->name,queue->cnt);while(EeQueue(queue,&s1)!=-1) {printf("\t%d",s1);}printf("\n");deleteLinkQueue(queue);
f("\t%d",s1);}printf("\n");deleteLinkQueue(queue);
}