数据结构与算法 - 队列(完整代码)_数据结构队列代码

样例输入:

in 1
in 3
in 5
in 9
in 12
out
end
1
2
3
4
5
6
7

样例输出:

Queue length: 4
Queue data: 3  5  9  12
1
2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int T;

struct LNode {
    T data;
    LNode* next;
};
LNode* CLQ_Create()
// 创建一个队列
{
    LNode* rear=(LNode*)malloc(sizeof(LNode));
    rear->data = 0;
    rear->next = rear;
    return rear;
}
bool CLQ_IsEmpty(LNode* rear)
// 判断队列是否为空
{
    return rear==rear->next;
}
bool CLQ_Out(LNode* & rear, T& item)
// 出队列。空队列时，返回值为false。rear指向尾结点
{
    if(CLQ_IsEmpty(rear)) return false;
    else if(rear->next->data==1) 
    {
        rear=rear->next;
        rear->next=rear;
        rear->data--;
    }
    else{
        LNode* addNode=rear->next;
        addNode->next=addNode->next->next;
        addNode->data--;
        return true;
    }
}
void CLQ_MakeEmpty(LNode* &rear)
// rear指向尾结点
// 将队列变为空队列
{
    T item;
    while(!CLQ_IsEmpty(rear))
        CLQ_Out(rear,item);
}
void CLQ_Free(LNode* rear)
// rear指向尾结点
{
    CLQ_MakeEmpty(rear);
    free(rear);
}


int CLQ_Length(LNode* rear)
// 返回队列长度，rear指向尾结点
{
    return rear->next->data;
}
void CLQ_In(LNode* &rear, T x)
// 入队列, 新结点加入链表尾部。rear指向尾结点
{
    LNode* newNode=new LNode;
    newNode->data=x;
    newNode->next=rear->next;
    rear->next=newNode;
    rear=newNode;
    rear->next->data++;
}

bool CLQ_Head(LNode* rear, T& item)
// rear指向尾结点
// 获取队列头。空队列时返回值为false。
{
    if (CLQ_IsEmpty(rear)) 
        return false;
    item = rear->next->next->data;
    return true;
}
void CLQ_Print(LNode* rear)
// 打印队列
{
    if (CLQ_IsEmpty(rear))  {
        printf("The queue is: empty. \n");
        return;
    }
    LNode* node=rear->next->next;
    do {
        printf("%d  ", node->data);
        node = node->next;
    }   while (node != rear->next); 
    //printf("\n");
}
int main()
{
    LNode* rear=CLQ_Create();
    char dowhat[100];
    while(true) {
        scanf("%s", dowhat);
        if (!strcmp(dowhat,"in")) {
            T x;
            scanf("%d", &x);
            CLQ_In(rear,x);
        }else if (!strcmp(dowhat,"out")) {
            T item;
            CLQ_Out(rear, item);
        }
        else {
            break;
        }
    }
    int length=CLQ_Length(rear);
    printf("Queue length: %d\n", length);
    printf("Queue data: ");
    CLQ_Print(rear);
    CLQ_Free(rear);
}


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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120