队列的数组实现

简介: 队列的数组实现

像栈一样,队列也是表。使用队列时插入和删除分别在队列的两端进行

队列是一种先进先出(FIFO)的数据结构

队列的链表实现方式太过于简单,本文介绍数组的实现方式

实现思路:

1.维护两个索引,front代表队列的首部,rear代表队列的尾部

2.入队时,rear + 1,队列当前大小 + 1

3.出队时,front + 1, 队列当前大小 + 1

4.通过队列当前大小判断队列是否已满,来保证入队时新元素不会覆盖旧元素

5.将front和rear的递增后的索引对队列总大小取模,保证不会下标越界,同时实现循环数组

代码实现

1.队列结构体

typedef struct {
    int *data; // 数组
    int front; // 队列首部索引
    int rear; // 队列尾部索引
    int size; // 队列当前大小
    int capacity; // 队列总大小
} queue;

2.创建队列

void init_queue(queue *queue) {
    queue->data = (int *)malloc(INITIAL_CAPACITY * sizeof(int));
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = INITIAL_CAPACITY;
}

3.入队

int enqueue(queue *queue, int value) {
    if (queue->size == queue->capacity) {
        expand(queue);
    }
    queue->rear = (queue->rear + 1) % queue->capacity; // 循环数组
    queue->data[queue->rear] = value;
    queue->size++;
}

4.出队

int enqueue(queue *queue, int value) {
    if (queue->size == queue->capacity) {
        expand(queue);
    }
    queue->rear = (queue->rear + 1) % queue->capacity; // 循环数组
    queue->data[queue->rear] = value;
    queue->size++;
}

5.销毁队列

void freeQueue(queue *queue) {
    free(queue->data);
    queue->data = NULL;
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = 0;
}

6.测试

int main() {
    queue queue;
    initQueue(&queue);
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    printf("Front element is %d\n", peek(&queue));
    printf("Dequeued element is %d\n", dequeue(&queue));
    printf("Front element is now %d\n", peek(&queue));
    freeQueue(&queue);
    return 0;
}

推荐学习 https://xxetb.xetslk.com/s/p5Ibb

目录
相关文章
|
6月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
42 0
|
7月前
|
缓存
队列的实现及操作(链表实现)
队列的实现及操作(链表实现)
|
7月前
|
存储
队列的学习(一)用数组和链表实现单向队列
队列的学习(一)用数组和链表实现单向队列 队列(Queue)是一种先进先出的数据结构,类似于现实生活中排队的场景。它有两个基本操作:入队(enqueue)和出队(dequeue)。在本文中,我们将介绍如何使用数组和链表来实现单向队列。
|
消息中间件 前端开发 JavaScript
使用数组实现队列
使用数组实现队列
62 0
|
C++
7.5 C/C++ 实现链表队列
链表队列是一种基于链表实现的队列,相比于顺序队列而言,链表队列不需要预先申请固定大小的内存空间,可以根据需要动态申请和释放内存。在链表队列中,每个节点包含一个数据元素和一个指向下一个节点的指针,头节点表示队头,尾节点表示队尾,入队操作在队尾插入元素,出队操作在队头删除元素,队列的长度由节点数量决定。由于链表队列没有容量限制,因此可以处理任意数量的元素,但是相比于顺序队列,链表队列的访问速度较慢,因为需要通过指针来访问下一个节点。
76 0
用队列实现栈和用栈实现队列上
用队列实现栈和用栈实现队列上
79 0
用队列实现栈和用栈实现队列下
用队列实现栈和用栈实现队列下
114 0
队列的定义、基本操作、顺序实现(初始化,入队,出队)
数据结构:队列的定义、基本操作、顺序实现(初始化,入队,出队)附有代码讲解
650 0
|
C# C++ 索引
用C#构造一个队列Queue。要求此队列是循环队列,并进行入队、出队的测试。
用C#构造一个队列Queue。要求此队列是循环队列,并进行入队、出队的测试。
203 0
用C#构造一个队列Queue。要求此队列是循环队列,并进行入队、出队的测试。
|
存储 索引
【数据结构】—— 队列(有序队列及环形队列的数组实现)
【数据结构】—— 队列(有序队列及环形队列的数组实现)
207 0
【数据结构】—— 队列(有序队列及环形队列的数组实现)