数据结构之队列的链式存储_队列的链式存储结构

队列的链式存储

这里是数据结构个人学习的笔记记录，如有问题欢迎指正说明

一、队列的链式存储结构

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出，我们把它简单称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。空队列时，我们将队头指针和队尾指针都指向头结点。

先来定义链队列的结构，它类似于单链表，不过有队头指针和队尾指针，具体定义如下

结构体的定义：

typedef struct LinkNode{
    int data;
    LinkNode* next;
}*LinkNodePtr;

typedef struct LinkQueue{
    LinkNodePtr front;
    LinkNodePtr rear;
}*LinkQueuePtr;
1
2
3
4
5
6
7
8
9

二、相关操作实现

1.初始化

malloc一个链队列，并生成一个头结点，队头指针和队尾指针为NULL。

/* 初始化 */
LinkQueuePtr initQueue(){
    LinkQueuePtr resultPtr=(LinkQueuePtr)malloc(sizeof(LinkQueue));
    LinkNodePtr headerPtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
    headerPtr->next=NULL;

    resultPtr->front=headerPtr;
    resultPtr->rear=headerPtr;
    return resultPtr;
}
1
2
3
4
5
6
7
8
9
10

2.依次对栈中的每个数据元素输出

定义一个tempPtr指向队头指针的下一位。

void outputLinkQueue(LinkQueuePtr paraQueuePtr)
{
    LinkNodePtr tempPtr=paraQueuePtr->front->next;
    while(tempPtr!=NULL)
    {
        printf("%d ",tempPtr->data);
        tempPtr=tempPtr->next;
    }
    printf("\r\n");
}
1
2
3
4
5
6
7
8
9
10

3.进队列

进队列只能在队尾，所以只需要将队尾指针进行移动。

void enqueue(LinkQueuePtr paraQueuePtr,int paraElement)
{
    LinkNodePtr tempNodePtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
    tempNodePtr->data=paraElement;
    tempNodePtr->next=NULL;

    paraQueuePtr->rear->next=tempNodePtr;
    paraQueuePtr->rear=tempNodePtr;
}
1
2
3
4
5
6
7
8
9

4.出队列

首先需要判断队列是否为空，如果不为空则将队头元素出队列，并返回该值，并需要判断出队列之后是否为空队列

int dequeue(LinkQueuePtr paraQueuePtr)
{
    int resultValue;
    LinkNodePtr tempNodePtr;

    if(paraQueuePtr->front==paraQueuePtr->rear)
    {
        printf("The queue is empty.\r\n");
        return -1;
    }

    tempNodePtr=paraQueuePtr->front->next;
    resultValue=tempNodePtr->data;
    paraQueuePtr->front->next=tempNodePtr->next;

    if(paraQueuePtr->rear==tempNodePtr)
    {
        paraQueuePtr->rear=paraQueuePtr->front;
    }

    tempNodePtr=NULL;

    return resultValue;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5.链队列中元素个数

遍历整个链队列便能得到这个链队列的长度了。

int lengthQueue(LinkQueuePtr paraQueuePtr)
{
    int length=0;
    LinkNodePtr tempNodePtr;
    tempNodePtr=paraQueuePtr->front->next;

    while(tempNodePtr!=NULL)
    {
        length++;
        tempNodePtr=tempNodePtr->next;
    }
    return length;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

6.测试函数

该处我写了两个测试函数，一个为对链队列的测试操作，还有一个是对地址的输出，便于我们看到链队列是如何存储数据的。

void testLinkQueue(){
    printf("---Begin!---\r\n");
    LinkQueuePtr tempQueuePtr;
    tempQueuePtr=initQueue();
    enqueue(tempQueuePtr,10);
    enqueue(tempQueuePtr,30);
    enqueue(tempQueuePtr,50);

    outputLinkQueue(tempQueuePtr);

    printf("Length of the queue is %d\r\n",lengthQueue(tempQueuePtr));

    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));

    enqueue(tempQueuePtr,8);
    enqueue(tempQueuePtr,6);
    enqueue(tempQueuePtr,9);
    outputLinkQueue(tempQueuePtr);
    printf("---End!---\r\n");
}

void testAddress()
{
    LinkQueuePtr tempQueuePtr;
    tempQueuePtr=initQueue();

    enqueue(tempQueuePtr,8);
    enqueue(tempQueuePtr,6);
    enqueue(tempQueuePtr,9);
    outputLinkQueue(tempQueuePtr);

    printf("tempQueuePtr:%ld\n",&tempQueuePtr);
    printf("tempQueuePtr->front:%ld\n",&tempQueuePtr->front);
    printf("tempQueuePtr->rear:%ld\n",&tempQueuePtr->rear);
    printf("tempQueuePtr->front->next:%ld\n",&tempQueuePtr->front->next);
}
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

7.具体代码实现

#include<stdio.h>
#include<malloc.h>

typedef struct LinkNode{
    int data;
    LinkNode* next;
}*LinkNodePtr;

typedef struct LinkQueue{
    LinkNodePtr front;
    LinkNodePtr rear;
}*LinkQueuePtr;

LinkQueuePtr initQueue(){
    LinkQueuePtr resultPtr=(LinkQueuePtr)malloc(sizeof(LinkQueue));
    LinkNodePtr headerPtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
    headerPtr->next=NULL;

    resultPtr->front=headerPtr;
    resultPtr->rear=headerPtr;
    return resultPtr;
}

void outputLinkQueue(LinkQueuePtr paraQueuePtr)
{
    LinkNodePtr tempPtr=paraQueuePtr->front->next;
    while(tempPtr!=NULL)
    {
        printf("%d ",tempPtr->data);
        tempPtr=tempPtr->next;
    }
    printf("\r\n");
}

void enqueue(LinkQueuePtr paraQueuePtr,int paraElement)
{
    LinkNodePtr tempNodePtr=(LinkNodePtr)malloc(sizeof(LinkNodePtr));
    tempNodePtr->data=paraElement;
    tempNodePtr->next=NULL;

    paraQueuePtr->rear->next=tempNodePtr;
    paraQueuePtr->rear=tempNodePtr;
}

int dequeue(LinkQueuePtr paraQueuePtr)
{
    int resultValue;
    LinkNodePtr tempNodePtr;

    if(paraQueuePtr->front==paraQueuePtr->rear)
    {
        printf("The queue is empty.\r\n");
        return -1;
    }

    tempNodePtr=paraQueuePtr->front->next;
    resultValue=tempNodePtr->data;
    paraQueuePtr->front->next=tempNodePtr->next;

    if(paraQueuePtr->rear==tempNodePtr)
    {
        paraQueuePtr->rear=paraQueuePtr->front;
    }

    free(tempNodePtr);

    return resultValue;
}

int lengthQueue(LinkQueuePtr paraQueuePtr)
{
    int length=0;
    LinkNodePtr tempNodePtr;
    tempNodePtr=paraQueuePtr->front->next;

    while(tempNodePtr!=NULL)
    {
        length++;
        tempNodePtr=tempNodePtr->next;
    }
    return length;
}

void testLinkQueue(){
    printf("---Begin!---\r\n");
    LinkQueuePtr tempQueuePtr;
    tempQueuePtr=initQueue();
    enqueue(tempQueuePtr,10);
    enqueue(tempQueuePtr,30);
    enqueue(tempQueuePtr,50);

    outputLinkQueue(tempQueuePtr);

    printf("Length of the queue is %d\r\n",lengthQueue(tempQueuePtr));

    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));
    printf("dequeue gets %d\r\n",dequeue(tempQueuePtr));

    enqueue(tempQueuePtr,8);
    enqueue(tempQueuePtr,6);
    enqueue(tempQueuePtr,9);
    outputLinkQueue(tempQueuePtr);
    printf("---End!---\r\n");
}

void testAddress()
{
    LinkQueuePtr tempQueuePtr;
    tempQueuePtr=initQueue();

    enqueue(tempQueuePtr,8);
    enqueue(tempQueuePtr,6);
    enqueue(tempQueuePtr,9);
    outputLinkQueue(tempQueuePtr);

    printf("tempQueuePtr:%ld\n",&tempQueuePtr);
    printf("tempQueuePtr->front:%ld\n",&tempQueuePtr->front);
    printf("tempQueuePtr->rear:%ld\n",&tempQueuePtr->rear);
    printf("tempQueuePtr->front->next:%ld\n",&tempQueuePtr->front->next);
}
int main()
{
    testLinkQueue();
    testAddress();
    return 0;
}
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
121
122
123
124
125
126
127
128

三、样例输出

—Begin!—
10 30 50
Length of the queue is 3
dequeue gets 10
dequeue gets 30
dequeue gets 50
The queue is empty.
dequeue gets -1
8 6 9
—End!—
8 6 9
tempQueuePtr:6421992
tempQueuePtr->front:13004720
tempQueuePtr->rear:13004728
tempQueuePtr->front->next:12981320

四、问题回答

1.这个问题在链队列里我没有找到答案，但我发现一个巧合，就是我多次打印链队列的队头指针和队尾指针的地址，我发现它们总是差两个字节，无论该链队列中有多少数据。
2.局部变量的空间能重复利用，它之所以叫局部变量，就是它只在局部函数里利用，函数调用结束则该空间就会释放。
3.指针的值是它所指向的变量的地址，而指针的地址是指该指针变量本身的地址。

五、写在最后

链队列适用于长度不确定的链队列。
因为链队列类似于单链表，所以每个结点的存储位置不一定是连续的。
在空间上链队列比循环队列更加灵活。