Tạo bài viết
Đăng ký
01/10/2018, 22:40

Lập trình C: Bài 16 – Xây dựng hàng đợi (Queue)

Lập trình C: Bài 16 – Xây dựng hàng đợi (Queue) Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 30 responses [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 ...

Lập trình C: Bài 16 – Xây dựng hàng đợi (Queue)

Tháng Một 20, 2018 nguyenvanquan7826 TUT Cấu trúc dữ liệu 30 responses

[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.

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í đó

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 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.

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<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
			Q.Data[i] = Q.Data[i+1];
		Q.Rear--; // giam vi tri phan tu cuoi xuong
		Q.count--;//giam so phan tu xuong
		return x; //tra ve phan tu lay ra
	}
}

1.5 Xem thông tin phần tử đầ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 chúng ta 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 phần tử đầu Queue chúng ta cần di chuyển tất cả các phần tử phía sau về trước. Để khắc phục điều này chúng ta có thể coi mảng đó như 1 mảng với các phân tử được xếp vòng tròn.

Circular

Khi đó ta có thể thêm, xóa các phần tử đơn giản, tuy nhiên cần lưu ý khi thêm và xóa phần tử 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ẽ trở về 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 chỉnh (full code)

#include <stdlib.h>
#include <stdio.h>

#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; i<Q.Rear; i++) //di chuyen cac phan tu ve dau hang
			Q.Data[i] = Q.Data[i+1];
		Q.Rear--; // giam vi tri phan tu cuoi xuong
		Q.count--;//giam so phan tu xuong
		return x; //tra ve phan tu lay ra
	}
}

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

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
}


void Input (Queue &Q) //nhap hang doi
{
	int n;
	item x;
	do
	{
		printf("Nhap so phan tu cua Queue (<%d) :",Max);
		scanf("%d",&n);
	} while (n>Max || n<1);
	for (int i=0; i<n; i++)
	{
		printf("Nhap phan tu thu %d : ", i+1);
		scanf("%d",&x);
		Push(Q,x);
		Push_Circular(Q,x); //hang vong
	}
}

void Output(Queue Q)
{
	if (Isempty(Q)) printf("Hang doi rong !");
	else
	{
		for (int i=Q.Front; i<=Q.Rear; i++)
		//for (int i=Q.Front, j=0; j<Q.count; j++, i = (i++) % Max) //hang vong
			printf("%d   ",Q.Data[i]);
		printf("
");
	}
}

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

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("
1: Kiem tra Queue rong");
    printf("
2: Kiem tra Queue day");
    printf("
3: Them phan tu vao Queue");
    printf("
4: Xoa phan tu trong Queue");
    printf("
5: Xuat Queue");
    printf("
6: Thoat");
    do
    {
        printf("
Ban chon: ");
        scanf("%d",&lua_chon);
		switch (lua_chon)
		{
			case 1:
			{
				if (Isempty(Q)) printf("Queue rong !");
				else printf ("Queue khong rong !");
				break;
			}
			case 2:
			{
				if (Isfull(Q)) printf("Queue day !");
				else printf ("Queue chua day !");
				break;
			}
			case 3:
			{
				item x;
				printf ("Nhap phan tu can chen vao Queue: ");
				scanf("%d",&x);
				Push(Q,x);
				//Push_Circular(Q,x); hang vong
				break;
			}
			case 4:
			{
				Pop(Q);
				//Pop_Circular(Q); hang vong
				break;
			}
			case 5: 
			{
				Output(Q);
				break;
			}
			case 6: break;
		}
    }while (lua_chon !=6);
    return 0;
}

link dự phòng

2. Queue cài đặt 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 phần tử vào cuối Queue

Để thêm phần tử, 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 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.
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 chỉnh (full code)

#include <stdlib.h>
#include <stdio.h>

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("
");
}

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

    int lua_chon;
    printf("Moi ban chon phep toan voi DS LKD:");
    printf("
1: Kiem tra Queue rong");
    printf("
2: Them phan tu vao Queue");
    printf("
3: Xoa phan tu trong Queue");
    printf("
4: Xuat Queue");
    printf("
5: Thoat");
    do
    {
        printf("
Ban 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 <iostream>
#include <queue> // su dung queue

using namespace std;

int main() {
	queue <int> 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() << "
";
	
	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 << "
";
	
	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”]

Trịnh Tiến Mạnh

27 chủ đề

6824 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024