-
Notifications
You must be signed in to change notification settings - Fork 0
/
linked_queue.c
109 lines (79 loc) · 1.93 KB
/
linked_queue.c
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
#include "linked_queue.h"
//init_queue, init_qnode, add(from rear), remove(from front), isEmpty
//Functions--------------------------------------
//Initializes a Queue struct's sentinal nodes
void init_queue(Queue *q) {
q->head.next = &(q->tail);
q->tail.prev = &(q->head);
q->head.prev = NULL;
q->tail.next = NULL;
}
//Returns an initialized Queue struct
Queue* create_queue() {
Queue *q = malloc(sizeof(Queue));
init_queue(q);
return q;
}
//Initializes a QNode to have all NULL ptrs
void init_qnode(QNode *node) {
node->next = NULL;
node->prev = NULL;
}
//Adds the passed in Qnode to the END of the passed in Queue
void add_queue(Queue *q, QNode *node) {
node->next = &(q->tail);
node->prev = q->tail.prev;
q->tail.prev->next = node;
q->tail.prev = node;
}
//Pops the element at the front of the queue off and returns it
//Return the removed node if successful
//Return NULL if the Queue is empty
QNode* remove_queue(Queue *q) {
//if queue is empty
if (is_empty(q)) {
//ERROR
return NULL;
}
else {
QNode *temp = q->head.next;
//new linkage
q->head.next = q->head.next->next;
q->head.next->prev = &(q->head);
//kill temp's access to the list
temp->prev = NULL;
temp->next = NULL;
return temp;
}
}
//Takes in a Queue, returns if its empty
//Return 1 if empty
//Return 0 if NOT empty
int is_empty (Queue *q) {
//if the head's next points to the tail
if (q->head.next == &(q->tail)) {
return 1;
}
return 0;
}
//Takes in a queue, returns its size.
//Returns size of -1 on error.
int size_queue(Queue * q) {
if (!q)
return -1;
int count = 0;
QNode * it = q->head.next;
while (it != &q->tail)
count++, it = it->next;
return count;
}
//Takes a Queue and prints all the addresses of the nodes
void print_queue(Queue * q) {
if (!q)
return;
QNode * it = q->head.next;
printf("head: %p\n", &q->head);
while (it != &(q->tail))
printf("%p\n", it), it = it->next;
printf("tail: %p\n", &q->tail);
}