Hàng đợi

Cài đặt hàng đợi

Có 2 cách cài đặt hàng đợi:
- Dùng mảng.
- Dùng danh sách liên kết.
1. Cài đặt hàng đợi sử dụng mảng trong C (Implementation Queue using Array)
a) Mảng bình thường:
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
typedef <Element's type> El_type;
typedef struct Queue
{
El_type el[MAX];
int front;
int rear;
} Queue;
Các thao tác:
- Khởi tạo hàng đợi(Initialize Queue)
Eltype *initQ(Queue *q)
{
q = (Queue *)malloc(sizeof(Queue));
if(q!= NULL) 
{
 q->front = -1;
 q->rear = -1;
}
return q;
}
- Kiểm tra xem hàng đợi có rỗng không? (Check if a queue is empty)
int isEmpty(Queue *q)
{
return (q->front == -1);
}
- Kiểm tra xem hàng đợi có đầy không? (Check if a queue is full)
int isFull(Queue q)
{
return (q.rear-q.front+1 == MAX);
}
- Đưa thêm một phần tử vào hàng đợi
void enQ(El_type new_el, Queue *q)
{
if(!isFull(q))
{
 if(isEmpty(q)) q->front = q->front+1;
 q->rear = q->rear+1;
 q->el[q->rear] = new_el;
}
else
 printf("Queue is full.\n");
}
- Xóa một phần tử khỏi hàng đợi
void deQ(Queue *q)
{
if(!isEmpty(q)) 
q->front = q->front+1;  
else
printf("Queue is empty.\n");
}
Nhược điểm:
- Qua mỗi lần xóa (deQ): phần sử dụng được của mảng sẽ giảm đi (do front tăng lên).
Cách khắc phục:
- Sử dụng mảng vòng (Circular Array).
b) Mảng vòng:
tương ta có:
- Khởi tạo hàng đợi(Initialize Queue)
Eltype *initQ(Queue *q)
{
q = (Queue *)malloc(sizeof(Queue));
if(q!= NULL) 
{
 q->front = -1;
 q->rear = -1;
}
return q;
}
- Kiểm tra xem hàng đợi có rỗng không? (Check if a queue is empty)
int empty_queue(queue q)
{
return q.front==-1;
}
- Kiểm tra xem hàng đợi có đầy không? (Check if a queue is full)
int full_queue(queue q)
{
return (q.rear-q.front+1)%maxlength==0;
}
- Đưa thêm một phần tử vào hàng đợi
void enqueue(elementtype x,queue *q)
{
if(!full_queue(*q))
{
if(empty_queue(*q))q->front=0;
q->rear=(q->rear+1)%maxlength;
q->data[q->rear]=x;  
}
else printf("Hang Day!");
}
- Xóa một phần tử khỏi hàng đợi
void dequeue(queue *q)
{
if(!empty_queue(*q))
{
if(q->front==q->rear)makenull_queue(q);
else q->front=(q->front+1)%maxlength;
}
else printf("Hang rong!");
}
Nhược điểm:
- Mặc dù phương pháp sử dụng mảng vòng có thể tận dùng toàn bộ các mảng đã được cấp pháp ban đầu nhưng khi mảng đầy thì không thể thêm phần tử vào hàng được nữa.
Cách khắc phục:
- Sử dụng Danh sách liên kết.
2. Cài hàng đợi sử dụng Danh Sách Liên Kết: (Implementation Queue using List Point)
Khai báo cài đặt hàng bằng con trỏ
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef int elementtype;
typedef struct node{
elementtype data;
node* next;
};
typedef node* position;
typedef struct queue{
position front,rear; 
};
Các thao tác:
- Khởi tạo hàng đợi(Initialize Queue)
void makenull_queue(queue *q)
{
q->front=(node*)malloc(sizeof(node));
q->front->next=NULL;
q->rear=q->front;
}
- Kiểm tra xem hàng đợi có rỗng không? (Check if a queue is empty)
int empty_queue(queue q)
{
return (q.front==q.rear); 
}
- Kiểm tra hàng đợi có đầy không (ở đây không có hàm này vì danh sách liên kết làm sao đầy được ^^!)
- Đưa thêm một phần tử vào hàng đợi
void enqueue(elementtype x, queue *q)
{
q->rear->next=(node*)malloc(sizeof(node));
q->rear=q->rear->next;
q->rear->data=x;
q->rear->next=NULL; 
}
- Xóa một phần tử khỏi hàng đợi
void dequeue(queue *q)
{
position t;
t=q->front;
q->front=q->front->next;
free(t);
}
Ưu điểm:
- khắc phục được tình trạng đầy của việc sử dụng mảng để cài đặt queue.