Cấu trúc dữ liệu - Queue

Hiroshi · March 29, 2019, 3:35am

I. Queue là gì?

Queue (hàng đợi) là cấu trúc dữ liệu tương tự stack nhưng khác ở chỗ là nếu stack hoạt động theo cơ chế LIFO thì queue hoạt động theo cơ chế FIFO (First - in First - out). Tức là phần tử nào được thêm vào trước sẽ được truy xuất trước. Trong thực tế có khá nhiều hiện tượng giống như queue. Ví dụ như xe đi trên đường một chiều: Ta có thể thấy xe nào vào đường trước thì sẽ thoát ra trước. dữ liệu ở đây cũng vậy.

II. Cấu trúc hàng đợi (thực hiện với mảng):
Ở đây ta sử dụng các biến sau để cài đặt queue:

rear: chỉ số phần tử ở cuối queue.(Ta khởi tạo giá trị ban đầu của biến này là -1)
front: chỉ số phần tử ở đầu queue.(Giá trị ban đầu là 0).
queue[]: mảng chứa dữ liệu.
count: biến đếm số phần tử trong queue.(Giá trị ban đầu là 0)

III. Các hoạt động với Queue.
Tương tự như stack thì queue cũng có hai hoạt động chính:

Hoạt động enqueue(): Thêm phần tử vào cuối hàng đợi.
Hoạt động dequeue(): Xóa phần tử khỏi đầu hàng đợi.
Ngoài ra còn có các hàm bổ trợ:
Hoạt động isFull(): Kiểm tra xem queue đã đầy hay chưa.
Hoạt đông isEmpty(): Kiểm tra xem queue có rỗng hay không.
Hoạt động size(): Lấy ra số phần tử của queue.
Hoạt động Front(): lấy ra phần tử đầu tiên trong hàng đợi.

Hoạt động isFull() và isEmpty():
Để kiểm tra hàm rỗng hay đầy ta chỉ cần kiểm tra độ lớn của biến count:

Nếu count = MAXSIZE thì hàng đợi đã đầy.
Nếu count = 0 thì hàng đợi rỗng.
Code c++:

bool isEmpty()
{
	if(count == 0) return true;
	return false;
}

bool isFull()
{
	if(count == MAX) return true;
	return false;
}

Hoạt động size():
Để truy xuất ra kích thước của hàng đợi ta chỉ cần lấy ra biến count của hàng đợi.
Code c++:

int Size()
{
         return count;
}

Hoạt động Front():
Ta chỉ cần lấy ra phần tử thứ front trong hàng đợi (vì front chỉ đến phần tử đầu tiên như ta đã quy ước bên trên).

int Front()
{
	return queue[front];
}

Hoạt đông enqueue():
Để thêm một phần tử vào cuối hàng đợi ta cần làm theo các bước:

B1. Kiểm tra xem hàng đợi đã đầy hay chưa.
B2. Nếu hàng đợi đã đầy in thông báo rồi thoát khỏi hàm.
B3. Nếu hàng đợi chưa đầy thì thêm biến rear và count lên 1.
B4. Gán dữ liệu vào vị trí rear trong hàng đợi.

Code c++:

void enqueue(int data)
{
	if(!isFull())
	{
		rear++;
		count ++;
		queue[rear] = data;
	}
	else cout << "hang doi da day";
}

Hoạt động dequeue():
Để xóa phần tử đầu tiên khỏi hàng đơụ ta chỉ cần tăng thêm biến front lên 1 để nó không trỏ tới vị trí cần xóa nữa là được. Các bước thực hiện:

B1: Kiểm tra xem hàng đợi có rỗng hay không.
B2: Nếu hàng đợi rỗng(không có phần tử nào) thông báo rồi thoát khỏi hàm.
B3: Nếu hàng đợi không rỗng thì giảm front đi 1.

Code c++:

void dequeue()
{
	if(!isEmpty())
	{
		count--;
		front++;
	}
	else cout << "hang da het phan tu!";
}

IV. Toàn bộ code (Sử dụng mảng):

#include <iostream>
using namespace std;

const MAX = 10;
int queue[MAX];
int front = 0, rear = -1;
int count = 0;

bool isEmpty()
{
	if(count == 0) return true;
	else return false;
}
bool isFull()
{
	if(count == MAX) return true;
	return false;
}
int Front()
{
	return queue[front];
}
int size()
{
        return count;
}
void enqueue(int data)
{
	if(!isFull())
	{
		rear++;
		count ++;
		queue[rear] = data;
	}
	else cout << "hang doi da day";
}
void dequeue()
{
	if(!isEmpty())
	{
		count--;
		front++;
	}
	else cout << "hang da het phan tu!";
}
int main()
{}

V. Code theo hướng đối tượng OOP:

#include <iostream>
using namespace std;
const int MAX = 10;
 
class Queue{
	private:
		int rear = -1; // phan tu cuoi
		int front = 0; // phan tu dau tien
		int count = 0;
	public: 
		int queue[MAX];
		void enqueue(int data);
		void dequeue();
		int size();
		bool isFull();
		bool isEmpty();
		int Front();
}; 

bool Queue::isEmpty()
{
	return(count == 0) ;
}
bool Queue::isFull()
{
	return(count == MAX) ;
}
bool Queue::dequeue() isFull(){
	if(count == MAX) return true;
	return false;
}
int Queue::size(){
	return count;
}
int Queue::Front()
{
	if(!isEmpty())
	return queue[front];
}
void Queue::enqueue()
{
	if(!isFull())
	{
		rear++;
		count ++;
		queue[rear] = data;
	}
	else cout << "hang doi da day";
}
void Queue::dequeue()
{
	if(!isEmpty())
	{
		count--;
		front++;
	}
	else cout << "hang da het phan tu!";
}
int main()
{}

Trên đây là lí thuyết cơ bản về queue. Có nhiều thiếu xót mong các bạn góp ý; sửa chữa và bổ sung để có thể hoàn thiện kiến thức hơn. Chân thành cám ơn!!!

                                                                               Writer
                                                                                 KT

tntxtnt · March 27, 2019, 3:35pm

sao ko viết là return count == 0; luôn :V

code tuy là ví dụ nhưng đi xài biến toàn cục thấy dở quá. Thà viết mã giả luôn chứ viết ra code C++ thế này làm gì… ví dụ muốn xài 2 queue trong 1 chương trình thì làm thế nào

Hiroshi · March 27, 2019, 4:43pm

Cảm ơn góp ý của bạn. Mình viết mã giả hơi kém, với lại phần này mình cũng mới học nên viết code như vậy để nhớ những ý chính và tác dụng của hàm thôi. Còn trong chương trình tất nhiên sẽ không dùng biến toàn cục như vậy được.