首页 > 其他分享 >队列

队列

时间:2022-10-15 23:15:18浏览次数:34  
标签:node return 队列 Queue int que size

应用:广搜

总结:链表总的来说比较灵活,普通的顺序表有一头是固定的,因此对于队列这种两端都存在数据变化的情况,使用链表实现会比较自然,而使用顺序表实现则要用循环队列的方式来弥补普通顺序表的不足。

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

#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
#define GREEN(a) COLOR(a, 32)

//结构定义:队列(顺序表)
typedef struct Queue {
    int *data;
    int head, tail, size, length;
} Queue;

//结构操作
Queue *init(int size);
void clear(Queue *que);
int expand(Queue *que);
int push(Queue *que, int val);
int front(Queue *que);
int empty(Queue *que);
int pop(Queue *que);
void output(Queue *que);

int main() {
    srand(time(0));
    #define MAX_N 20
    Queue *que = init(1);
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("push %d to the Queue = %d\n", val, push(que, val));
            } break;
            case 3: {
                if (empty(que)) {
                    printf("pop from the Queue = 0\n");
                } else {
                    printf("pop %d from the Queue = ", front(que));
                    printf("%d\n", pop(que));
                }
            } break;
        }
        output(que), printf("\n");
    }
    #undef MAX_N
    clear(que);
    return 0;
}

//结构操作:初始化队列
Queue *init(int size) {
    Queue *que = (Queue *)malloc(sizeof(Queue));
    que->data = (int *)malloc(sizeof(int) * size);
    que->head = que->tail = que->length = 0;
    que->size = size;
    return que;
}

//结构操作:销毁队列
void clear(Queue *que) {
    if (que == NULL) return;
    free(que->data);
    free(que);
    return;
}

//结构操作:队列扩容
int expand(Queue *que) {
    int extra_size = que->size;
    int *temp;
    while (extra_size) {
        temp = (int *)malloc(sizeof(int) * (que->size + extra_size));
        if (temp != NULL) break;
        extra_size >>= 1;
    }
    if (temp == NULL) return 0;
    for (int i = 0; i < que->length; i++) {
        temp[i] = que->data[(que->head + i) % que->size];
    }
    free(que->data);
    que->data = temp;
    que->head = 0;
    que->tail = que->length;
    que->size += extra_size;
    return 1;
}

//结构操作:入队
int push(Queue *que, int val) {
    if (que == NULL) return 0;
    if (que->length == que->size) {
        if (!expand(que)) {
            printf(RED("fail to expand!\n"));
            return 0;
        }
        printf(GREEN("success to expand! the new size = %d\n"), que->size);
    }
    que->data[que->tail++] = val;
    if (que->tail == que->size) que->tail = 0;
    que->length += 1;
    return 1;
}

//结构操作:访问队首元素
int front(Queue *que) {
    return que->data[que->head];
}

//结构操作:队列判空
int empty(Queue *que) {
    return que->length == 0;
}

//结构操作:出队
int pop(Queue *que) {
    if (que == NULL) return 0;
    if (empty(que)) return 0;
    que->head += 1;
    if (que->head == que->size) que->head = 0;
    que->length -= 1;
    return 1;
}

//结构操作:输出所有元素
void output(Queue *que) {
    printf("Queue(%d): [", que->length);
    for (int i = 0; i < que->length; i++) {
        i && printf(", ");
        printf("%d", que->data[(que->head + i) % que->size]);
    }
    printf("]\n");
    return;
}

链队列

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

#define COLOR(a, b) "\033[" #b "m" a "\033[0m"
#define RED(a) COLOR(a, 31)
#define GREEN(a) COLOR(a, 32)

//结构定义:链表节点
typedef struct Node {
    int data;
    Node *next;
} Node;

//结构定义:队列(链表)
typedef struct Queue {
    Node head, *tail; // 定义虚拟头节点 (index = -1) for 入队时可以统一操作
    int length;
} Queue;

//结构操作
Node *getNewNode(int val);
Queue *init();
void clear_node(Node *node);
void clear(Queue *que);
int push(Queue *que, int val);
int front(Queue *que);
int empty(Queue *que);
int pop(Queue *que);
void output(Queue *que);

int main() {
    srand(time(0));
    #define MAX_N 20
    Queue *que = init();
    for (int i = 0; i < MAX_N; i++) {
        int op = rand() % 4;
        int val = rand() % 100;
        switch (op) {
            case 0:
            case 1:
            case 2: {
                printf("push %d to the Queue = %d\n", val, push(que, val));
            } break;
            case 3: {
                if (empty(que)) {
                    printf("pop from the Queue = 0\n");
                } else {
                    printf("pop %d from the Queue = ", front(que));
                    printf("%d\n", pop(que));
                }
            } break;
        }
        output(que), printf("\n");
    }
    #undef MAX_N
    clear(que);
    return 0;
}

//结构操作:获得一个新节点
Node *getNewNode(int val) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    return node;
}

//结构操作:初始化队列
Queue *init() {
    Queue *que = (Queue *)malloc(sizeof(Queue));
    que->head.next = NULL;
    que->tail = &(que->head);
    que->length = 0;
    return que;
}

//结构操作:释放一个节点
void clear_node(Node *node) {
    if (node == NULL) return;
    free(node);
    return;
}

//结构操作:销毁队列
void clear(Queue *que) {
    if (que == NULL) return;
    Node *node = que->head.next, *post_node;
    while (node != NULL) {
        post_node = node->next;
        clear_node(node);
        node = post_node;
    }
    free(que);
    return;
}

//结构操作:入队
int push(Queue *que, int val) {
    if (que == NULL) return 0;
    Node *node = getNewNode(val);
    que->tail->next = node;
    que->tail = node;
    que->length += 1;
    return 1;
}

//结构操作:访问队首元素
int front(Queue *que) {
    return que->head.next->data;
}

//结构操作:队列判空
int empty(Queue *que) {
    return que->length == 0;
}

//结构操作:出队
int pop(Queue *que) {
    if (que == NULL) return 0;
    if (empty(que)) return 0;
    Node *node = que->head.next;
    que->head.next = node->next;
    clear_node(node);
    que->length -= 1;
    if (que->length == 0) que->tail = &(que->head);
    return 1;
}

//结构操作:输出所有元素
void output(Queue *que) {
    printf("Queue(%d): [", que->length);
    for (Node *node = que->head.next; node != NULL; node = node->next) {
        node != que->head.next && printf(", ");
        printf("%d", node->data);
    }
    printf("]\n");
    return;
}

标签:node,return,队列,Queue,int,que,size
From: https://www.cnblogs.com/Kelvin-Wu/p/16795297.html

相关文章

  • 堆与优先队列
    数据结构就是定义一种性质并去维护这种性质所产生的结构。优先队列(堆)#include<stdio.h>#include<stdlib.h>#include<time.h>#defineswap(a,b){\__type......
  • Muduo库之阻塞队列
    在并发编程中,常常需要用到线程安全的队列。常见的线程安全队列的设计分为两种:阻塞队列:常用于生产者和消费者的场景,其中,生产者存放元素,而消费者获取元素。常用的实现方法......
  • RabbitMQ高可用--镜像队列的原理
    简介说明    本文介绍RabbitMQ的镜像队列的原理。镜像队列可以保证RabbitMQ的高可用,防止消息丢失。什么是镜像队列        镜像队列(MirrorQueue):将队列复......
  • C++ 队列!还是要从 STL 中的说起……
    1.前言队列和栈一样,都是受限的数据结构。队列遵循先进先出的存储原则,类似于一根水管,水从一端进入,再从另一端出去。进入的一端称为队尾,出去的一端称为队头。队列有2......
  • JavaScript--队列结构
     1.认识队列     2.队列的应用   3.队列类的常见操作    封装一个队列<!DOCTYPEhtml><htmllang="en"><head><metacharset="U......
  • 数据结构(严蔚敏版)第三章——栈和队列(二)【栈的表示和操作的实现】
    3.3、栈的表示和操作的实现3.3.1、栈的类型定义栈的基本操作的抽象数据类型定义:ADTStack{数据对象;D={ai|ai属于ElementSet,i=1,2,...,n,n>=0}......
  • Go:基于 Redis 实现的延迟队列详解
    大家好,本文来自Go爱好者投稿,作者:finley背景我们在工作中经常遇到等待一段时间后再执行某些任务的需求,比如:若订单创建15分钟后仍未支付,需要关闭订单并释放库存。用......
  • Redis延迟队列golang高效实践
    一、背景 业务中经常会有这样的场景: 到期后自动执行指定操作; 查询某个任务是否完成,未完成等待一定时间再次查询; 回调通知,当回调失败时,等待后重试;等等还......
  • 数据结构(严蔚敏版)——栈和队列(一)【栈和队列的定义和特点】
    第三章__栈和队列3.1、栈和队列的定义和特点3.1.1、栈的定义和特点定义:栈是是一种特殊的线性表,是限定在表尾进行插入或删除操作的线性表。又称为后进先出的线性表,简称L......
  • 通过消息队列MQ实现组件解耦
    ​当业务系统的规模扩大时,也会增加系统架构的复杂度,在架构设计时对系统进行分层与解耦能够避免多个组件之间的性能不足、负载高、任务处理堆栈长及组件故障等风险。    ......