链式队列实现(c语言)_链队列打印

队列的定义

      队列是一个线性的数据结构，这个数据结构只从一端进行插入，另一端进行删除，禁止直接访问除这两端以外的一切数据。

如图所示，队列就像一个管道一样，从一端输入，一端输出，先输入的就先输出。

队列节点的设计与初始化

        链式队列是一种同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点。

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node,*Q_node;
typedef struct queues{
    Q_node front;
    Q_node rear;
}queues,*Queues;
1
2
3
4
5
6
7
8

下面是关于队列和节点的初始化：

Q_node Init_Node(){
    Node* node=(Node*) malloc(sizeof(Node));
    if(node==NULL){
        printf("分配失败");
        exit(ERROR);
    }
    node->next=NULL;
    return node;
}
Queues Init_Queues(){
    Queues queues=(Queues)malloc(sizeof(queues));
    if(queues==NULL){
        printf("内存分配失败");
        exit(ERROR);
    }
    queues->front=NULL;
    queues->rear=NULL;
//    printf("初始化成功\n");
    return queues;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

入队操作

当队列为空队列时，队头和队尾都是应该从空到指向新插入的节点，之后在每次插入都会对队尾节点进行连接，并在将指针移向刚插入的节点。如图所示：

第一次入队时，只有一个节点，也就成为了唯一的节点，所以队头和队尾都指向同一节点。

当队列不为空时，就是队尾在不断的向后移动，在通过节点的next指针指向下一个从而连接。

status push(Queues queues,ElemType e){
    if(queues==NULL){
        return ERROR;
    }
    Q_node node=Init_Node();
    node->data=e;
    if(queues->rear==NULL && queues->front==NULL){
        queues->front=queues->rear=node;
    } else {
    queues->rear->next=node;
    queues->rear=node;
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

连续入队操作

连续入队的也同入队一样，都是通过不断next指针连接，在队尾指针向后移进行插入。

status Queues_I(Queues queues){
    int x;
    if(queues==NULL){
        return ERROR;
    }
    while (scanf("%d",&x)!=EOF){
        Q_node  node=Init_Node();
        node->data=x;
        if(queues->rear==NULL && queues->front==NULL){
          queues->front=queues->rear=node;
        } else{
            queues->rear->next=node;
            queues->rear=node;
        }
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

出队操作

出队则是遵循着队列的先入先出，所以说在出的时候要从队头开始出，如果队内只有一个元素就直接置为空，否则就指向下一个节点，释放原有节点，即为出队。

status pop(Queues q){
    if(q==NULL){
        return ERROR;
    }
    Q_node qNode=q->front;
    if(q->front==q->rear){
        q->front=NULL;
        q->rear=NULL;
    }else{
        q->front=q->front->next;
        free(qNode); 
    }
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

打印队列

void Print_Queues(Queues q){
    if(q==NULL){
        printf("打印出错");
        exit(ERROR);
    }
    Q_node node= q->front;
    while (node!=NULL){
        printf("对列中的元素：%d\n",node->data);
        node=node->next;
    }
}
1
2
3
4
5
6
7
8
9
10
11

完整代码

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int status;
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node,*Q_node;
typedef struct queues{
    Q_node front;
    Q_node rear;
}queues,*Queues;
Q_node Init_Node(){
    Node* node=(Node*) malloc(sizeof(Node));
    if(node==NULL){
        printf("分配失败");
        exit(ERROR);
    }
    node->next=NULL;
    return node;
}
Queues Init_Queues(){
    Queues queues=(Queues)malloc(sizeof(queues));
    if(queues==NULL){
        printf("内存分配失败");
        exit(ERROR);
    }
    queues->front=NULL;
    queues->rear=NULL;
//    printf("初始化成功\n");
    return queues;
}
status push(Queues queues,ElemType e){
    if(queues==NULL){
        return ERROR;
    }
    Q_node node=Init_Node();
    node->data=e;
    if(queues->rear==NULL && queues->front==NULL){
        queues->front=queues->rear=node;
    } else {
    queues->rear->next=node;
    queues->rear=node;
    }
    return OK;
}
/**多条插入*/
status Queues_I(Queues queues){
    int x;
    if(queues==NULL){
        return ERROR;
    }
    while (scanf("%d",&x)!=EOF){
        Q_node  node=Init_Node();
        node->data=x;
        if(queues->rear==NULL && queues->front==NULL){
          queues->front=queues->rear=node;
        } else{
            queues->rear->next=node;
            queues->rear=node;
        }
    }
    return OK;
}
status pop(Queues q,ElemType *e){
    if(q==NULL){
        return ERROR;
    }
    Q_node qNode=q->front;
    *e=q->front->data;
    q->front=q->front->next;

    free(qNode);
    return OK;
}

void Print_Queues(Queues q){
    if(q==NULL){
        printf("打印出错");
        exit(ERROR);
    }
    Q_node node= q->front;
    while (node!=NULL){
        printf("对列中的元素：%d\n",node->data);
        node=node->next;
    }
}

int  main(){
    int x;
Queues  queues=Init_Queues();
    Queues_I(queues);
    Print_Queues(queues);
    push(queues,100);
    printf("入队之后\n");
    Print_Queues(queues);
    pop(queues,&x);
    printf("出队之后\n");
    Print_Queues(queues);
    printf("%d",x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103