Giải thích hàng đợi dùng danh sách liên kết trong C

Tràn hàng đợi và thiếu hàng đợi có thể tránh bằng danh sách liên kết.

Các thao tác trên hàng đợi với danh sách liên kết:

• Chèn
• Xóa

Chèn

Cú pháp:

Cú pháp

&item: Newnode = (node*) malloc(sizeof(node)); 
newnode->data = item; 
newnode->link = NULL; 
if((front == NULL) || (rear == NULL)){ 
    front = newnode; 
    rear = newnode; 
}else{ 
    Rear->link = newnode; 
    rear = newnode; 
}

Xóa

Cú pháp:

Cú pháp

if(front == NULL) 
    printf("Khong the xoa, hang doi rong"); 
else{ 
    temp = front; 
    front = front->link; 
    free(temp); 
}

Hiển thị

Cú pháp:

Cú pháp

while(front != NULL){ 
    printf("%d", front->data); 
    front = front->link; 
}

Chương trình

Chương trình C hàng đợi bằng danh sách liên kết:

#include <stdio.h> 
#include <stdlib.h> 
struct node{ 
    int info; 
    struct node *ptr; 
} *front, *rear, *temp, *front1; 
int frontelement(); 
void enq(int data); 
void deq(); 
void display(); 
void create(); 
int count = 0; 
void main(){ 
    int no, ch, e; 
    printf("\n 1 - Enqueue"); 
    printf("\n 2 - Dequeue"); 
    printf("\n 3 - Display"); 
    printf("\n 4 - Exit"); 
    printf("\n 5 - Front"); 
    create(); 
    while(1){ 
        printf("\n Nhap lua chon: "); 
        scanf("%d", &ch); 
        switch(ch){ 
            case 1: 
                printf("Nhap du lieu: "); 
                scanf("%d", &no); 
                enq(no); 
                break; 
            case 2: 
                deq(); 
                break; 
            case 3: 
                display(); 
                break; 
            case 4: 
                exit(0); 
                break; 
            case 5: 
                e = frontelement(); 
                if(e != 0) 
                    printf("Phan tu dau: %d", e); 
                else 
                    printf("\n Khong co phan tu dau"); 
                break; 
            default: 
                printf("Lua chon sai, thu lai "); 
                break; 
        } 
    } 
} 
void enq(int data){ 
    if(rear == NULL){ 
        rear = (struct node *)malloc(1*sizeof(struct node)); 
        rear->ptr = NULL; 
        rear->info = data; 
        front = rear; 
    }else{ 
        temp = (struct node *)malloc(1*sizeof(struct node)); 
        rear->ptr = temp; 
        temp->info = data; 
        temp->ptr = NULL; 
        rear = temp; 
    } 
    count++; 
} 
void display(){ 
    front1 = front; 
    if((front1 == NULL) && (rear == NULL)){ 
        printf("Hang doi rong"); 
        return; 
    } 
    while(front1 != rear){ 
        printf("%d ", front1->info); 
        front1 = front1->ptr; 
    } 
    if(front1 == rear) 
        printf("%d", front1->info); 
} 
void deq(){ 
    front1 = front; 
    if(front1 == NULL){ 
        printf("\n Loi"); 
        return; 
    } else if(front1->ptr != NULL){ 
        front1 = front1->ptr; 
        printf("\n Gia tri Dequeued: %d", front->info); 
        free(front); 
        front = front1; 
    }else{ 
        printf("\n Gia tri Dequeued: %d", front->info); 
        free(front); 
        front = NULL; 
        rear = NULL; 
    } 
    count--; 
} 
int frontelement(){ 
    if((front != NULL) && (rear != NULL)) 
        return(front->info); 
    else 
        return 0; 
}

Đầu ra

Kết quả chạy chương trình:

1 - Enqueue 
2 - Dequeue 
3 - Display 
4 - Exit 
5 - Front 
Nhap lua chon: 1 
Nhap du lieu: 14 
Nhap lua chon: 1 
Nhap du lieu: 85 
Nhap lua chon: 1 
Nhap du lieu: 38 
Nhap lua chon: 5 
Phan tu dau: 14 
Nhap lua chon: 3 
14 85 38 
Nhap lua chon: 2 
Dequeued: 14 
Nhap lua chon: 3 
Nhap lua chon: 4