Implement Queue with LL

Explanation

1
* // Definition:
2
*
3
* back front
4
* v v
5
* Q: "1" <- "2" <- "3"
6
*
7
*
8
* // enQueue: Push an element from the "back"
9
*
10
* back front
11
* v v
12
* Q: "1" <- "2" <- "3"
13
*
14
* Step 1: create a Node: new = "0"
15
*
16
* Step 2: add from the back, therefore,
17
* new->next = back
18
*
19
* back front
20
* v v
21
* "0" -> "1" <- "2" <- "3"
22
*
23
* Step 3: back->next = new
24
*
25
* |---- back front
26
* v v v
27
* "0" "1" <- "2" <- "3"
28
*
29
* Step 4: back = new
30
*
31
* back front
32
* v v
33
* "0" <- "1" <- "2" <- "3"
34
*
35
*
36
* // deQueue: Delete an element from the "front"
37
*
38
* back front
39
* v v
40
* Q: "1" <- "2" <- "3"
41
*
42
* Step 1: create a Node: tmp to point "front"
43
*
44
* front
45
* back tmp
46
* v v
47
* Q: "1" <- "2" <- "3"
48
*
49
*
50
* Step 2: q->front = q->front->next
51
*
52
*
53
* back front tmp
54
* v v v
55
* "1" <- "2" <- "3"
56
*
57
* Step 3: free(tmp)
58
*
59
* back front
60
* v v
61
* "1" -> "2"
62
*
Copied!

C version

Declaration data structures:

1
#include <stdio.h>
2
#include <stdlib.h>
3
4
struct Node{
5
struct Node* next;
6
int val;
7
};
8
9
10
struct Queue{
11
struct Node* front;
12
struct Node* back;
13
};
Copied!

Create Queue and New an element

1
struct Node* newNode(int value){
2
struct Node* new_node = (struct Node*) malloc (sizeof(struct Node));
3
new_node->val = value;
4
new_node->next = NULL;
5
return new_node;
6
}
7
8
9
struct Queue* creatQueue(){
10
struct Queue* q = (struct Queue*) malloc (sizeof(struct Queue));
11
q->front = NULL;
12
q->back = NULL;
13
return q;
14
}
Copied!

Enqueue and Dequeue

1
void deQueue(struct Queue *q){
2
if(q->front == NULL){
3
return;
4
}
5
struct Node* temp = q->front;
6
7
q->front = q->front->next;
8
9
if (q->front == NULL)
10
q->back = NULL;
11
12
free(temp);
13
14
}
15
16
17
void enQueue(struct Queue *q, int value){
18
struct Node* new_node = newNode(value);
19
20
if(q->back == NULL){
21
22
q->front = new_node;
23
q->back = new_node;
24
return;
25
}
26
27
q->back->next = new_node;
28
q->back = new_node;
29
}
Copied!

Test code:

1
int main() {
2
3
struct Queue* q = creatQueue();
4
enQueue(q, 10);
5
enQueue(q, 20);
6
deQueue(q);
7
deQueue(q);
8
enQueue(q, 30);
9
enQueue(q, 40);
10
enQueue(q, 50);
11
deQueue(q);
12
printf("Queue Front : %d \n", q->front->val);
13
printf("Queue back : %d", q->back->val);
14
15
return 0;
16
}
Copied!
Copy link