Implement Queue with LL

Search…
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!
DS with C - Previous
Reverse Linked List
Next - DS with C
Find mid of LL without traverse
Last modified 5mo ago
Copy link
Contents
Explanation
C version