链队列

链队列

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

结构定义

//结构定义 
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 ;
}