Hàng đợi (queue) là gì? Cách xây dựng hàng đợi

1. Hàng đợi (queue) là gì?

Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In First Out), tạm dịch là “vào trước ra trước”. Có nghĩa là phần tử nào được thêm hàng đợi trước thì sẽ được lấy ra trước.

Có thể hình dung hàng đợi như một đoàn người xếp hàng mua vé. Người nào xếp hàng trước sẽ được mua vé trước và ra khỏi hàng để nhường vị trí cho người xếp hàng ngay phía sau.

Có thể xem hàng đợi (queue) là một kiểu danh sách có 2 phép toán đặc trưng là:

• • Bổ sung một phần tử vào cuối danh sách (rear)
  • Loại bỏ một phần tử ở đầu danh sách (front)

Một số thao tác thông dụng trên queue như:

• enqueue(): thêm một phần tử vào queue.
• dequeue(): loại bỏ một phần tử ra khỏi queue.
• isFull(): kiểm tra queue có đầy chưa. Số lượng phần tử trong queue do người dùng quy định. Tùy trường hợp chúng ta mới cần sử dụng hàm isFull().
• isEmpty(): kiểm tra queue có rỗng hay không.

Trong lập trình, có 2 cách thường dùng để xây dựng queue là sử dụng mảng (array) và danh sách liên kết (linked list).

2. Xây dựng hàng đợi bằng mảng

Khi xây dựng queue bằng mảng thì chúng ta lưu ý một số vấn đề sau:

• • Cần có hai chỉ số front và rear để lưu chỉ số phần tử đầu và chỉ số phần tử cuối trong queue. Khởi tạo queue rỗng thì front = 0 và rear = -1.
  • Để thêm một phần tử vào queue, ta tăng rear lên 1 và đưa giá trị đó vào phần tử thứ rear trong mảng.
  • Để loại bỏ một phần tử khỏi queue, ta tăng front lên 1.
  • Chỉ những phần tử của mảng từ vị trí front tới rear mới được xem là các phần tử trong queue.
  • Khi front > rear thì queue đang rỗng.
  • Khi rear tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, không thể thêm phần tử vào nữa.

#include <iostream>
using namespace std;

#define max 10000
int Queue[max];
int front, rear;

void QueueInit(){
	front = 0;
	rear = -1;
}

void enqueue(int V){
	if(rear >= max-1){
		cout<<"Queue is full";
	}else{
		rear++;
		Queue[rear] = V;
	}
}

int dequeue(){
	if(front > rear){
		cout<<"Queue is empty";
		return -1;
	}else{
		int res = Queue[front];
		front++;
		return res;
	}
}

//print Queue
void printQueue(){
	if(front > rear){
		cout<<"Queue is empty";
	}else{
		cout<<"Elements in Queue:";
		for(int i=front;i<=rear;i++){
			cout<<Queue[i]<<" ";
		}
	}
}

int main(){
	//init Queue
	QueueInit();
	//enqueue to Queue
	enqueue(5);
	enqueue(21);
	enqueue(10);
	enqueue(99);
	enqueue(101);
	//print Queue
	printQueue();
	//dequeue from Queue
	cout<<endl<<"Dequeue fromt Queue:";
	cout<<dequeue()<<" ";
	cout<<dequeue()<<endl;
	//print Queue after dequeue
	cout<<"Print Queue after dequeue"<<endl;
	printQueue();
	system("pause");
}

Kết quả

Elements in Queue:5 21 10 99 101
Dequeue fromt Queue:5 21
Print Queue after dequeue
Elements in Queue:10 99 101

Nhận xét:

Khi sử dụng mảng để cài đặt queue, chỉ số rear và front chỉ tăng lên chứ không giảm đi, kể cả khi lấy các phần tử ra khỏi hàng đợi. Chỉ có các phần tử từ vị trí front tới rear là thuộc queue. Các phần tử từ vị trí 0 tới front-1 bị lãng phí.

Hơn nữa, nếu chỉ số rear tăng lên vượt quá số lượng phần tử cho phép trong mảng thì queue cũng bị tràn, không thể thêm phần tử vào queue nữa.

Chúng ta có thể sử dụng danh sách liên kết để cài đặt queue nhằm khắc phục các khuyết điểm trên.

3. Xây dựng hàng đợi bằng danh sách liên kết

Khi sử dụng danh sách liên kết đơn để xây dựng queue, nếu muốn thêm một phần tử vào queue thì ta thêm vào cuối danh sách. Nếu muốn lấy một phần tử ra khỏi queue thì ta hủy phần tử đầu danh sách.

#include <iostream>
using namespace std;

struct node{
	int data;
	node *next;
};

node * front;
node *rear;

void QueueInit(){
	front = NULL;
	rear = NULL;
}

void enqueue(int V){
	node *p;
	p = new node;
	p->data = V;
	p->next = NULL;
	if (front!=NULL){
		rear->next = p;
	}else{
		front = p;
	}
	rear = p;
}

int dequeue(){
	if (front == NULL){
		cout<<"Queue is empty";
		return -1;
	}else{
		int res = front->data;
		node *p = front->next;
		delete front;
		front = p;
		if(front == NULL){
			rear = NULL;
		}
		return res;
	}
}

//print Queue
void printQueue(){
	node  *p;
	p = front;
	cout<<"Elements in Queue:";
	while (p!= NULL){
		cout<<p->data<<" ";
		p = p->next;
	}
}

int main(){
	//init Queue
	QueueInit();
	//enqueue to Queue
	enqueue(5);
	enqueue(21);
	enqueue(10);
	enqueue(99);
	enqueue(101);
	//print Queue
	printQueue();
	//dequeue from Queue
	cout<<endl<<"Dequeue fromt Queue:";
	cout<<dequeue()<<" ";
	cout<<dequeue()<<endl;
	//print Queue after dequeue
	cout<<"Print Queue after dequeue"<<endl;
	printQueue();
	system("pause");
}

Kết quả

Elements in Queue:5 21 10 99 101
Dequeue fromt Queue:5 21
Print Queue after dequeue
Elements in Queue:10 99 101