当前位置: 首页> 教育> 高考 > 专业团队为您服务_网站建设和运营哪家公司好_自动外链网址_洛阳seo博客

专业团队为您服务_网站建设和运营哪家公司好_自动外链网址_洛阳seo博客

时间:2025/7/10 17:25:48来源:https://blog.csdn.net/m0_74859128/article/details/142929373 浏览次数:0次
专业团队为您服务_网站建设和运营哪家公司好_自动外链网址_洛阳seo博客

1队列的定义和操作

1.1队列的定义和特性

一 队列的定义

队列是一种特殊的线性表,它只允许在表的一端进行插入操作,而在另一端进行删除操作。进行插入操作的一端称为队尾(rear),进行删除操作的一端称为队头(front)。

二 队列的特性

  1. 先进先出(FIFO,First In First Out)
    • 就像在生活中的排队一样,最先进入队列的元素将最先被取出。例如,在银行排队办理业务,先来的客户先得到服务。
  2. 操作受限
    • 插入操作只能在队尾进行,删除操作只能在队头进行。这保证了队列的有序性和特定的操作方式。
  3. 动态性
    • 队列的长度可以根据实际需求动态变化。可以不断地向队列中插入元素,也可以从队列中删除元素。

三、队列的应用场景

队列广泛应用于各种场景,如:

  • 任务调度:操作系统中的任务队列。
  • 广度优先搜索(BFS):图搜索算法。
  • 消息传递:多线程编程中的消息队列。
  • 打印任务:打印机中的打印任务队列

12队列的基本操作

1. 入队(Enqueue)

定义:将一个元素添加到队列的尾部。

操作步骤

  • 检查队列是否已满(对于固定容量的队列)。
  • 如果队列不满,则将新元素插入到队列的尾部,并更新尾指针。

示例代码(C语言):

void enqueue(Queue *q, int value) {if (isFull(q)) {printf("队列已满,无法入队!\n");return;}if (isEmpty(q)) {q->front = 0;  // 如果队列为空,初始化 front}q->rear = (q->rear + 1) % MAX_SIZE;  // 循环队列的尾指针更新q->data[q->rear] = value;  // 将新元素加入队列
}

2. 出队(Dequeue)

定义:从队列的头部移除一个元素,并返回该元素。

操作步骤

  • 检查队列是否为空。
  • 如果队列不为空,则移除并返回队首元素,更新头指针。
  • 如果出队后队列为空,将头和尾指针重置。

示例代码(C语言):

int dequeue(Queue *q) {if (isEmpty(q)) {printf("队列为空,无法出队!\n");return -1;  // 或者返回其他标志}int value = q->data[q->front];  // 获取队首元素if (q->front == q->rear) {// 如果出队后队列为空q->front = -1;q->rear = -1;} else {q->front = (q->front + 1) % MAX_SIZE;  // 循环队列的头指针更新}return value;  // 返回出队的元素
}

3. 查看队首元素(Front)

定义:获取队列头部的元素,但不移除它。

操作步骤

  • 检查队列是否为空,为空则无法获取队首元素。
  • 如果不为空,返回队首元素的值。

示例代码(C语言):

int front(Queue *q) {if (isEmpty(q)) {printf("队列为空,无法获取队首元素!\n");return -1;  // 或者返回其他标志}return q->data[q->front];  // 返回队首元素
}

4. 查看队尾元素(Rear)

定义:获取队列尾部的元素,但不移除它。

操作步骤

  • 检查队列是否为空。
  • 如果不为空,返回队尾元素的值。

示例代码(C语言):

int rear(Queue *q) {if (isEmpty(q)) {printf("队列为空,无法获取队尾元素!\n");return -1;  // 或者返回其他标志}return q->data[q->rear];  // 返回队尾元素
}

5. 判断队列是否为空(IsEmpty)

定义:检查队列是否为空。

操作步骤

  • 比较队首指针和尾指针,如果相等且队首指针不为 -1,则队列为空。

示例代码(C语言):

int isEmpty(Queue *q) {return q->front == -1;  // 返回队列是否为空的布尔值
}

6. 判断队列是否已满(IsFull)

定义:检查队列是否已满(适用于固定容量的队列)。

操作步骤

  • 判断尾指针是否在队首指针的前一个位置。

示例代码(C语言):

int isFull(Queue *q) {return (q->rear + 1) % MAX_SIZE == q->front;  // 返回队列是否满的布尔值
}

7. 获取队列大小(Size)

定义:获取队列中当前元素的数量。

操作步骤

  • 根据队首和队尾的指针计算元素数量。

示例代码(C语言):

int size(Queue *q) {if (isEmpty(q)) {return 0;  // 如果队列为空,返回0}return (q->rear - q->front + MAX_SIZE) % MAX_SIZE + 1;  // 计算队列的当前大小
}

2队列的存储与实现

2.1顺序队列

一顺序队列的定义和运算

定义

顺序队列是队列的顺序存储结构,用一个向量空间(即数组)来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的,因此需要设置两个指针front和rear,分别指示队头元素和队尾元素在向量空间中的位置。

  • 队头指针(front):指向队头元素的位置。
  • 队尾指针(rear):指向队尾元素的下一个位置,即新元素应该插入的位置。

初始化时,front和rear的初值通常都设置为0。

顺序队列结构体定义

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 队列最大容量typedef struct {int data[MAX_SIZE];  // 队列存储数组int front;           // 队列头指针int rear;            // 队列尾指针
} SequentialQueue;

1. 初始化队列

void initQueue(SequentialQueue *q) {q->front = 0;  // 指向队列的第一个元素q->rear = 0;   // 队尾指向队列已存放的元素位置
}

2. 判断队列是否为空

int isEmpty(SequentialQueue *q) {return q->front == q->rear;  // 如果 front 和 rear 指针相等,则队列为空
}

3. 判断队列是否已满

int isFull(SequentialQueue *q) {return (q->rear + 1) % MAX_SIZE == q->front;  // 判断是否满
}

4. 入队操作(Enqueue)

void enqueue(SequentialQueue *q, int value) {if (isFull(q)) {printf("队列已满,无法入队!\n");return;}if (isEmpty(q)) {q->front = 0;  // 当队列为空时,初始化 front}q->rear++;  // 更新队尾指针q->data[q->rear] = value;  // 在尾部插入新元素
}

5. 出队操作(Dequeue)

int dequeue(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空,无法出队!\n");return -1;  // 返回特殊值表示队列为空}int value = q->data[q->front];  // 获取队头元素// 检查出队后是否需要重置队列if (q->front == q->rear) {// 如果出队后队列为空,需要重置队列q->front = -1;q->rear = -1;} else {// 更新队首指针q->front++;}return value;  // 返回出队的元素
}

6. 查看队首元素(Front)

int front(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空,无法获取队首元素!\n");return -1;}return q->data[q->front];  // 返回队首元素
}

7. 查看队尾元素(Rear)

int rear(SequentialQueue *q) {if (isEmpty(q)) {printf("队列为空,无法获取队尾元素!\n");return -1;  // 返回特殊值表示队列为空}return q->data[q->rear];  // 返回队尾元素
}

8. 获取队列大小(Size)

int size(SequentialQueue *q) {if (isEmpty(q)) {return 0;  // 当队列为空则返回大小为0}return q->rear - q->front + 1;  // 计算当前大小
}

2.2循环顺序队列

循环顺序队列,简称循环队列,是一种特殊的顺序队列,其特点在于将队列的存储空间视为一个逻辑上的环状空间,从而实现了队列的循环利用。以下是关于循环顺序队列的详细介绍:

定义与结构

循环队列是将顺序队列的首尾相连,形成一个逻辑上的环状空间。在循环队列中,当存储空间的最后一个位置已被使用而再要进行入队操作时,如果存储空间的第一个位置空闲,那么就可以将新元素插入到第一个位置,此时将存储空间的第一个位置视为队尾。

循环队列通常使用一个数组来存储队列元素,并设置两个指针front和rear来分别指示队头和队尾的位置。front指向队头元素的位置,而rear指向队尾元素的下一个位置(即新元素应该插入的位置)。

1. 循环顺序队列的结构体定义
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 队列最大容量typedef struct {int data[MAX_SIZE];  // 队列存储数组int front;           // 队列头指针int rear;            // 队列尾指针
} CircularQueue;

2. 初始化队列
void initQueue(CircularQueue *q) {q->front = 0;  // 队列头指针q->rear = 0;   // 队列尾指针
}

3. 判断队列是否为空
int isEmpty(CircularQueue *q) {return q->front == q->rear;  // 如果 front 和 rear 指针相等,则队列为空
}

4. 判断队列是否已满

在判断队列是否已满时,使用 (q->rear + 1) % MAX_SIZE == q->front 条件来判断队列是否已满。

int isFull(CircularQueue *q) {return (q->rear + 1) % MAX_SIZE == q->front;  // 判断是否满
}

  • (q->rear + 1) % MAX_SIZE:计算 rear 的下一个位置。如果 rear 现在在数组的末尾(MAX_SIZE - 1),则 (q->rear + 1) % MAX_SIZE 会回绕到数组的开始(即 0)。
  • == q->front:如果计算出的下一个 rear 位置与 front 位置相同,则表示队列已满,没有空余位置可以插入新元素。

 

5. 入队操作(Enqueue)

在入队操作中,rear 指针需要移动到下一个位置以存储新的元素。由于队列是循环的,当 rear 达到数组的末尾时,它需要回绕到数组的开头。

void enqueue(CircularQueue *q, int value) {if (isFull(q)) {printf("队列已满,无法入队!\n");return;}q->data[q->rear] = value;  // 在尾部插入新元素q->rear = (q->rear + 1) % MAX_SIZE;  // 更新尾指针,循环使用
}

  • q->data[q->rear] = value;:将新元素插入到当前 rear 指针所指向的位置。
  • q->rear = (q->rear + 1) % MAX_SIZE;:计算 rear 的下一个位置。如果 rear 已经到达数组的末尾(MAX_SIZE - 1),则下一次 rear 会回绕到数组的开始(即 rear = 0)。
6. 出队操作(Dequeue)

在出队操作中,front 指针也需要移动到下一个位置以移除当前元素。由于队列是循环的,当 front 达到数组的末尾时,它需要回绕到数组的开头。

int dequeue(CircularQueue *q) {if (isEmpty(q)) {printf("队列为空,无法出队!\n");return -1;  // 返回特殊值表示队列为空}int value = q->data[q->front];  // 获取队头元素q->front = (q->front + 1) % MAX_SIZE;  // 循环更新队头指针return value;  // 返回出队的元素
}

  • q->data[q->front];:获取当前 front 指针所指向的元素,即队头元素。
  • q->front = (q->front + 1) % MAX_SIZE;:计算 front 的下一个位置。如果 front 已经到达数组的末尾(MAX_SIZE - 1),则下一次 front 会回绕到数组的开始(即 front = 0)。

例子

假设 MAX_SIZE 为 5,当前队列的状态如下:

  • front:指向 0
  • rear:指向 4(即数组的最后一个位置)。

现在我们尝试进行一次入队操作:

  • 插入元素前的 rear4
  • 插入元素后的 rear(4 + 1) % 5 = 0(回绕到数组的开始)

此时,rear 指向下一个要插入的位置 0,如果再次判断队列是否已满:

(0 + 1) % 5 == 0 // 结果为 1 == 0 (假)

结果为假,表示队列未满。

如果 front 也移动到 1,并且 rear 仍然是 0,那么再次尝试判断满的条件:

(0 + 1) % 5 == 1 // 结果为 1 == 1 (真)

这时结果为真,表示队列已满。

2.3链式队列

链式队列的基本结构包括:

  1. 节点(Node):链表中的每个元素称为节点,包含两个部分:

    • 数据域(data):存储节点中的数据。
    • 指针域(next):指向下一个节点的指针。
  2. 队列(Queue):队列包含两个指针:

    • front:指向队列头部的指针。
    • rear:指向队列尾部的指针。
链式队列的操作

链式队列的基本操作包括:

  1. 初始化队列:初始化队列时,front 和 rear 都指向 NULL,表示队列为空。
  2. 入队(Enqueue):在队列尾部插入一个新节点。
  3. 出队(Dequeue):从队列头部移除一个节点。
  4. 判断队列是否为空:检查 front 是否指向 NULL
  5. 获取队列头部元素:获取队列头部的值,但不移除节点。

下面是链式队列的实现代码示例:

#include <stdio.h>
#include <stdlib.h>// 定义节点结构体
typedef struct Node {int data;           // 数据struct Node* next;  // 指向下一个节点的指针
} Node;// 定义队列结构体
typedef struct Queue {Node* front;  // 队列头部指针Node* rear;   // 队列尾部指针
} Queue;// 初始化队列
void initQueue(Queue* q) {q->front = NULL;q->rear = NULL;
}// 判断队列是否为空
int isEmpty(Queue* q) {return q->front == NULL;
}// 入队操作
void enqueue(Queue* q, int value) {// 创建新节点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败!\n");return;}newNode->data = value;newNode->next = NULL;// 如果是空队列,front 和 rear 都指向新节点if (isEmpty(q)) {q->front = newNode;q->rear = newNode;} else {// 否则,将新节点添加到 rear 后面,并更新 rearq->rear->next = newNode;q->rear = newNode;}
}// 出队操作
int dequeue(Queue* q) {if (isEmpty(q)) {printf("队列为空,无法出队!\n");return -1;  // 返回特殊值表示队列为空}// 获取队头元素int value = q->front->data;Node* temp = q->front;  // 临时指针指向队头节点// 更新 frontq->front = q->front->next;// 如果出队后队列为空,rear 也要更新if (q->front == NULL) {q->rear = NULL;}// 释放原队头节点的内存free(temp);return value;  // 返回出队的元素
}// 获取队列头部元素
int getFront(Queue* q) {if (isEmpty(q)) {printf("队列为空!\n");return -1;  // 返回特殊值表示队列为空}return q->front->data;
}// 主程序
int main() {Queue q;initQueue(&q);// 入队操作示例enqueue(&q, 10);enqueue(&q, 20);enqueue(&q, 30);// 输出当前出队元素printf("出队元素: %d\n", dequeue(&q));  // 输出: 10printf("出队元素: %d\n", dequeue(&q));  // 输出: 20// 新的入队操作printf("入队元素: 40\n");enqueue(&q, 40);// 输出队列头部元素printf("队列头部元素: %d\n", getFront(&q));  // 输出: 30// 测试更多的入队和出队操作printf("入队元素: 50\n");enqueue(&q, 50);printf("入队元素: 60\n");enqueue(&q, 60);// 输出当前出队元素printf("出队元素: %d\n", dequeue(&q));  // 输出: 30printf("出队元素: %d\n", dequeue(&q));  // 输出: 40printf("出队元素: %d\n", dequeue(&q));  // 输出: 50printf("出队元素: %d\n", dequeue(&q));  // 输出: 60// 尝试出队时队列为空printf("出队元素: %d\n", dequeue(&q));  // 输出: 队列为空,无法出队!return 0;
}

关键字:专业团队为您服务_网站建设和运营哪家公司好_自动外链网址_洛阳seo博客

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: