Hàng đợi queue - Cách cài đặt hàng đợi trong C/C++ - https://final-blade.com

Hàng đợi queue trong C / C + + là một kiểu cấu trúc tài liệu giải thuậ t được học ở những môn học cơ bản .. Bài viết này mình sẽ san sẻ cho những bạn cách cài đặt hàng đợi bằng list link. Từ đó tìm ra cách ứng dụng hàng đợi vào giải những bài tập tương quan .

Tóm Tắt

1. Lý thuyết về hàng đợi

Hàng đợi hay ngắn gọn là hàng ( Queue ) là một list đặc biệt quan trọng trong đó việc thêm thành phần chỉ thực thi tại một đầu của hàng gọi là cuối hàng ( Rear ). Còn việc lấy ra thành phần khỏi hàng thì triển khai ở đầu còn lại của hàng gọi là đầu hàng ( Front ) .

Hàng đợi còn gọi là cấu trúc FIFO ( First In – First Out ) ” vào trước – ra trước ”. Thật vậy, phần tử vào đầu tiên sẽ ra trước, tương tự, phần tử vào sau sẽ ra sau. Cái này quá giống với thực tế luôn.

Bạn đang đọc: Hàng đợi queue – Cách cài đặt hàng đợi trong C/C++ – https://final-blade.com

Bạn tưởng tượng nó giống hệt việc xếp hàng như trong thực tiến đời sống. Ví dụ như : xếp hàng mua vé, xếp hàng lên máy bay. . .

Các phép toán cơ bản trên hàng đợi

Thêm phần từ vào hàng đợi
Khởi tạo hàm đợi
Kiểm tra hàm đợi đầy, rỗng
Xóa phần tử khỏi hàng đợi

Ứng dụng của hàng đợi trong thực thế?

Có nhiều bạn sẽ vướng mắc cái cấu trúc tài liệu này ứng dụng trong những bài toán thế nào ? Loại cấu trúc này sẽ vận dụng vào những bài toán cần có tính logic thứ tự. Ví dụ như việc giải quyết và xử lý những tiến trình của máy tính. Hoặc quản trị những hóa đơn đặt hàng. . .
vi du thuc te ve hang doi queue

2. Cách đặt hàng đợi Queue bằng mảng code C/C++

Có hai cách cài đặt hàng đợi :

Sử dụng mảng
Sử dụng con trỏ

Ở bài viết này mình sẽ nói kĩ hơn về cách setup bằng mảng nhé ! Bạn muốn xem cách setup bằng con trỏ thì bạn hoàn toàn có thể tìm hiểu thêm tại đây .

Cách cài đặt bằng mảng

Khai báo mảng chứa các phần tử của hàng đợi
Giả sử hàng có n phần tử thì front = 1 và rear = n.
Khi lấy một phần tử khỏi đầu hàng thì front tăng lên 1, thêm phần tử vào cuối hàng thì rear tăng lên 1.

hang doi cai dat bang mang c

Nhược điểm:

Hàng sẽ có giới hạn các phần tử.
Ngoài ra có thể bị tràn và dư thừa phần trống. Để khắc phục chúng ta sẽ sử dụng mảng vòng, phần dưới mình sẽ nói kĩ hơn nhé!

Mình sẽ viết code bằng C + +, bạn nào viết bằng C thì chỉ cẩn sửa một chút ít câu lệnh nhập xuất là được nhé ! Oke khởi đầu vào code demo thôi nha .

2.1 Khai báo hàng đợi queue

Hay còn gọi là cài đặt hàng đợi nhé ^^!

Xem thêm: Tìm hiểu về Facade trong Laravel – Vantien’s blog

// by tailieu.pro 
#include
using namespace std;
#define N 100
typedef int item;

struct Queue{
	int Front, Rear;
	item Data[N];
	int count;
};

Trong đoạn code trên, mình khai báo số thành phần max N của hàng là 100, một mảng Data để chứa thành phần, hai biến front, rear. Biến count là để đếm số thành phần trong mảng hiện có .

2.2 Khởi tạo hàng đợi – Make_Q

Các bạn chú ý, website đang bị lỗi hiển thị kí tự &. Nó sẽ chuyển thành & amp; Nên bạn nào copy code về phải sửa mới chạy được nhé!

Code của mình Code bạn sẽ thấy :

// Ham khoi tao queue
void Make_Q(Queue & Q){
	Q.Front=0;
	Q.Rear = -1;
	Q.count=0;
	
}
Queue Q;

Bởi vì hiện tại trong list không có thành phần nào, nên mình sẽ đặt Front = 0 và Rear = – 1. Count = 0 ;
( Đặt rear = – 1 vì lúc này trong hàng đợi không có thành phần nào cả )

2.3 Hàm kiểm tra hàng rỗng, hàng đầy

Hàng rỗng tức là hàng không có phần tử nào ( count = 0) còn hàng đầy thì count = N

//Ham kiem tra hang rong
int Check_null(Queue Q){
	if(Q.count==0)
		return 1;
	return 0;
}
// Ham kiem tra hang day
int Check_full(Queue Q){
	if(Q.count==N)
		return 1;
	return 0;
}

2.4 Hàm thêm 1 phần tử vào cuối hàng đợi

Việc thêm phần tử sẽ ở một đầu của cuối hàng đợi tức là tăng rear +1, count + 1.
Để tránh bị dư thừa bộ nhớ mảng ta sẽ dùng mảng vòng, nếu như rear != N -1 ( vị trí cuối mảng ) thì ta tăng rear lên 1. Còn nểu rear == N-1 thì ta đặt rear về 0.

them phan tu vao hang doi Ví dụ về thêm phần tử tại vị trí 6-1

// Ham them 1 phan tu vao hang doi
void Insert_last(Queue & Q, item x){
	if(Check_full(Q))
		cout<<"\nHang day"< 2.5 Nhập các phần tử cho hàng đợi từ bàn phím
Ở đây mình sẽ gọi hàm chèn thêm một thành phần ở bên trên, phối hợp vòng lặp while, điều kiện kèm theo nhập vào là - 1 sẽ kết thúc. Bạn hoàn toàn có thể tùy chỉnh điều kiện kèm theo theo ý của mình nhé !
// Nhap hang doi tu ban phim
void Import_Q(Queue & Q){
	item x=0; //Nhap x =-1 de ket thuc
	while(x!=-1){
	cout<<"\nNhap phan tu can them: "; cin>>x;
	if(x!=-1)
	Insert_last(Q,x);
	}
}

2.6 Xuất ra màn hình
Xuất ra màn hình các phần tử sẽ có hai trường hợp xảy ra. Một trường hợp là hàng chưa vòng tròn ( Front + count <=N ).
Trường hợp thứ 2 là hàng đã vòng tròn. Bạn xem code rồi hình dung ra nhé!

Xem thêm: Laravel là gì? Tại sao Laravel là PHP Framework tốt nhất năm 2021?

void Export_Q(Queue Q){
      if ( (Q.Front + Q.count ) <= N){
	for(int i=Q.Front; i<(Q.count+Q.Front);i++){
		cout<<"\t"<2.7 Xóa phần tử khỏi hàng đợi
Có hai vị trí đặc biệt quan trọng tất cả chúng ta cần xóa, một là ở vị trí tiên phong ( Del_first ) sau đó là ở vị trí k bất kỳ ( Del_k )
void Del_first(Queue & Q){
	if(Check_null(Q))
		cout<<"\nHang trong"<N)
		cout<<"\nVi tri xoa khong hop le";
	else{
		if(k==1)
			Del_first(Q);
		if(k==(Q.count+1)){
			Q.Rear--;
			Q.count--;
		}
		else{
			for(int i=(k-1); i<(Q.Front+Q.count);i++)
				Q.Data[i]=Q.Data[i+1];
			Q.Rear--;
			Q.count--;
		}
	}
}


3. Code hàng đợi  C++ hoàn chỉnh
Đây chỉ là một bài tập ví dụ về hàng đợi thiết lập bằng mảng. Nếu bạn chăm sóc thì hoàn toàn có thể xem thêm những setup bằng con trỏ tại đây .
//by tailieu.pro
// Queue cai dat bang mang 
#include
using namespace std;
#define N 100
typedef int item;

struct Queue{
	int Front, Rear;
	item Data[N];
	int count;
};
Queue Q;

void Make_Q(Queue & Q){
	Q.Front=0;
	Q.Rear = -1;
	Q.count=0;
	
}
int Check_null(Queue Q){
	if(Q.count==0)
		return 1;
	return 0;
}

int Check_full(Queue Q){
	if(Q.count==N)
		return 1;
	return 0;
}

void Del_first(Queue & Q){
	if(Check_null(Q))
		cout<<"\nHang trong"<>x;
	if(x!=-1)
	Insert_last(Q,x);
	}
}
void Export_Q(Queue Q){
      if ( (Q.Front + Q.count ) <= N){
	for(int i=Q.Front; i<(Q.count+Q.Front);i++){
		cout<<"\t"<N)
		cout<<"\nVi tri xoa khong hop le";
	else{
		if(k==1)
			Del_first(Q);
		if(k==(Q.count+1)){
			Q.Rear--;
			Q.count--;
		}
		else{
			for(int i=(k-1); i<(Q.Front+Q.count);i++)
				Q.Data[i]=Q.Data[i+1];
			Q.Rear--;
			Q.count--;
		}
	}
}
main(){
	Make_Q(Q);
	Import_Q(Q);
	int k;
	cout<<"\nNhap vi tri can xoa: "; cin>>k;
	Del_k(Q, k);
	Export_Q(Q);
	cout<<"\nThe end";
	return 0;
}

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com