队列 | 邪云

基础数据结构

发布日期: 2021-06-07

更新日期: 2021-09-20

文章字数: 2k

阅读时长: 10 分

阅读次数:

顺序队列

FIFO : first int first out 先进先出
LILO: last int last out 后进后出
线性结构
需要一片连续存储空间
队首head, 队尾tail
先进先出
队尾入队，队首出队

结构定义

//结构定义 
typedef struct Queue{//普通队列 
    int *data;
    int head, tail, length;
} Queue;

// 队尾 ：tail
// 队首 ：head
// length队列长度
// data_type 元素

结构操作

// 结构操作 
Queue *init_Queue(int);
void clear_Queue(Queue *);
int push(Queue *, int);
int front(Queue *);
int pop(Queue *);
int empty(Queue *);
void output(Queue *);

测试

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

//结构定义 
typedef struct Queue{//普通队列 
    int *data;
    int head, tail, length;
} Queue;

// 结构操作 
Queue *init_Queue(int);
void clear_Queue(Queue *);
int push(Queue *, int);
int front(Queue *);
int pop(Queue *);
int empty(Queue *);
void output(Queue *); 

int main() {
    srand(time(0));
    #define MAX_N 20
    Queue *q = init_Queue(10);
    for (int i = 0; i < MAX_N; i++) {
        int val = rand() % 100;
        int op = rand() % 4;
        switch (op) {
            case 0 :
            case 1 :
            case 2 : {
                printf("入队 %d， %s\n", val, push(q, val) ? "入队成功" : "入队失败");
            } break;
            case 3 : {
                if (!empty(q)) {
                    // 为啥要分成两行写？
                    // 跟系统的增长顺序有关，
                    // 现代操作系统栈的增长顺序从高地址向低地址增长； 
                    /*
                    printf("出队元素:%d, ", front(q));
                    printf("%s\n", pop(q) ? "出队成功" : "出队失败");*/
                    printf("%s, 出队元素：%d\n", pop(q) ? "出队成功" : "出队失败", front(q));
                    
                }
            } break;
        }
        output(q), printf("\n");
    }
    #undef MAX_N 
    return 0;
}

Queue *init_Queue(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->length = n;
    q->head = q->tail = 0;
    return q;
}

void clear_Queue(Queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
} 

int empty(Queue *q) {//判断队列是否为空 
    return q->head == q->tail;//为空返回1 
}

int front(Queue *q) { //打印队首元素 
    return q->data[q->head];
}

int push(Queue *q, int val) {
    if (q == NULL) return 0; //队列不存在 
    if (q->tail == q->length) return 0; //队列满了
    q->data[q->tail++] = val;
    return 1;
}
int pop(Queue *q) {//出队操作 
    if (q == NULL) return 0;
    if (empty(q)) return 0; //队列为空 
    q->head += 1; 
    return 1;
}

void output(Queue *q) {
    if (q == NULL) return ;
    printf("Queue: [");
    for (int i = q->head; i < q->tail; i++) {
        i != q->head && printf(", ");
        printf("%d", q->data[i]); 
    }
    printf("]\n");
    return ;
}

循环队列

解决队列假溢出

结构定义

//结构定义 

typedef struct Queue{//循环队列 
    int *data;
    int head, tail, length, count;
} Queue;

// 队尾 ：tail
// 队首 ：head
// count 元素个数
// length队列长度
// data_type 元素

结构操作

// 结构操作 
Queue *init_Queue(int);
void clear_Queue(Queue *);
int push(Queue *, int);
int front(Queue *);
int pop(Queue *);
int empty(Queue *);
void output(Queue *); 
int expand(Queue *);

扩容操作

int expand(Queue *q) {
    //不能用realloc();可能导致数据错乱
    int extr_size = q->length;
    int *temp;
    while (extr_size) {
        temp = (int *)malloc(sizeof(int) * (q->length + extr_size));
        if (temp) break;
        extr_size >>= 1;
    } 
    if (temp == NULL) return 0;
    for (int i = q->head, j = 0; j < q->count; j++) {
        temp[j] = q->data[(j + i) % q->length];
    }
    free(q->data);
    q->data = temp;
    q->head = 0, q->tail = q->count;
    q->length += extr_size;
    return 1;
}

测试

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

//结构定义 

typedef struct Queue{//循环队列 
    int *data;
    int head, tail, length, count;
} Queue;

// 队尾 ：tail
// 队首 ：head
// count 元素个数
// length队列长度
// data_type 元素

// 结构操作 
Queue *init_Queue(int);
void clear_Queue(Queue *);
int push(Queue *, int);
int front(Queue *);
int pop(Queue *);
int empty(Queue *);
void output(Queue *); 
int expand(Queue *);

int main() {
    srand(time(0));
    #define MAX_N 30
    Queue *q = init_Queue(1);
    for (int i = 0; i < MAX_N; i++) {
        int val = rand() % 100;
        int op = rand() % 4;
        switch (op) {
            case 0 :
            case 1 :
            case 2 : {
                printf("入队 %d， %s\n", val, push(q, val) ? "入队成功" : "入队失败");
            } break;
            case 3 : {
                if (!empty(q)) {
                    printf("出队元素:%d, ", front(q));
                    printf("%s\n", pop(q) ? "出队成功" : "出队失败");
                }
            } break;
        }
        output(q), printf("\n");
    }
    #undef MAX_N 
    return 0;
}

Queue *init_Queue(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (int *)malloc(sizeof(int) * n);
    q->length = n;
    q->head = q->tail = 0;
    q->count = 0;
    return q;
}

void clear_Queue(Queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
} 

int empty(Queue *q) {//判断队列是否为空 
    return !(q->count);//为空返回1 
}

int front(Queue *q) { //打印队首元素 
    return q->data[q->head];
}

int push(Queue *q, int val) {
    if (q == NULL) return 0; //队列不存在 
    if (q->count == q->length) {
        if (!expand(q)) {
            printf("扩容失败 !\n");
            return 0;
        }
        printf("扩容成功，容量：%d\n", q->length);
    } //队列满了
    q->data[q->tail++] = val;
    q->tail %= q->length;
    //if (q->tail == q->length) q->tail = 0;
    q->count += 1;
    return 1;
}
int pop(Queue *q) {//出队操作 
    if (q == NULL) return 0;
    if (empty(q)) return 0; //队列为空 
    q->head += 1;
    q->head %= q->length;
    //if (q->head == q->length) q->head = 0;
    q->count -= 1;
    return 1;
}

void output(Queue *q) {
//    printf("队列长度：%d\nQueue: [", q->count);
//    int n = q->count, i = q->head;
//    while (n--) {
//        printf("%d", q->data[i++]);
//        i %= q->length;
//        n && printf(", ");
//    }
//    printf("]\n");
    printf("队列长度：%d\nQueue: [", q->count);
    for (int i = q->head, j = 0; j < q->count; j++) {
        j && printf(", ");
        printf("%d", q->data[(j + i) % q->length]);
    }
    printf("]\n");
    return ;
}

int expand(Queue *q) {
    //不能用realloc();可能导致数据错乱
    int extr_size = q->length;
    int *temp;
    while (extr_size) {
        temp = (int *)malloc(sizeof(int) * (q->length + extr_size));
        if (temp) break;
        extr_size >>= 1;
    } 
    if (temp == NULL) return 0;
//    for (int i = q->head, j = 0; j < q->count; j++) {
//        temp[j] = q->data[(j + i) % q->length];
//    }
    int n = q->count, i = 0;
    while (n--) {
        temp[i++] = q->data[q->head++];
        q->head %= q->length;
    }
    free(q->data);
    q->data = temp;
    q->head = 0, q->tail = q->count;
    q->length += extr_size;
    return 1;
}

链队列

链表实现的队列
空间消耗大

结构定义

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

typedef struct Queue {
    int length; //链队列长度 
    Node head; //虚拟队列头节点，存储队列第一个节点 
    Node *tail; //尾指针 
} Queue;

说明一下

定义虚拟头节点head，初始化一定得开辟head空间
初始化操作init_Queue(Queue *) 中，必须有一下代码，不然q->tail->next = node;这行不执行，调试时候会报错。
```
q->head = *(Node *)malloc(sizeof(Node));
q->tail = &(q->head); 
```

结构操作

// 结构操作 

Queue *init_Queue(); // 队列初始化 
Node *getnewNode(int); // 封装val为节点 
int front(Queue *); // 打印队首元素不删除 
int pop(Queue *); //队首弹出元素 
int push(Queue *, int); // 队尾压入元素 
int empty(Queue *); // 判断队列是否为空 
void output(Queue *); //输出链队列 
void clear_Queue(Queue *); //队列销毁
void clear_Node(Node *); //节点销毁

测试

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


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

typedef struct Queue {
    int length; //链队列长度 
    Node head; //虚拟队列头节点，存储队列第一个节点 
    Node *tail; //尾指针 
} Queue;

// 结构操作 

Queue *init_Queue(); // 队列初始化 
Node *getnewNode(int); // 封装val为节点 
int front(Queue *); // 打印队首元素不删除 
int pop(Queue *); //队首弹出元素 
int push(Queue *, int); // 队尾压入元素 
int empty(Queue *); // 判断队列是否为空 
void output(Queue *); //输出链队列 
void clear_Queue(Queue *); //队列销毁
void clear_Node(Node *); //节点销毁 

int main() {
    srand(time(0));
    #define MAX_N 2000
    Queue *q = init_Queue();
    for (int i = 0; i < MAX_N; i++) {
        printf("i = %d\n", i);
        int op = rand() % 4;
        int val = rand() % 100;
        switch (op) {
            
            case 0 :
            case 2 : {
                printf("插入元素：%d, %s\n", val, push(q, val) ? "插入成功" : "插入失败");
            } break;
            
            case 1 :
            case 3 : {
                if (!empty(q)) {
                    //printf("删除元素：%d, %s\n", front(q), pop(q) ? "成功" : "失败"); 
                    //也可以这么写 
                    printf("删除元素：%d，", front(q));
                    printf("%s\n", pop(q) ? "删除成功" : "删除失败");
                } else printf("队列为空\n");
            }
        }
        output(q), printf("\n");
    }
    #undef MAX_N
    clear_Queue(q);
    return 0;
}

Node *getnewNode(int val) { //封装val为节点 
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    return node;
}

Queue *init_Queue() { // 队列初始化 
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->head = *(Node *)malloc(sizeof(Node));
    
    /*使其指向虚拟头节点 ，这步很重要，
    找了很久才知道这里错了，没写这步的时候一直错，
    还不知道哪里错 
    */ 
    q->tail = &(q->head); 
    
    q->head.next = NULL;
    q->length = 0;
    return q;
}

int front(Queue *q) {
    return q->head.next->data;
}

int push(Queue *q, int val) { //从队尾压入元素 
    if (q == NULL) return 0;
    Node *node = getnewNode(val);
    q->tail->next = node;
    q->tail = node;
    q->length += 1;
    return 1;
}

int pop(Queue *q) { //弹出队首元素 
    if (q == NULL) return 0;
    if (empty(q)) return 0; 
    Node *p = q->head.next; //保存队首 
    q->head.next = p->next; //  head保存队首位置 
    q->length -= 1;
    clear_Node(p); //销毁队头元素 
    if (!(q->length)) q->tail = &(q->head);
    return 1;
}

int empty(Queue *q) {
    return !(q->length);
}

void clear_Node(Node *node) {
    if (node == NULL) return ;
    free(node);
    return ;
}

void clear_Queue(Queue *q) {
    if (q == NULL) return ;
    Node *p = q->head.next, *qq;
    while (p) {
        qq = p->next;
        clear_Node(p);
        p = qq;
    }
    free(&(q->head));
    free(q);
    return ;
}

void output(Queue *q) {
    if (q == NULL) return ;
    printf("队列长度：%d\n", q->length); 
    int n = q->length;
    Node *node = q->head.next; 
    printf("Queue：[");
    while (n--) {
        printf("%d", node->data);
        n && printf(", ");
        node = node->next;
    }
    printf("]\n");
    return ;
}

Axieyun

https://Axieyun.top/posts/682f.html

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !

基础数据结构

队列

顺序队列

结构定义

结构操作

测试

循环队列

结构定义

结构操作

扩容操作

测试

链队列

结构定义

说明一下

结构操作

测试

你的赏识是我前进的动力