Hướng dẫn khai báo queue c++

[qads]

Hàng đợi [Queue] là một cấu trúc dữ liệu dùng để chứa các đối tượng làm 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 có thể được thêm vào hàng đợi bất kỳ lúc nào, nhưng chỉ có đối tượng thêm vào đầu tiên mới được phép lấy ra khỏi hàng đợi. Việc thêm một đối tượng luôn diễn ra ở cuối hàng đợi và một phần tử luôn được lấy ra từ đầu hàng đợi.

Nội dung

1. Queue cài đặt trên mảng
- 1.1 Khởi tạo Queue rỗng.
- 1.2 Kiểm tra Queue rỗng, đầy
- 1.3 Thêm phần tử vào cuối Queue [Push]
- 1.4 Xóa phần tử đầu Queue [Pop]
- 1.5 Xem thông tin phần tử đầu Queue
- 1.6 hàng đợi vòng [Queue Circular]
- 1.7 Chương trình hoàn chỉnh [full code]
2. Queue cài đặt bằng con trỏ
- 2.1 Xây dựng cấu trúc
- 2.2 Khởi tạo.
- 2.3. Kiểm tra rỗng
- 2.4 Tạo 1 Node P
- 2.5 Thêm phần tử vào cuối Queue
- 2.6 Xóa phần tử đầu Queue
- 2.7 Chương trình hoàn chỉnh [full code]
3. Sử dụng Quêu có sẵn trong C++
4. Ứng dụng của queue

1. Queue cài đặt trên mảng

Ở bài Stack, chúng ta có thể đếm số phần tử trong Stack bằng cách dùng 1 biến đếm [count] để cho dễ dàng, 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 phần tử vào cuối Queue [Push]

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

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 phần tử đầ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 hiện di chuyển các phần tử 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.

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 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 || nNext về P và Rear trỏ về P. Tăng count lên 1
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 phần tử đầ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.

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 chỉnh [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ự phòng
3. Sử dụng Quêu có sẵn trong C++
Giống như
Stack trong C++, Queue cũng được 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

1. Queue cài đặt trên mảng

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

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

1.3 Thêm phần tử vào cuối Queue [Push]

1.4 Xóa phần tử đầu Queue [Pop]

2.6 Xóa phần tử đầu Queue

2.7 Chương trình hoàn chỉnh [full code]

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

Bài Viết Liên Quan

Toplist mới

Bài mới nhất

Chủ Đề