Bài trước, tôi đã giới thiệu qua về việc cài đặt hàng đợi queue bằng mảng. Trong bài này chúng ta sẽ cùng đi chi tiết hơn về việc cài đặt hàng đợi queue bằng mảng trong ngôn ngữ C/C++. Các thao tác cần có khi cài đặt hàng đợi queue bằng mảng đó là:
- Khởi tạo Queue: Init (q)
- Kiểm tra Queue rỗng: IsEmpty (q)
- Kiểm tra Queue đầy: IsFull (q)
- Thêm phần tử vào Queue: Add(q, x)
- Lấy phần tử ra khỏi Queue: Remove (q)
Trước khi đi vào chi tiết các thao tác trên ta có hàng đợi khi cài đặt bằng mảng sẽ được khai báo như sau:
Bạn đang xem: 1.Hàm khởi tạo và kiểm tra hàng đợi queue bằng mảng
#define MAX 100 typedef struct queue { int A[MAX]; int front, rear; }; typedef struct queue QUEUE;
1.1 Hàm khởi tạo queue
Để khởi tạo hàng đợi ta cần có lệnh khởi tạo front = 0 và rear = -1 sẽ tạo ra một queue rỗng, sau khi thực hiện khởi tạo thành công ta sẽ đảm bảo các thao tác trên queue được thực hiện đúng đắn.
Hàm void Init(QUEUE &q) dưới đây nhận QUEUE &q là hàng đợi cần khởi tạo và thực hiện gán int front = 0; và int rear = -1;
void Init(QUEUE &q){ //gan front bang 0 q.front = 0; //gan rear bang -1 q.rear = -1; }
1.2 Hàm kiểm tra queue rỗng
Trước khi thực hiện việc lấy phần tử trong hàng đợi ra, ta cần phải đảm bảo việc kiểm tra queue đó là không rỗng. Nếu queue là rỗng thì không được phép lấy phần tử. Ở phần khởi tạo hàng đợi ta đã gán int front = 0; và int rear = -1; (nghĩa là front > rear ), vì vậy để kiểm tra rằng hàng đợi có là rỗng hay không ta chỉ cần thực hiện kiểm tra nếu front > rear thì hàng đợi đó đang rỗng, ngược lại thì không rỗng!
int IsEmpty(QUEUE q){ //neu front > rear thi hang doi rong va tra ve 1 if (q.front > q.rear){ return 1; } //nguoc lai khong rong thi tra ve 0 return 0; }
1.3 Kiểm tra queue đầy
Việc kiểm tra queue đã đầy hay chưa được gọi đến trước khi thực hiện thao tác đưa một phần tử vào queue. Nếu queue đó đầy thì phần tử cuối cùng của queue đó bằng MAX – 1 (trong đó MAX là số lượng phần tử mà ban đầu ta đã định nghĩa). Việc đó tương đương với việc so sánh int rear có bằng MAX – 1 hay không?
int IsFull (QUEUE q){ //neu rear == MAX – 1 thi hang doi day va tra ve 1 if (q.rear==MAX-1){ return 1; } //nguoc lai hang doi chua day return 0; }
2.1 Hàm add trong queue
Add chính là thao tác thêm phần tử mới vào trong hàng đợi. Việc thêm phần tử mới vào hàng đợi queue luôn luôn đặt phần tử được thêm vào cuối hàng đợi.
Xem thêm : Hướng dẫn fix iPhone 6 Plus tối nửa màn hình thành công
Trước khi thêm vào hàng đợi ta sẽ kiểm tra xem hàng đợi đó đã đầy hay chưa, nếu chưa đầy thì thực hiện việc thêm phần tử vào cuối hàng đợi.
Hàm void Add(QUEUE &q, int x) nhận QUEUE &q là hàng đợi cần thêm phần tử và int x là giá trị phần từ cần thêm vào cuối hàng đợi.
void Add (QUEUE &q, int x){ //Queue chưa đầy if (IsFull(q)==0) { //tang chi so rear len 1 don vi q.rear++; //them phan tu x vao cuoi hang doi q.A[q.rear] = x; } }
2.2 Hàm remove trong queue
Thao tác remove chính là thao tác lấy phần tử trong hàng đợi ra và đồng thời xóa đi phần tử đó. Việc lấy phần tử của hàng đợi luôn được thực hiện bằng cách lấy phần tử ở đầu hàng đợi đó ra.
Hàm int Remove(QUEUE &q) nhận QUEUE &q là hàng đợi cần thực hiện lấy ra phần tử đầu, hàm này thực hiện trả về phần tử đầu tiên của hàng đợi và đồng thời xóa đi phần tử vừa được lấy ra.
int Remove(QUEUE &q){ int x; //neu hang doi khong rong if (!IsEmpty(q)) { //gan x bang phan tu dau tien cua hang doi x = q.A[q.front]; //tang bien front len 1 don vi q.front++; //tra ve phan tu lay duoc return x; } else{//nguoc lai hang doi rong front = 0; rear = -1; } }
Để nhập được N phần tử vào trong hàng đợi ta cần sử dụng lại hàm void Add() ở trên và kết hợp với vòng lặp for. Để thực hiện lấy ra tất cả phần tử cũng tương tự như vậy.
Hàm nhập N phần tử vào trong hàng đợi cài đặt bằng mảng như sau:
void Input(QUEUE &q, int n){ //duyet tu 0 den n for(int i = 0; i< n; i++){ //thuc hien nhap gia tri vao bien x int x; printf(“Nhap gia tri phan tu thu %d: “,i); scanf(“%d”,&x); //thuc hien add phan tu x vao queue Add(q,x); } }
Hàm xuất ra những phần tử có trong hàng đợi nhưng không xóa đi chúng được biểu diễn như sau:
void Output(QUEUE q){ //duyet tu phan tu dau ve phan tu cuoi queue for(int i = q.front; i <= q.rear; i++){ //hien thi ra ket qua printf(“%d t”,q.A[i]); } }
Chương trình hoàn chỉnh dưới đây được lắp ghép lại từ các hàm ở trên, vì vậy bạn nên đọc kỹ các phần ở trên trước khi đến chương trình hoàn chỉnh này!
Xem thêm : Các Kỹ Thuật Bóng Đá Cơ Bản | Hướng Dẫn Chi Tiết
#include <stdio.h> #define MAX 100 typedef struct queue { int A[MAX]; int front, rear; }; typedef struct queue QUEUE; void Init(QUEUE &q){ //gan front bang 0 q.front = 0; //gan rear bang -1 q.rear = -1; } int IsEmpty(QUEUE q){ //neu front > rear thi hang doi rong va tra ve 1 if (q.front > q.rear){ return 1; } //nguoc lai khong rong thi tra ve 0 return 0; } int IsFull (QUEUE q){ //neu rear == MAX – 1 thi hang doi day va tra ve 1 if (q.rear==MAX-1){ return 1; } //nguoc lai hang doi chua day return 0; } void Add (QUEUE &q, int x){ //Neu queue chua day if (IsFull(q)==0) { //tang chi so rear len 1 don vi q.rear++; //them phan tu x vao cuoi hang doi q.A[q.rear] = x; } } int Remove(QUEUE &q){ int x; //neu hang doi khong rong if (!IsEmpty(q)) { //gan x bang phan tu dau tien cua hang doi x = q.A[q.front]; //tang bien front len 1 don vi q.front++; //tra ve phan tu lay duoc return x; } else{//nguoc lai hang doi rong q.front = 0; q.rear = -1; } } void Input(QUEUE &q, int n){ //duyet tu 0 den n for(int i = 0; i< n; i++){ //thuc hien nhap gia tri vao bien x int x; printf(“Nhap gia tri phan tu thu %d: “,i); scanf(“%d”,&x); //thuc hien add phan tu x vao queue Add(q,x); } } void Output(QUEUE q){ //duyet tu phan tu dau ve phan tu cuoi queue for(int i = q.front; i <= q.rear; i++){ //hien thi ra ket qua printf(“%d t”,q.A[i]); } } int main(){ //khai bao hang doi QUEUE q; //khoi tao hang doi Init(q); //nhap N int n; printf(“NHAP N: “); scanf(“%d”,&n); //nhap N phan tu vao hang doi Input(q,n); //hien thi phan tu printf(“Cac phan tu vua nhap vao queue la: n”); Output(q); //thao tac add int x = 66; Add(q,x); printf(“nHang doi sau khi add %d la: n”,x); Output(q); //thao tac lay ra phan tu hang doi int front = Remove(q); printf(“nHang doi sau khi remove phan tu %d la: n”,front); Output(q); } NHAP N: 5
Nhap gia tri phan tu thu 0: 11
Nhap gia tri phan tu thu 1: 22
Nhap gia tri phan tu thu 2: 33
Nhap gia tri phan tu thu 3: 44
Nhap gia tri phan tu thu 4: 55
Cac phan tu vua nhap vao queue la:
11 22 33 44 55
Hang doi sau khi add 66 la:
11 22 33 44 55 66
Hang doi sau khi remove phan tu 11 la:
22 33 44 55 66
Nguồn: https://sigma.edu.vn
Danh mục: Công Nghệ
