Hàng đợi queue – Cách cài đặt hàng đợi trong C/C++

1
463
hang doi queue cai dat hang doi bang mang c

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

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

Hàng đợi hay ngắn gọn là hàng( Queue ) là một danh sách đặc biệt trong đó việc thêm phần tử chỉ thực hiện tại một đầu của hàng gọi là cuối hàng ( Rear ). Còn việc lấy ra phần tử khỏi hàng thì thực hiện ở đầ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 hình dung nó giống hệt việc xếp hàng như trong thực tiến cuộc 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ẽ thắc mắc cái cấu trúc dữ liệu này ứng dụng trong các bài toán thế nào? Loại cấu trúc này sẽ áp dụng vào các bài toán cần có tính logic thứ tự. Ví dụ như việc xử lý các tiến trình của máy tính. Hoặc quản lý các 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 cài đặt bằng mảng nhé! Bạn muốn xem cách cài đặt bằng con trỏ thì bạn có thể tham khảo 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 câu lệnh nhập xuất là được nhé!Oke bắt đầ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é ^^!

// by tailieu.pro 
#include<iostream>
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ố phần tử max N của hàng là 100, một mảng Data để chứa phần tử, hai biến front, rear. Biến count là để đếm số phần tử 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 &amp; Q){
	Q.Front=0;
	Q.Rear = -1;
	Q.count=0;
	
}
Queue Q;

Bởi vì hiện tại trong danh sách không có phần tử 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ó phần tử 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 &amp; Q, item x){
	if(Check_full(Q))
		cout<<"\nHang day"<<endl;
	else{
		if(Q.Rear==(N-1))
			Q.Rear=0;
		else
			Q.Rear++;
		Q.Data[Q.Rear]=x;
		Q.count++;
	}
}

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 phần tử ở bên trên, kết hợp vòng lặp while, điều kiện nhập vào là -1 sẽ kết thúc. Bạn có thể tùy chỉnh điều kiện theo ý của mình nhé!

// Nhap hang doi tu ban phim
void Import_Q(Queue &amp; 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é!

void Export_Q(Queue Q){
      if ( (Q.Front + Q.count ) <= N){
	for(int i=Q.Front; i<(Q.count+Q.Front);i++){
		cout<<"\t"<<Q.Data[i];
	}
      }
      else{
        for( int i = Q.Front ; i < N; i++ )
                cout<<"\t"<<Q.Data[i];
        for ( int i =0; i< (Q.count - (N-Q.Front))
                cout<<"\t"<<Q.Data[i];
      }
}

2.7 Xóa phần tử khỏi hàng đợi

Có hai vị trí đặc biệt chúng ta cần xóa, một là ở vị trí đầu tiên ( Del_first) sau đó là ở vị trí k bất kì ( Del_k)

void Del_first(Queue &amp; Q){
	if(Check_null(Q))
		cout<<"\nHang trong"<<endl;
	else{
		if(Q.count==1)
			Make_Q(Q);
		else{
			if(Q.Front==(N-1))
				Q.Front=0;
			else
				Q.Front++;
			
			Q.count--;
		}
	}
}

// Xoa o vi tri k bat ki
void Del_k(Queue &amp;Q, int k){
	if(k<1 || k>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 cài đặt bằng mảng. Nếu bạn quan tâm thì có thể xem thêm các cài đặt bằng con trỏ tại đây.

//by tailieu.pro
// Queue cai dat bang mang 
#include<iostream>
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 &amp; 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 &amp; Q){
	if(Check_null(Q))
		cout<<"\nHang trong"<<endl;
	else{
		if(Q.count==1)
			Make_Q(Q);
		else{
			if(Q.Front==(N-1))
				Q.Front=0;
			else
				Q.Front++;
			
			Q.count--;
		}
	}
}

void Insert_last(Queue &amp; Q, item x){
	if(Check_full(Q))
		cout<<"\nHang day"<<endl;
	else{
		if(Q.Rear==(N-1))
			Q.Rear=0;
		else
			Q.Rear++;
		Q.Data[Q.Rear]=x;
		Q.count++;
	}
}

void Import_Q(Queue &amp; 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);
	}
}
void Export_Q(Queue Q){
      if ( (Q.Front + Q.count ) <= N){
	for(int i=Q.Front; i<(Q.count+Q.Front);i++){
		cout<<"\t"<<Q.Data[i];
	}
      }
      else{
        for( int i = Q.rear ; i < N; i++ )
                cout<<"\t"<<Q.Data[i];
        for ( int i =0; i< (Q.count - (N-Q.rear))
                cout<<"\t"<<Q.Data[i];
      }
}

void Del_k(Queue &amp;Q, int k){
	if(k<1 || k>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;
}

1 COMMENT

LEAVE A REPLY

Please enter your comment!
Please enter your name here