Bài 16: Xây dựng queue trong C

[qads]

Hàng đợi ( Queue ) là một cấu trúc tài liệu dùng để chứa những đối tượng người dùng thao tác theo chính sá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, những đối tượng người tiêu 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 tiêu dùng thêm vào tiên phong mới được phép lấy ra khỏi hàng đợi. 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 từ đầu hàng đợi .

queue

1. Queue setup trên mảng

Ở bài Stack, tất cả chúng ta hoàn toàn có thể đếm số thành phần trong Stack bằng cách dùng 1 biến đếm ( count ) để cho thuận tiện, và ở phần Queue này tôi sẽ sử dụng biến đếm đó trong cấu trúc .

#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu

struct Queue
{
	int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
	item Data[Max]; //Mang cac phan tu
	int count; //dem so phan tu cua Queue
};

1.1 Khởi tạo Queue rỗng .

Để khởi tạo Queue rỗng ta cần đưa vị trí Front về 0, Rear về – 1, cout về 0 .

void Init (Queue &Q) //khoi tao Queue rong
{
	Q.Front = 0; //phan tu dau
	Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
	Q.count = 0; //so phan tu bang 0
}

1.2 Kiểm tra Queue rỗng, đầy

Kiểm tra rỗng đầy chỉ cần kiểm tra count so với 0 và max

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

int Isfull (Queue Q) //kiem tra Queue day
{
	if (Q.count == Max) //so phan tu = Max => day
		return 1;
	return 0;
}

1.3 Thêm thành phần vào cuối Queue ( Push )

Tăng vị trí của Rear lên 1 và đưa data vào vị trí đó

push

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	if (Isfull(Q)) printf("Hang doi day !");
	else
	{ 
		Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
		Q.count++; //tang so phan tu len
	}
}

1.4 Xóa thành phần đầu Queue ( Pop )

Trước tiên phải kiểm tra Queue rỗng không, nếu không rỗng ta thực thi chuyển dời những thành phần trong hàng về đầu hàng bằng vòng for ( giống như xếp hàng khi mua hàng ) sau đó giảm Rear và count xuống .

pop

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		item x = Q.Data[Q.Front];
		for (int i=Q.Front; i

1.5 Xem thông tin thành phần đầu Queue

item Qfront (Queue Q) //xem thong tin phan tu dau hang
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else return Q.Data[Q.Front];
}

1.6 hàng đợi vòng ( Queue Circular )

Như trên tất cả chúng ta thiết kế xây dựng Queue dựa vào mảng, và thấy 1 điểm bất lợi là khi xóa thành phần đầu Queue tất cả chúng ta cần vận động và di chuyển tổng thể những thành phần phía sau về trước. Để khắc phục điều này tất cả chúng ta hoàn toàn có thể coi mảng đó như 1 mảng với những phân tử được xếp vòng tròn .

Circular

Khi đó ta hoàn toàn có thể thêm, xóa những thành phần đơn thuần, tuy nhiên cần chú ý quan tâm khi thêm và xóa thành phần mà Rear và Front ở cuối mảng ( Max-1 ). Để khắc phục ta chia Front và Rear lây dư cho Max. Vậy là Nếu Front và Rear ở Max thì sẽ quay trở lại vị trí 0 .

void Push_Circular(Queue &Q, item x) //them phan tu vao cuoi hang doi vong
{
	if (Isfull(Q)) printf("Hang doi day !");
	else 
	{
		Q.Data[(++Q.Rear) % Max] = x; 
		//tang Rear len va gan phan tu vao, Neu Rear dang o vi tri Max-1 thi tang ve vi tri 0
		Q.count++; //tang so phan tu len
	}
}

int Pop_Circular(Queue &Q) //Loai bo phan tu khoi dau hang doi vong
{
	if (Isempty(Q)) printf("Hang doi rong !");
	item x = Q.Data[Q.Front];
	Q.Front = (Q.Front++) % Max; // tang vi tri phan dau tien len, neu dang o Max-1 thi ve 0
	Q.count--;//giam so phan tu xuong
	return x; //tra ve phan tu lay ra
}

1.7 Chương trình hoàn hảo ( full code )

#include 
#include 

#define Max 5 //so phan tu toi da cua Queue
typedef int item; //kieu du lieu

struct Queue
{
	int Front, Rear; //front: phan tu dau hang, rear: phan tu cuoi hang
	item Data[Max]; //Mang cac phan tu
	int count; //dem so phan tu cua Queue
};

void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
int Isfull(Queue Q); //kiem tra Queue day
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi 
void Push_Circular(Queue &Q, item x); //them phan tu vao cuoi hang doi vong
int Pop_Circular(Queue &Q); //Loai bo phan tu khoi dau hang doi vong
void Input (Queue &Q); //Nhap 
void Output(Queue Q); //Xuat 

void Init (Queue &Q) //khoi tao Queue rong
{
	Q.Front = 0; //phan tu dau
	Q.Rear = -1; // phan tu cuoi o -1 (khong co phan tu trong Q)
	Q.count = 0; //so phan tu bang 0
}

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

int Isfull (Queue Q) //kiem tra Queue day
{
	if (Q.count == Max) //so phan tu = Max => day
		return 1;
	return 0;
}

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	if (Isfull(Q)) printf("Hang doi day !");
	else
	{ 
		Q.Data[++Q.Rear] = x; //tang Rear len va gan phan tu vao
		Q.count++; //tang so phan tu len
	}
}

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		item x = Q.Data[Q.Front];
		for (int i=Q.Front; iMax || n<1);
	for (int i=0; i
link dự trữ

2. Queue thiết lập bằng con trỏ

queue pointer

2.1 Xây dựng cấu trúc

typedef int item; //kieu du lieu
struct Node
{
	item Data;
	Node * Next;
};
struct Queue
{
	Node * Front, *Rear; //Node dau va Node cuoi
	int count; //dem so phan tu
};

2.2 Khởi tạo .

Khởi tạo Queue ta cho Front và Rear cùng trỏ về NULL, count = 0 .

void Init(Queue &Q)
{
	Q.Front = Q.Rear = NULL;
	Q.count = 0;
}

2.3. Kiểm tra rỗng

int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

2.4 Tạo 1 Node P

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

2.5 Thêm thành phần vào cuối Queue

Để thêm thành phần, ta kiểm tra xem hàng có rỗng không, nếu hàng rỗng thì cho cả Front và Rear cùng trỏ về Node P mới tạo chứa phàn tử x cần thêm. Nếu không rỗng ta trỏ Rear -> Next về P. và Rear trỏ về P. Tăng count lên 1

push

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	Node *P = MakeNode(x); //Neu Q rong
	if (Isempty(Q))
	{
		Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
	}
	else //Khong rong
	{ 
		Q.Rear->Next = P;
		Q.Rear = P;
	}
	Q.count ++ ; //tang so phan tu len
}

2.6 Xóa thành phần đầu Queue

Ta kiểm tra Queue có rỗng không, Nếu không rỗng kiểm tra xem có 1 hay nhiêu hơn 1 phần tử, nếu có 1 phần tử thì ta khởi tạo lại Queue, nếu có nhiều hơn ta cho Front trỏ đến tiếp theo. Giảm count xuống 1.
pop

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) 
	{
		printf("Hang doi rong !");
		return 0;
	}
	else
	{
		item x = Q.Front->Data;
		if (Q.count == 1) //neu co 1 phan tu
			Init(Q);
		else
			Q.Front = Q.Front->Next;
		Q.count --;
		return x; //tra ve phan tu lay ra
	}
}

2.7 Chương trình hoàn hảo ( full code )

#include 
#include 

typedef int item; //kieu du lieu
struct Node
{
	item Data;
	Node * Next;
};
struct Queue
{
	Node * Front, *Rear; //Node dau va Node cuoi
	int count; //dem so phan tu
};

void Init (Queue &Q); //khoi tao Queue rong
int Isempty(Queue Q); //kiem tra Queue rong
void Push(Queue &Q, item x); //them phan tu vao cuoi hang doi
int Pop(Queue &Q); //Loai bo phan tu khoi dau hang doi
int Qfront (Queue Q); //xem thong tin phan tu dau hang doi 
Node *MakeNode(item x); //tao 1 Node
void Input (Queue &Q); //Nhap 
void Output(Queue Q); //Xuat 

void Init(Queue &Q)
{
	Q.Front = Q.Rear = NULL;
	Q.count = 0;
}
int Isempty (Queue Q) //kiem tra Queue rong
{
	if (Q.count == 0) //so phan tu = 0 => rong
		return 1;
	return 0;
}

Node *MakeNode(item x) //tao 1 Node
{
	Node *P = (Node*) malloc(sizeof(Node));
	P->Next = NULL;
	P->Data = x;
	return P;
}

void Push(Queue &Q, item x) //them phan tu vao cuoi Queue
{
	Node *P = MakeNode(x); //Neu Q rong
	if (Isempty(Q))
	{
		Q.Front = Q.Rear = P; //dau va cuoi deu tro den P
	}
	else //Khong rong
	{ 
		Q.Rear->Next = P;
		Q.Rear = P;
	}
	Q.count ++ ; //tang so phan tu len
}

int Pop(Queue &Q) //Loai bo phan tu khoi dau hang doi
{
	if (Isempty(Q)) 
	{
		printf("Hang doi rong !");
		return 0;
	}
	else
	{
		item x = Q.Front->Data;
		if (Q.count == 1) //neu co 1 phan tu
			Init(Q);
		else
			Q.Front = Q.Front->Next;
		Q.count --;
		return x; //tra ve phan tu lay ra
	}
}

void Input (Queue &Q) //nhap hang doi
{
    int i=0; 
    item x;
    do
    {
        i++;
        printf ("Nhap phan tu thu %d : ",i);
        scanf("%d",&x);
        if (x != 0) Push(Q,x);
    } while(x != 0); //nhap 0 de ket thuc
}

void Output(Queue Q)
{
	Node *P = Q.Front;
	while (P != NULL)
	{
		printf("%d   ",P->Data);
		P = P->Next;
	}
	printf("\n");
}

int main()
{
    Queue Q;
    Init(Q);
    Input(Q);
    Output(Q);

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("\n1: Kiem tra Queue rong");
    printf("\n2: Them phan tu vao Queue");
    printf("\n3: Xoa phan tu trong Queue");
    printf("\n4: Xuat Queue");
    printf("\n5: Thoat");
    do
    {
        printf("\nBan chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(Q)) printf("Queue rong !");
				else printf ("Queue khong rong !");
				break;
			}
			case 2:
			{
				item x;
				printf ("Nhap phan tu can chen vao Queue: ");
				scanf("%d",&x);
				Push(Q,x);
				break;
			}
			case 3:
			{
				Pop(Q);
				break;
			}
			case 4: 
			{
				Output(Q);
				break;
			}
			case 5: break;
		}
    }while (lua_chon !=5);
    return 0;
}

link dự trữ

3. Sử dụng Quêu có sẵn trong C + +

Giống như Stack trong C + +, Queue cũng được kiến thiết xây dựng và ta chỉ việc dùng mà thôi .

#include 
#include  // su dung queue

using namespace std;

int main() {
	queue  Q; // khai bao queue co kieu nguyen
	for (int i = 0; i < 10; i++) {
		Q.push(i * 78 + 26); // them phan tu vao queue
	}
	
	cout << "So luong phan tu trong queue: " << Q.size() << "\n";
	
	while (!Q.empty()) { // trong khi queue khong rong
		int x = Q.front(); 	// lay gia tri dau hang
		Q.pop(); 			// xoa gia tri dau hang
		cout << x << "  ";
	}
	
	cout << "\n";
	
	return 0;
}

4. Ứng dụng của queue

Queue được dùng để khử đệ qui, tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng và quay lui, vét cạn, tổ chức quản lý và phân phối tiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.

[ rps-include post = ” 2703 ″ shortcodes = ” false ” ]

Bạn hoàn toàn có thể sẽ thích :