Hàng đợi – Wikipedia tiếng Việt

Hàng đợi (tiếng Anh: queue) là một cấu trúc dữ liệu dùng để chứa các đối tượng thực hiện việc theo cơ chế FIFO (viết tắt từ tiếng Anh: First In First Out), nghĩa là “vào trước ra trước”

Trong hàng đợi, các đối tượng người dùng hoàn toàn có thể đã được thêm vào hàng đợi bất kể khi nào, nhưng chỉ có đối tượng người dùng thêm vào tiên phong mới đã được phép lấy ra khỏi hàng đợi. Thao tác thêm vào và lấy một đối tượng người dùng ra khỏi hàng đợi được gọi lần lượt là ” enqueue ” và ” dequeue “. Việc thêm một đối tượng người dùng luôn diễn ra ở cuối hàng đợi , và một thành phần luôn được lấy ra đến từ đầu hàng đợi .Trong tin học, cấu trúc tài liệu hàng đợi có nhiều ứng dụng : khử đệ quy, tổ chức triển khai lưu vết các quá trình tìm kiếm theo chiều rộng , quay lui, vét cạn, tổ chức triển khai quản trị và phân phối tiến trình trong các hệ quản lý và điều hành, tổ chức triển khai bộ đệm bàn phím .

Cấu trúc dữ liệu hàng đợi có thể định nghĩa như sau: Hàng đợi chính là một cấu trúc dữ liệu trừu tượng (ADT) tuyến tính. Tương tự như ngăn xếp, hàng đợi trợ giúp các thao tác:

Hàng đợi – Wikipedia tiếng Việt

Bạn đang đọc: Hàng đợi – Wikipedia tiếng Việt

EnQueue(o): thêm đối tượng o vào cuối hàng đợi.DeQueue(): lấy đối tượng ở đầu queue ra khỏi hàng đợi , trả về giá trị của nó. Nếu hàng đợi rỗng thì lỗi cũng sẽ xảy ra.IsEmpty(): kiểm tra xem hàng đợi có rỗng không.Front(): trả về giá trị của phần tử nằm ở đầu hàng đợi mà chưa hủy nó. Nếu hàng đợi rỗng thì lỗi sẽ xảy ra.

Các thao tác thêm, trích , huỷ một thành phần phải đã được thực thi ở hai phía khác nhau của hàng đợi, do đó hoạt động giải trí của hàng đợi được triển khai theo nguyên tắc FIFO. Cũng như ngăn xếp, cấu trúc mảng một chiều hoặc cấu trúc list link hoàn toàn có thể dùng để trình diễn cấu trúc hàng đợi .

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

Có 2 cách cài đặt hàng đợi :- Sử dụng mảng .- Dùng list link .1. Cài đặt hàng đợi sử dụng mảng trong C ( Implementation Queue using Array )a ) Mảng thông thường :

#include #include

#define MAX 20

typedef 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 chưa ? ( Check if a queue is empty )

int isEmpty(Queue *q) return (q->front == -1);

– Kiểm tra xem hàng đợi có đầy chưa ? ( Check if a queue is full )

int isFull(Queue q) return (q.rear-q.front+1 == MAX);

– Đưa thêm một thành phần 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 thành phần 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 chưa ? ( 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 thành phần 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 thành phần 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ù giải pháp sử dụng mảng vòng hoàn toàn có thể tận dùng hàng loạt các mảng đã được cấp pháp bắt đầu nhưng khi mảng đầy thì không hề thêm thành phần vào hàng đã được nữa. Phương Pháp khắc phục :- Sử dụng Danh sách link .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 #include #include

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 chưa ? ( 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ì list link thực hiện thế nào đầy đã được ^ ^ ! )- Đưa thêm một thành phần 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 thực trạng đầy của việc sử dụng mảng để setup queue .

Ứng dụng của hàng đợi

Hàng đợi hoàn toàn có thể được sử dụng trong một vài ít bài toán :

Sản xuất và tiêu thụ (ứng dụng trong các hệ điều hành song song).Bộ đệm (Thí dụ: Nhấn phím -> Bộ đệm -> CPU xử lý).Xử lý các lệnh trong máy tính (ứng dụng trong hệ điều hành, trình biên dịch), hàng đợi các tiến trình chờ đã được xử lý.

Giới thiệu: Quang Sơn

Quang Sơn là giám đốc hocdauthau.com - Kênh thông tin học đấu thầu, kiến thức tổng hợp, công nghệ, đời sống.

0 Shares
Share
Tweet
Pin